【初阶数据结构】详解二叉树 - 树和二叉树（三）（递归的魅力时刻）

前言

如果有看过的堆和堆排序这篇文章的话，你一定对二叉树的顺序存储有了一定的了解，但是这个是有特定的使用环境的。

那么在本文中，我将要给大家讲解二叉树的另一种表示方式——链式结构，以及我会给大家讲解有了顺序存储结构，为什么还要使用链式存储结构？以及如何用链式创建一棵二叉树？此外，还要讲解递归在二叉树中扮演着何种角色？

1. 二叉树链式结构的意义

在学习堆时，我们说堆的本质就是一棵完全二叉树，而完全二叉树的结构注定了我们使用顺序表来存储比较方便，而这个就是二叉树的顺序存储。

可能大家也意识到了一个点：好像二叉树的顺序存储有个要求，那就是这棵二叉树必须得是完全二叉树。没错！

如果我们不分青红皂白地使用顺序结构来存储二叉树会发生什么可怕的是事情呢？
请大家将目光往下注视：

可以看到，如果我们遇到的是一棵非完全二叉树，并且我们还要有顺序结构来存储这棵树。第一步，我们就得在逻辑上将这颗树补全为完全二叉树，但是补的地方我们是不能进行任何的操作的。那这个就十分尴尬，自己创建的空间却不能愉快地使用，有点扯淡了！而且这样的方式很浪费空间资源，从上图你就可以看出有几个空间是没有办法使用的。

那该怎么办呢？此时，天空一声巨响，二叉树的链式结构就闪亮登场了！

二叉树的链式结构针对的群体就是普通的二叉树。 那至于普通二叉树链式是如何被我们用代码创建的，让我们接着往下看！

2. 手搓一棵二叉树

这里为了降低大家的学习成本，我先不教大家如何用函数创建二叉树，如果大家对自己的二叉树比较有自信的话，可以移步到本文的后面，学习如何用函数创建一棵二叉树。

学习是要一步一步来的，我们不能不懂装懂，有时候也得直面不完美的自己！

二叉树链式结构示意图：

那我们这里开始就开始手搓一棵二叉树，为了方便大家学习，我会按照下面的图的给大家建立，往后的操作都是以这副图为基础。

代码如下：

//二叉树结点的结构体
typedef int BTDataType;typedef struct BTNode
{BTDataType data;struct BTNode* left;struct BTNode* right;}BTNode;BTNode* BuyNewnode(BTDataType x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));newnode->data = x;newnode->left = NULL;newnode->right = NULL;return newnode;
}BTNode* CreateTree()
{BTNode* node1 = BuyNewnode(1);BTNode* node2 = BuyNewnode(2);BTNode* node3 = BuyNewnode(3);BTNode* node4 = BuyNewnode(4);BTNode* node5 = BuyNewnode(5);BTNode* node6 = BuyNewnode(6);//开始结点之间的链接node1->left = node2;node1->right = node3;node2->left = node4;node2->right = node5;node3->right = node6;return node1;
}

这种方式初学者来说十分的友好。

3. 二叉树的遍历（重要）

接下来，我来讲一下本文的精华 —— “二叉树的遍历”。为什么会说是精华的部分呢？因为想要学会这个就得先知道递归的规则，并且这是科班同学在练习中会经常遇到的题目。同时这个也是二叉树的入门门槛！

二叉树遍历有四种方式，分别是：

• 先序遍历（可能有的书籍会称其为"先根遍历"）
• 中序遍历
• 后序遍历
• 层序遍历

3.1 遍历的规则

1. 先序遍历：遍历顺序为根、左子树、右子树。记忆的规则就是，先序又称先根，顾名思义就是根结点先遍历。
2. 中序遍历：遍历顺序为左子树、根、右子树。记忆的规则就是，中序是将根结点放在遍历的中间顺序。
3. 后序遍历：遍历顺序为左子树、右子树、根。记忆的规则就是，后序是将根节点但在遍历的最后顺序。
4. 层序遍历：遍历的顺序时按照一层层开始，每一层从左往右依次遍历各节点。

在本文，会重点讲解先序遍历、中序遍历以及后序遍历。

为了更好的讲解每种遍历的规则，接下来我会分篇幅给大家做进一步的讲解。

3.2 先序遍历

先序遍历：遍历顺序为根、左子树、右子树。

