📘前言

二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。简言之，二叉树是数据结构中非常重要的东西，在很多OJ试题和笔试题中，都会出现它的影子；至于高阶数据结构中的各种树，比如二叉搜索树、AVL树、红黑树、B树等都是基于二叉树的高阶树。总之，现在把普通二叉树学好了，对以后的学习是十分有帮助的。

Tips：二叉树的学习与之前略有不同，我们不讨论普通二叉树的增删查改，因为对于普通二叉树来说，这些操作意义不大

📘正文

这是一棵很标准的满二叉树，可以一起来拜一拜（愿程序无Bug）

📖认识二叉树

如上图所示，这是一棵现实中的二叉树，我们看着很形象，也很容易理解 “二叉” 这个概念，不过计算机可不这样认为，在它眼中二叉树要么长这样 [1,2,3,4,5]，要么长这样 1->2->3->4->5

没错，二叉树在计算机中可以有两种表示形式

顺序结构

即以数组的形式存储节点信息，这种结构一般用于存储完全二叉树

比如之前学过的堆，因为数组正好符合完全二叉树连续存储的要求

链式结构

即以链表的形式存储节点信息，这种结构可以用于所有二叉树，本文代码结构也是以链式为主

二叉树普遍都是不规则的，数组难以满足节点分散这个要求

知道结构后还需加以规则限制，二叉树的规则有

空树也可以看作二叉树

任何一棵二叉树，都可以分为根、左子树、右子树

二叉树中不存在度大于2的节点（度即当前节点的子树数量）

二叉树的子树有左右之分，顺序不可颠倒，即左边一定是左树

任何一棵二叉树都只能由以下几种情况构成：

关于二叉树的更多性质可以查看下图

好了，了解以上知识，就算碰到二叉树的门槛了，关于二叉树的具体实现，还得接着往下看

📖实现二叉树

这部分主要是实现一些简单功能，涉及大量递归知识，系好安全带，准备出发

📃结构

前面说过，二叉树主要有两种表现形式，关于数组的已经在前一篇文章中提过了，现在来说说链式结构（链式二叉树）

任何一棵二叉树都有根、左、右三部分，细化到一个节点也是如此，因此链式二叉树在结构上分为以下三部分

数据域，负责存放当前节点的元素信息

左子树（左孩子），指向左树的指针

右子树（右孩子），指向右树的指针

代码实现如下

typedefcharBTDataType;    //二叉树的数据类型typedefstructBinaryTreeNode{
BTDataTypedata;    //存储节点的元素信息，每个节点都有structBinaryTreeNode*left;    //左子树（左孩子）structBinaryTreeNode*right;   //右子树（右孩子）}BTNode;

注意： 因为链式二叉树每次都需要单独申请节点，因此没有初始化函数，但每个节点都有初始化状态： 数据域置0，左右子树都指向空 。二叉树的销毁需要借助递归+后序遍历的方式销毁，后面会提及

📃节点数

为了方便后续功能的讲解，先在假设存在一棵二叉树，形状如下所示，代码实现时由自己手动进行申请、赋值、链接

关于二叉树的节点数

对于二叉树来说，不为空的都可以称为一个节点，如上图所示，共计5个节点，其中节点 'A ’ 为根节点（root）

统计二叉树节点需要巧妙利用递归，大问题化为小问题

如何递归呢？

众所周知，递归是个技巧，代码极其简洁，但不太好懂，也不太好调试，并且存在很多问题（栈溢出、运行时间慢等），但这丝毫不妨碍我们在这里使用它，理由如下：

首先我们需要统计的是整棵二叉树的节点数，已知任何一棵二叉树都可以看成 n 棵树组成的树，而每二叉棵树都有根、左、右三部分组成

其中如果根不为空，那么这个节点就是有效节点，可以参与统计，为空就不参与

现在我们只考虑一个节点是否合法，如果合法，那么返回1，兵分两路走向它的左右子树，继续判断

