✨个人主页： Yohifo
所属专栏： 数据结构 | C语言
每篇一句： 图片来源

  • Only by self-respect will you compel others to respect you.
    • 只有自尊才能迫使他人尊敬你。

文章目录

  • 前言
  • 正文
    • 认识二叉树
    • 实现二叉树
      • 结构
      • 节点数
      • 树深度
      • 前、中、后序遍历
        • ✒️前序遍历
        • ✒️中序遍历
        • ✒️后序遍历
        • ✒️二叉树的销毁
    • 玩转二叉树
      • 构建树
      • 层序遍历
      • 判断是否为完全二叉树
    • 源码
    • 相关题目
  • 总结

前言

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

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

正文

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

认识二叉树

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

  • 顺序结构
    • 即以数组的形式存储节点信息，这种结构一般用于存储完全二叉树
    • 比如之前学过的堆，因为数组正好符合完全二叉树连续存储的要求
  • 链式结构
    • 即以链表的形式存储节点信息，这种结构可以用于所有二叉树，本文代码结构也是以链式为主
    • 二叉树普遍都是不规则的，数组难以满足节点分散这个要求

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

  • 空树也可以看作二叉树
  • 任何一棵二叉树，都可以分为根、左子树、右子树
  • 二叉树中不存在度大于2的节点（度即当前节点的子树数量）
  • 二叉树的子树有左右之分，顺序不可颠倒，即左边一定是左树
  • 任何一棵二叉树都只能由以下几种情况构成：

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

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

实现二叉树

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

结构

前面说过，二叉树主要有两种表现形式，关于数组的已经在前一篇文章中提过了，现在来说说链式结构（链式二叉树）
任何一棵二叉树都有根、左、右三部分，细化到一个节点也是如此，因此链式二叉树在结构上分为以下三部分

  1. 数据域，负责存放当前节点的元素信息
  2. 左子树（左孩子），指向左树的指针
  3. 右子树（右孩子），指向右树的指针

代码实现如下

typedef char BTDataType;//二叉树的数据类型typedef struct BinaryTreeNode{BTDataType data;//存储节点的元素信息，每个节点都有struct BinaryTreeNode* left;//左子树（左孩子）struct BinaryTreeNode* right;//右子树（右孩子）}BTNode;

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

节点数

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

关于二叉树的节点数

  • 对于二叉树来说，不为空的都可以称为一个节点，如上图所示，共计5个节点，其中节点 ‘A ’ 为根节点（root）
  • 统计二叉树节点需要巧妙利用递归，大问题化为小问题

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

  • 首先我们需要统计的是整棵二叉树的节点数，已知任何一棵二叉树都可以看成 n 棵树组成的树，而每二叉棵树都有根、左、右三部分组成
  • 其中如果根不为空，那么这个节点就是有效节点，可以参与统计，为空就不参与
  • 现在我们只考虑一个节点是否合法，如果合法，那么返回1，兵分两路走向它的左右子树，继续判断
  • 观察发现二叉树肯定存在边界，比如上图，最底层的空就是边界，当我们往下递归，碰到空时，直接返回，不再往下判断
  • 整个过程符合递归要求：有终止条件+接近手段，我们可以从根节点开始往下递出，最后返回每次判断所得到的节点数就行了（要么是0，要么是1），这就是递归
  • 这个思想比较重要，后面很多函数都是走的这个思想

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

代码实现如下所示

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

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

树深度

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

  • 设两个变量：leftDepth 和 rightDepth ，分别用来存储左右子树的深度
  • 左右子树的深度即左右子树的节点数，统计方式与上面函数类型
  • 得到这两个深度后，判断谁是较大的一方，返回它
  • 这也是个典型的递归，终止条件为节点为空，接近手段为向下移动

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

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

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

前、中、后序遍历

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

  • 前、中、后序思想一致，无非就是出发点和结束点不一样罢了
  • 前序：根出发，最右子树结束
  • 中序：最左子树出发，最右子树结束
  • 后序：最左子树出发，根结束
  • 三种方式遍历代码量可以说是完全一致，只不过顺序不同罢了

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

✒️前序遍历


芝士代码

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

✒️中序遍历


芝士代码

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

✒️后序遍历


芝士代码

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

✒️二叉树的销毁

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

// 二叉树销毁void BinaryTreeDestory(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, int n, int* pi){assert(a);//如果一开始就为 # 就没必要创建了if (a[*pi] == '#'){(*pi)++;//向后移动，找到下一个值return NULL;}BTNode* node = (BTNode*)malloc(sizeof(BTNode));assert(node);node->data = a[(*pi)++];//赋值，并向后移动node->left = BinaryTreeCreate(a, n, pi);//左右链接node->right = BinaryTreeCreate(a, n, pi);return node;//最开始的节点就是根节点}

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

层序遍历

层序遍历，又被称为 广度优先遍历，之前是前、中、后序都属于深度优先遍历，所谓广度优先，就是一层一层的遍历，比如最开始的演示二叉树，层序遍历结果为：A B C D E
层序遍历不必依靠递归，但是需要借助队列，因为队列的性质很符合广度这个要求

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

具体实现步骤：

  • 核心思想：先将根节点入队，然后出队，带根节点的下一层入队（如果存在的话）
  • 当根节点入队，出队打印后，把第二层的节点入队
  • 如此重复，直到每层所有节点遍历完毕
  • 循环终止条件是队列是否为空，当队列为空时，说明整棵二叉树都入过队了

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

芝士代码

// 层序遍历void BinaryTreeLevelOrder(BTNode* root)//需要借助队列{if (!root){printf("队列为空!\n");return;}//思路：根节点先入队，出队时，带左右孩子入队（如果存在的话）//如此重复，直到队空Queue tmp;QueueInit(&tmp);QueuePush(&tmp, root);//根节点入队while (!QueueEmpty(&tmp)){//取队头节点，出队QListDataType node = 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 次
  • 核心思想仍然为 出上一层，带下一层
  • 原层序遍历中的打印当前出队得到的节点，会被替换成判断当前节点是否为空
  • 原层序遍历中，为空的节点是入不了队的，但这里不管当前节点的左右子树是否为空，都入队，假如不是完全二叉树，那么肯定就存在循环未终止的情况下，出队取到空节点
  • 仔细想想，用节点数作为循环终止条件，如果是完全二叉树，是肯定取不到空节点的，因为它根本没机会入队
  • 这样一来，问题就很好解决了，无非就是 入队、出队、判断、入队 如此重复

不多解释，看 动图

代码在这里

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

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

源码

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

相关题目

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

二叉树OJ试题集

总结

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

如果你觉得本文写的还不错的话，期待留下一个小小的赞，你的支持是我分享的最大动力！

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

…

相关文章推荐
关于“堆”，看看这篇文章就够了（附堆的两种应用场景）
数据结构 | 单链表
数据结构 | 栈和队列