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

72 阅读 0 评论 48 点赞

我是靠谱客的博主平常睫毛膏，最近开发中收集的这篇文章主要介绍超全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;
}

因为有小伙伴问了，可否在构建二叉树传入的参数为一级地址。上述的方法是一定要传二级参数的，但是这里给出一个传一级参数的方法，小伙伴也可以通过对比两种方法，对二叉树的构建和传参方式有更深的理解。

struct TreeNode* Create(){
int val;
scanf("%d", &val);
struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode*));
if (val <= 0) {
return NULL;
}
if (!root) {
printf("创建失败n");
}
if (val > 0) {
root->val = val;
root->left = Create();
root->right = Create();
}
return root;
}

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*));
//第二种构建方式：
//root = Create();
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);
}
}