超全C语言二叉树基本操作及讲解

今天刷LeetCode上的题的时候，做到了关于二叉树的题，于是决定把这一块的知识整理一下。

1、二叉树的定义

二叉树通常以结构体的形式定义，如下，结构体内容包括三部分：本节点所存储的值、左孩子节点的指针、右孩子节点的指针。这里需要注意，子节点必须使用指针，就像我们定义结构体链表一样，下一个节点必须使用地址的方式存在在结构体当中。

struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
};

当然，我们也可以为我们的的树节点结构体重新定义一下名字，使用C语言中的typedef方法就可以了。

typedef struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
} BiNode, *BiTree;

在本篇博客中，我们还是使用第一种方法来定义结构体，因为这是LeetCode中定义二叉树的方式，同时也方便下面讲解创建二叉树。

2、二叉树的创建

二叉树的操作通常使用递归方法，如果递归不太明白，建议去对此进行一下学习和练习。二叉树的操作可以分为两类，一类是需要改变二叉树的结构的，比如二叉树的创建、节点删除等等，这类操作，传入的二叉树的节点参数为二叉树指针的地址，这种参入传入，便于更改二叉树结构体的指针（即地址）。这里稍微有一点点绕，可能需要多思考一下。

如下是二叉数创建的函数，这里我们规定，节点值必须为大于0的数值，如果不是大于0的数，则表示结束继续往下创建子节点的操作。然后我们使用递归的方法以此创建左子树和右子树

int CreateTree(struct TreeNode** root) {

	int val;
	scanf_s("%d", &val);
	if (val <= 0) {
		*root = NULL;
		return 0;
	}

	*root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
	if (!root) {
		printf("创建失败\n");
	}

	if (val > 0) {
		(*root)->val = val;
		CreateTree(&((*root)->left));
		CreateTree(&((*root)->right));
	}
	return 0;
}

3、先、中、后序遍历二叉树

先序、中序和后序，实际上是指的根节点在子节点的先中后。以上图为例，

先序为：3、2、2、3、8、6、5、4，

中序为：2、2、3、3、4、5、6、8，

后序为2、3、2、4、5、6、8、3。

其实这三种遍历方式，实现过程还是十分相似的，在递归顺序方面有些不同，其他都一样，代码量很少，如下。

先序：

void PreOrderTree(struct TreeNode* root) {
	if (root == NULL) {
		return;
	}
	printf("%d ", root->val);
	PreOrderTree(root->left);
	PreOrderTree(root->right);
}

中序：

void InOrderTree(struct TreeNode* root) {
	if (root == NULL) {
		return;
	}
	InOrderTree(root->left);
	printf("%d ", root->val);
	InOrderTree(root->right);
}

后序：

void PostOrderTree(struct TreeNode* root) {
	if (root == NULL) {
		return;
	}
	PostOrderTree(root->left);
	PostOrderTree(root->right);
	printf("%d ", root->val);
}

验证程序是否正确的主函数和结果图如下：

int main()
{
	struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode*));
	
	CreateTree(&(root));
	printf("先序排列为：");
	PreOrderTree(root);
	printf("\n中序排列为：");
	InOrderTree(root);
	printf("\n后序排列为：");
	PostOrderTree(root);
	return 0;
}

4、二叉树的最大深度（LeetCode104）

int maxDepth(struct TreeNode* root) {
	if (root == NULL) {
		return 0;
	}
	else {
		int maxLeft = maxDepth(root->left), maxRight = maxDepth(root->right);
		if (maxLeft > maxRight) {
			return 1 + maxLeft;
		}
		else {
			return 1 + maxRight;
		}
	}
}

这也是LeetCode 104 Maximum Depth of Binary Tree题的答案，在做这道题的时候，一开始我并没有定义maxLeft和maxRight这两个变量，直接在判断处调用函数，这导致整个程序的运行时间过长。这道题的思想很简单，一棵树的最大深度，左子树和右子树的最大深度+1即可，使用递归，截止条件判断好了，很容易就能够做出来。

5、二叉树叶子节点的数量

这里我们要提到“度”的定义，简单来说，一个节点的度就是一个节点的分支数，二叉树中的节点按照度来分类的话，分为三类，度分别为0、1、2的节点，我们将其数量表示为n0、n1、n2，且我们将一棵树的总结点数量用N来表示。那么一个数的叶子节点的数量即为n0，且有N=n0+n1+n2。如果我们按照一棵树的子节点数来计算一棵树的总结点数，那么一棵二叉树树的总结点数N=2*n2+n1+1，最后一个1表示树的根节点。我们将关于N的两个等式合并，则有结论：

n0=n2+1

上述的结论与我们下面求叶子节点没有什么关系，只是作为一个知识的普及。

叶子节点计算方法如下：

int LeafNodeNum(struct TreeNode* root) {
	if (root == NULL) {
		return 0;
	}

	if (root->left == NULL&&root->right == NULL) {
		return 1;
	}
	else {
		return LeafNodeNum(root->left) + LeafNodeNum(root->right);
	}
}