观察发现二叉树肯定存在边界，比如上图，最底层的空就是边界，当我们往下递归，碰到空时，直接返回，不再往下判断

整个过程符合递归要求：有终止条件+接近手段，我们可以从根节点开始往下递出，最后返回每次判断所得到的节点数就行了（要么是0，要么是1），这就是递归

这个思想比较重要，后面很多函数都是走的这个思想

长话短说，借助递归+二叉树的特性，将整个二叉树走一遍，如果发现当前节点为空，就不往下走，否则会一直往下走，总体路径为 根 -> 左 -> 右，最后会回归每次判断所得的节点数，整个过程如图所示，这是一个比较长的 动图，耐心看完

// 二叉树节点个数intBinaryTreeSize(BTNode*root)
{
//一级指针，不能断言，不然就无法递归if (!root)
return0;
return1+BinaryTreeSize(root->left) +BinaryTreeSize(root->right);    //根 + 左 + 右}

注意： 除了单纯统计二叉树节点数外，还有两个变种：统计叶子节点数与统计第k层节点数，其中统计叶子节点数是在原代码基础上增加一个判断，即没有左右子树的节点才是叶子节点，才能被计数返回；至于统计第k层节点，需要借助k，每下潜一层，k-1，直到 k 为1时，才计数返回。这两个变种对代码的改动不大，篇幅有限，这里就不再展开叙述（完整源码中有）

📃树深度

二叉树的深度，指根节点的左右子树深度中的较大值，假如根的左子树深度为3，右子树的深度为1，那么整棵树的深度为3，同样的，需要借助递归，步骤如下

设两个变量：leftDepth 和 rightDepth ，分别用来存储左右子树的深度

左右子树的深度即左右子树的节点数，统计方式与上面函数类型

得到这两个深度后，判断谁是较大的一方，返回它

这也是个典型的递归，终止条件为节点为空，接近手段为向下移动

一样的通过 动图 来演示整个过程，这次的动图会省去很多文字讲解，更加注重过程

这个的代码量也很少，无非就是比上面多了两句

//二叉树的深度intBinaryTreeDepth(BTNode*root)
{
if (!root)
return0;
//大问题化小问题：求左右子树的最大深度intleftDepth=BinaryTreeDepth(root->left);
intrightDepth=BinaryTreeDepth(root->right);
return (leftDepth>rightDepth?leftDepth : rightDepth) +1;   //左右根}

📃前、中、后序遍历

学校最喜欢考的东西，其实很简单，我们直接三剑齐发，再附带一个销毁

遍历思想：

前、中、后序思想一致，无非就是出发点和结束点不一样罢了

前序：根出发，最右子树结束

中序：最左子树出发，最右子树结束

后序：最左子树出发，根结束

三种方式遍历代码量可以说是完全一致，只不过顺序不同罢了

关于这三种遍历方式，我想直接通过三张动图解决，单独将没啥意义，复读而已，还不如动图来的直观

✒️前序遍历

芝士代码

// 二叉树前序遍历 voidBinaryTreePrevOrder(BTNode*root)
{
if (!root)
    {
printf("NULL ");
return;
    }
//前序：根左右printf("%c ", root->data);
BinaryTreePrevOrder(root->left);
BinaryTreePrevOrder(root->right);
}

✒️中序遍历

芝士代码

// 二叉树中序遍历voidBinaryTreeInOrder(BTNode*root)
{
if (!root)
    {
printf("NULL ");
return;
    }
//中序：左根右BinaryTreeInOrder(root->left);
printf("%c ", root->data);
BinaryTreeInOrder(root->right);
}

✒️后序遍历

芝士代码

// 二叉树后序遍历voidBinaryTreePostOrder(BTNode*root)
{
if (!root)
    {
printf("NULL ");
return;
    }
//后序：左右根BinaryTreePostOrder(root->left);
BinaryTreePostOrder(root->right);
printf("%c ", root->data);
}

✒️二叉树的销毁

二叉树的销毁其实和后续遍历差不多，不过是把打印换成了 free 当前节点，其实也很好理解，想要销毁整棵二叉树就得从最后一层开始往上销毁，如果先销毁的是上面的节点，那么下面的节点就丢失了，如此看来，只有后序符合这个要求，通过后序遍历能完美销毁整棵二叉树，代码如下

// 二叉树销毁voidBinaryTreeDestory(BTNode**root)
{
assert(root);   //传过来的这个二级指针不能为空//先销毁左孩子，再销毁右孩子，最后销毁根 ---> 后序if (!(*root))
return; //叶子，不必销毁//左右根BinaryTreeDestory(&((*root)->left));
BinaryTreeDestory(&((*root)->right));   //取地址 --- 函数形参为二级指针free((*root));  //销毁当前节点    (*root) =NULL;
}

注意：二叉树在销毁时，要传二级指针，不然形参的改变是无法影响外面实参。如果想使用一级指针的话，在调用完销毁函数后，还得手动把根节点置空，避免野指针问题

📖玩转二叉树

二叉树的热身环节已经结束了，现在准备进入更高难度的函数，带你从多种角度玩转二叉树

📃构建树

首先来看看这个热门题：根据一个已知数组（存放的是某二叉树前序遍历的结果，# 表示空），构建出原二叉树。 题目的意思很简单，就是提供某二叉树的前序遍历结果，包括空也提供了，让我们根据这个结果，还原出原来的二叉树，前序遍历我们已经解决了，反过来还不简单？步骤如下

根据题目可知，数组中的 # 表示空，反过来说，如果遇到的不是 #，那就说明这是一个节点

如果是 # ，直接 return NULL；否则就申请一个节点，将此节点看作根节点

每次递归函数要么产生新节点，要么直接返回 NULL，利用前序遍历思想，在得到根节点后，递归链接其左右孩子，至于孩子是节点还是 NULL ，得看递归结果

最后再返回当前节点信息，除了根节点可以返回出函数外，其他的节点信息都是返回给上一层节点，即成为他们的左右孩子，返回时，整棵树才会被链接起来

长话短说，这就是一个递归遍历数组+申请节点链接的程序，每次递归，都得保证数组递归遍历能往后走，前序思想为 根、左、右，大问题转小问题：先保证这个节点存在，再链接其左右孩子。代码实现时需要多加小心，比如传递数组下标时，要传地址，不然数组都走不下去，还有递归终止条件为当前数组值是否为 # ，接近手段就是数组的遍历，具体看**动图**实现：

代码如下

// 通过前序遍历的数组"A B D # # E # H # # C F # # G # #"构建二叉树BTNode*BinaryTreeCreate(BTDataType*a, intn, int*pi)
{
assert(a);
//如果一开始就为 # 就没必要创建了if (a[*pi] =='#')
    {
        (*pi)++;    //向后移动，找到下一个值returnNULL;
    }
BTNode*node= (BTNode*)malloc(sizeof(BTNode));
assert(node);
node->data=a[(*pi)++];    //赋值，并向后移动node->left=BinaryTreeCreate(a, n, pi);    //左右链接node->right=BinaryTreeCreate(a, n, pi);
returnnode;    //最开始的节点就是根节点}

注意： 参数【数组下标】，需要传地址，不然数组遍历就无法进行下去

📃层序遍历

层序遍历，又被称为 广度优先遍历，之前是前、中、后序都属于深度优先遍历，所谓广度优先，就是一层一层的遍历，比如最开始的演示二叉树，层序遍历结果为：A B C D E

层序遍历不必依靠递归，但是需要借助队列，因为队列的性质很符合广度这个要求

队列的性质：先进先出，后进后出

具体实现步骤：

核心思想：先将根节点入队，然后出队，带根节点的下一层入队（如果存在的话）

当根节点入队，出队打印后，把第二层的节点入队

如此重复，直到每层所有节点遍历完毕

循环终止条件是队列是否为空，当队列为空时，说明整棵二叉树都入过队了

这个层序遍历得看看 动图 ，光凭文字不好描述：

芝士代码

// 层序遍历voidBinaryTreeLevelOrder(BTNode*root) //需要借助队列{
if (!root)
    {
printf("队列为空!\n");
return;
    }
//思路：根节点先入队，出队时，带左右孩子入队（如果存在的话）//如此重复，直到队空Queuetmp;
QueueInit(&tmp);
QueuePush(&tmp, root);  //根节点入队while (!QueueEmpty(&tmp))
    {
//取队头节点，出队QListDataTypenode=QueueFront(&tmp);
QueuePop(&tmp); //出队printf("%c ", node->data);  //打印元素//判断左右节点是否存在，存在就入队if (node->left)
QueuePush(&tmp, node->left);
if (node->right)
QueuePush(&tmp, node->right);
    }
QueueDestroy(&tmp);
}

注意： 这里借助了队列，需要引出相关头文件，入队列的元素是指向二叉树节点的指针，即二叉树节点 BinaryTreeNode* 在队列相关头文件中，需要特别注意一下，把队列元素类型修改为对应类型

📃判断是否为完全二叉树

这是力扣上的中等题，牛客上的困难题，也是本文的压轴戏

完全二叉树，指连续的二叉树，判断是否为完全二叉树的关键就是 判断当前树是否连续（每一层都要连续），涉及到层序遍历，一样需要借助队列，不过循环终止条件和入队条件不同，也不需要打印了，只是多了一个判断，步骤如下：

提前统计出二叉树的节点树，存储在变量 countNode 中，循环 countNode 次

核心思想仍然为 出上一层，带下一层

原层序遍历中的打印当前出队得到的节点，会被替换成判断当前节点是否为空

原层序遍历中，为空的节点是入不了队的，但这里不管当前节点的左右子树是否为空，都入队，假如不是完全二叉树，那么肯定就存在循环未终止的情况下，出队取到空节点

仔细想想，用节点数作为循环终止条件，如果是完全二叉树，是肯定取不到空节点的，因为它根本没机会入队

这样一来，问题就很好解决了，无非就是 入队、出队、判断、入队 如此重复

不多解释，看 动图

代码在这里

// 判断二叉树是否是完全二叉树boolBinaryTreeComplete(BTNode*root)
{
//空树也是完全二叉树if (!root)
returntrue;
//完全二叉树一定是有序的，需要利用层序遍历思想//循环节点次//取节点的时候，如果节点为空，说明不是完全二叉树Queuetmp;
QueueInit(&tmp);
QueuePush(&tmp, root);  //根节点入队intcountNode=BinaryTreeSize(root);   //获取节点数while (countNode--)
    {
QListDataTypenode=QueueFront(&tmp);
QueuePop(&tmp);
//如果取到空，说明不是完全二叉树if (!node)
returnfalse;
//左右孩子都入队QueuePush(&tmp, node->left);
QueuePush(&tmp, node->right);
    }
QueueDestroy(&tmp);
returntrue;
}

注意：在判断时，是判断当前节点是否为空，而非节点中的数据；上文中所有动图可能存在丢帧的情况，在录制时好好的，转成 gif 动图就出现这种情况了，如果感觉动图表意不明的，可以联系我查看原视频（更清晰、更丝滑）

📖源码

源码在我的 Gitee 仓库中，可以点击这里跳转

📖相关题目

二叉树这部分也是有很多OJ试题，感兴趣的同学的尝试着去做一做

二叉树OJ试题集

📘总结

以上就是二叉树的全部内容了，为了确保每种功能的直观性，我几乎为每个函数都配上了动图（制作不易，且看且珍惜），回顾全文，我们从何为二叉树出发，学习了二叉树的基础功能，最后还涉及了二叉树的部分中等知识，相信你在看完本文后，一定能学到很多干货，轻松理解二叉树！

如果本文有不足或错误的地方，随时欢迎指出，我会在第一时间改正