任何一颗树都是由根节点及其子树所构成的。二叉树也是如此，二叉树由其根节点、左子树和右子树所构成。其中，左子树由其根节点、左子树和右子树所构成…。给人一种循环的感觉，而这个就是递归！大家可以从下图(只做了部分的划分)感受一下

好了，我们根据先序遍历的规则，写出它的数据遍历的顺序（注意：空树用NULL表示）。

先序遍历的顺序：1 2 4 NULL NULL 5 NULL NULL 3 NULL 6 NULL NULL

怎么样，不是很困难吧。

3.3 中序遍历

中序遍历：遍历顺序为左子树、根、右子树

趁热打铁，我们把中序遍历也讲了。

有了先序遍历的经验，中序遍历洒洒水啦！

这里我就直接写答案了：

中序遍历的顺序：NULL 4 NULL 2 NULL 5 NULL 1 NULL 3 NULL 6 NULL

3.4 后序遍历

后序遍历：遍历顺序为左子树、右子树、根。

后序遍历的顺序：NULL NULL 4 NULL NULL 5 2 NULL NULL NULL 6 3 1

3.5 遍历的代码实现

这个就体现出递归的魅力时刻了！

这里我会拿先序遍历作为重点讲解，其余遍历方式的思维都是一样的。

3.5.1 先序遍历代码实现

先序遍历：遍历顺序为根、左子树、右子树。

//先序遍历
void PreOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}printf("%d ",root->data);PreOrder(root->left);PreOrder(root->right);
}

当遇到一个递归却被深深绕进去时，最好画一个递归展开图！

3.5.2 中序遍历代码实现

中序遍历：遍历顺序为左子树、根、右子树

//中序遍历
void InOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}InOrder(root->left);printf("%d ",root->data);InOrder(root->right);
}

3.5.3 后序遍历代码实现

后序遍历：遍历顺序为左子树、右子树、根。

//后序遍历
void PostOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data);
}

可能大家在平常的练习中看到的是这种形式的，

要想出来这个效果，我们只需要把printf("NULL ")这个语句注释掉即可。但是需要提醒大家的一点就是，上面这幅图的结果并不是二叉树原本的模样，大家要理解本质！

4. 统计二叉树结点的个数

在这里我要给大家将一个非常重要的思想 —— “分治思想”。

给大家设置一个场景，假如现在我是一位大学的校长，我要统计学校的人数。我该怎么做？

第一种方法：我到学生宿舍一个一个人的统计人数，每当宿舍有一个新生时，我就在我的小本本上画"正"字的一个笔画。最后我只要统计小本本上有多少个正字即可。

但是这个方法非常的费"校长"。不经的会感叹到这个校长当得也太累了吧！

第二种方法：既然身为一校之长，我肯定有一定的权力。我就让每个院的院长汇报各自院的人数给我，我再统计不就好了。院长接到任务后，就命令每个专业的系主任汇报各专业人数给我。每个系主任又叫每个班的班长统计各班的人数给他。之后，以宿舍为单位，让宿舍长汇报宿舍人数给班长，班长再做汇总，将结果给系主任。
这不就纯纯是打工人体系！！！

汇报人数的情况：

有了这个思想之后，我们写代码！

int TreeSize(BTNode* root)
{//写法一if(root == NULL){return 0;}return TreeSize(root->left) + TreeSize(root->right) + 1;/* //写法二return root == NULL? 0: TreeSize(root->left) + TreeSize(root->right) + 1;*/
}

5. 统计二叉树的高度

用了分治思想，这个代码似乎也能理解了。

int TreeHeight(BTNode* root)
{if(root == NULL){return 0; }int left_height = TreeHeight(root->left);int right_height = TreeHeight(root->right);return left_height > right_height? left_height + 1:right_height + 1;}

6. 统计二叉树的指定层数的结点个数

这里给大家提供一个思路：当前K层结点的个数 = 对应左子树K-1层结点的个数 + 对应右子树K-1层结点的个数

int TreeKLevel(BTNode* root, int k)
{if(root == NULL){return 0;}if(k == 1){return 1;}int leftK = TreeKLevel(root->left,k-1);int rightK = TreeKLevel(root->right,k-1);return leftK + rightK;
}

好了，本文就到这里结束了！

本文主要讲解了二叉树链式结构的定义以及接口的实现，其中有个重要的思想可以帮助我们更快的理解递归背后的本质，体会到递归的魅力。

最后如果觉得本文写的不错的话，麻烦给偶点个赞吧！！！