☑️前言

🚩二叉树可以说是我们学习数据结构路上的第二个高的台阶，要想跨越它，需要我们多画图，多理解，多思考它的 递归 过程。前面 树的介绍 和 堆 这两篇文章让我们对树有了一定的了解，对于二叉树的概念也有说到，因此，本章不会对二叉树的概念及介绍深入去讲，而是着重于它的实现，着重于理解递归。

🚩二叉树是后面一些高阶数据结构的基础，例如：红黑树，AVL树，B树等等。并且，我们在面试当中，也经常会被面试官要求手撕二叉树的相关OJ题，所以，二叉树这一章节就显得额外重要，可不敢遇到困难就退缩了。

🚩本章实现的二叉树是一棵普通的二叉树，与之前的数据结构有所不同，它的增删查改功能没那么有意义，那么什么时候有意义呢？我们在普通二叉树的基础上加上某一性质，使其能够通过这一性质来管理左右子树，这时候的增删查改就有意义了，例如搜索二叉树等等。

搜索二叉树：

🚩所以本章的二叉树，是打基础。我们在学习的过程中，一定要细细品味整个递归的过程，最好就是画图理解。接下来就带大家实现一棵属于自己的初等二叉树吧！

关于二叉树的补充

在实现普通二叉树之前，我们还需知道一些东西。

• 对于 堆 ，是采用顺序结构来存储数据的，那是因为 堆 的逻辑结构是一棵完全二叉树，那么本章的二叉树是否也能采用顺序结构来存储数据呢？先来看下图：

可以看到，可以是可以，但是一棵二叉树不一定就是完全二叉树，如果采用顺序存储结构的话，这里可能会有很多的空间浪费，因此，二叉树将采用链式的储存结构来存储数据，每一个数据对应一个树结点（结构体）。由于是二叉，所以我们只需要定义两个树结点的指针分别指向该结点的左孩子和右孩子即可。

前面说了，二叉树是递归定义的，因此后面的功能接口的实现几乎全是采用递归方法。

对于一棵二叉树，我们可以把它分成根，左子树和右子树，而它的左子树和右子树又可以分为根，左子树和右子树，依次这样下去，整个二叉树就有了递归的性质了，所以为什么二叉树是递归定义的，这是很重要的原因。

对于二叉树的递归，一个很重要的思想 —— 分治思想 贯穿全文，它可以形象为： 一个大学的校长想统计整个学校的人数，然后这个校长就叫来1院长和2院长去统计他们各自学院的人数，然后1院长和2院长又分别叫来各自的系主任去统计各自系的人数…最后分到每个寝室长统计各自寝室的人数，等最后一层统计完后，再依次上报，最终汇总到校长手中。这就是典型的分治思想。

得到一个树的结点

• 这里我们的普通二叉树实现都是在一个文件里：BinaryTree.c。
  
• 最开始我们要包含一下所需头文件：

#include <stdio.h>
// 断言所需
#include <assert.h>
// 申请空间所需
#include <stdlib.h>
// 布尔类型所需
#include <stdbool.h>

• 得到一个树的结点，我们首先要定义一个结点的结构体。一个结点包含存储的数据和分别指向左孩子结点和右孩子结点的两个指针，定义如下：

typedef int BTDataType;
typedef struct TreeNode
{
  // 存储数据
  BTDataType data;
  // 指向左结点的指针
  struct TreeNode* left;
  // 指向右结点的指针
  struct TreeNode* right;
}BTNode;

• 有了结点的定义之后，如何得到一个结点呢？当然是向内存申请一个结点的空间，申请之后，我们顺便将这个结点里的成员初始化：data 给自己想要的值，两个指针分别置为NULL。最后返回指向该结点空间的指针即可。

相关函数接口代码实现：

// 得到一个结点
BTNode* BuyTreeNode(BTDataType x)
{
  BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
  // 判断一下是否申请空间失败
  assert(newnode);
  newnode->data = x;
  // 两个指针都初始化 NULL
  newnode->left = NULL;
  newnode->right = NULL;
  // 返回指向这个结点空间的指针
  return newnode;
}

自己捣鼓的二叉树

• 有了得到一个树结点的功能后，接下来就是按照自己的意思创建一棵树了。

这里我们采用下面这棵树作为例子：

相关函数接口代码实现：

BTNode* BuyTree()
{
  // 依次得到一个结点
  BTNode* n1 = BuyTreeNode(1);
  BTNode* n2 = BuyTreeNode(2);
  BTNode* n3 = BuyTreeNode(3);
  BTNode* n4 = BuyTreeNode(4);
  BTNode* n5 = BuyTreeNode(5);
  BTNode* n6 = BuyTreeNode(6);
  BTNode* n7 = BuyTreeNode(7);
  // 通过每个结点内的指针进行树的连接
  n1->left = n2;
  n2->left = n3;
  n1->right = n4;
  n4->left = n5;
  n4->right = n6;
  n2->right = n7;
  // 返回所有结点的祖先结点
  return n1;
}

不同的二叉树这里的代码不同，根据自己的需求来建树。

二叉树的前序遍历

• 前序遍历的顺序是 根 - 左 - 右 ，先打印 根 ，然后递归左和右， 如果当前结点为 NULL，打印NULL，然后递归返回。

图示理解：

相关函数接口代码实现：

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

二叉树的中序遍历

• 中序遍历的顺序是 左 - 根 - 右 ，先遍历该二叉树的左子树，然后根，最后右子树， 然后该二叉树的左子树和右子树又是先遍历其左子树，然后根，最后右子树，这样就分成了若干个子问题。如果当前结点为 NULL，打印NULL，然后递归返回。

图示理解：

相关函数接口代码实现：

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

二叉树的后序遍历

• 前序遍历的顺序是 左 - 右 - 根 ，先遍历该而二叉树的左子树，然后右子树，最后根，然后该二叉树的左子树和右子树又是先遍历其左子树，然后右子树，最后根。这样就分成了若干个子问题。如果当前结点为 NULL，打印NULL，然后递归返回。

图示理解：

相关函数接口代码实现：

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

二叉树的结点个数

求二叉树的结点个数，我们可以采用一种分治思想， 求 该树的左子树的结点个数加上该树的右子树的结点个数再加上自己。然后该树的左子树和右子树又可以分成 求 该子树的左子树的结点个数加上该子树的右子树的结点个数再加上自己，这样不断将问题细化，符合递归的性质。

如果该根节点为NULL，说明不是一个结点，返回0。

图示理解：

相关函数接口代码实现：

// 二叉树的结点个数
int TreeNodeSize(BTNode* root)
{
  // +1 是算上自己为一个结点
  return root == NULL ? 0 : TreeNodeSize(root->left) + TreeNodeSize(root->right) + 1;
}