数据结构与算法：树

博客大纲

树

树的定义

树是一种非线性的数据结构，它是由n个有限的节点组成的一个有层次的数据的集合。这个数据结构叫做树是因为它像一颗倒挂的树。

在树结构中，有一个特殊的节点–根节点。他是一棵树的出发点，也就是最上面的那个节点，在此图中A就是根节点。

此外，树有一个最大的特点，就是每个节点都可以作为根，重新视为一颗树，比如下图中，红色三角形内可以视为一颗以D为根节点的树。

这样的树，称为这棵树的子树，一棵树可以有非常多的子树，因为任意一个节点都可以拿出来视作一个根节点，哪怕这个节点已经是最后一个节点了。比如上图中的B节点，它可以视为一颗只有根的树。

树与非树：

我刚刚为大家简单介绍了一下树的定义，但是仍可能存在对树结构的误判，在此只需要记住最重要的一点：除了根节点没有父节点，其余的所有节点都只有一个父节点。

再上图中，我标识了三个红色的指针，它们都是影响这个树结构的指针。

比如C指向了同一层的节点D，导致D节点有AC两个父亲；C指向了下一层的节点H，导致H节点有CD两个父亲；J指向了上一层的节点F，导致F节点有AJ两个父亲。

以上情况都导致了树的结构被破坏。

与树有关的概念

相比于之前的线性数据结构，树的相关概念非常多，但是整体来说还是不难理解的，接下来我就一一讲解：

节点的度：一个节点含有的子树的个数称为该节点的度

如上图中，A的度为6，D的度为3，B的度为0。

树的度：一棵树中，最大的节点的度称为树的度

如上图：树的度为6

叶节点或终端节点：度为0的节点称为叶节点

如上图：B、C、H、I…等节点为叶节点

非终端节点或分支节点：度不为0的节点

如上图：D、E、F、G…等节点为分支节点

双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点

如上图：A是B的父节点

孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点

如上图：B是A的孩子节点

兄弟节点：具有相同父节点的节点互称为兄弟节点；

如上图：B、C是兄弟节点

堂兄弟节点：双亲在同一层的节点互为堂兄弟

如上图：H、I互为堂兄弟节点

节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推

树的高度或深度：树中节点的最大层次

如上图：树的高度为4，因为PQ所处的层次为4。

特别的：当一棵树为空树，那么这个树的高度为0。

节点的祖先：从根到该节点所经分支上的所有节点

如上图：A是所有节点的祖先，F是KLM的祖先。

子孙：以某节点为根的子树中任一节点都称为该节点的子孙。

如上图：所有节点都是A的子孙，HIJPQ都是D的子孙。

森林：由m（m>0）棵互不相交的树的集合称为森林

树的实现

由于一般的树的实现实际价值并不大，而后续讲解的二叉树才是重点，此处只讲解现存的几种实现结构，并不一一实现接口。

方案一：

为每个节点创建一个结构体，结构体内存储当前节点的值，并存入指向每个孩子的指针。

struct TreeNode
{
  int val;
  struct TreeNode* child1;
  struct TreeNode* child2;
  struct TreeNode* child3;
  struct TreeNode* child4;
  ......
};

这种方法看似完美，但是有一个问题就是，每个节点的孩子个数是不确定的，而结构体一旦定义，就无法改变其成员的个数。所以这就会导致当一个节点孩子过多时，这个结构体可能存不下所有孩子的指针。而当一个节点孩子太少时，这个结构体又会产生指针的浪费。

方案二：

在结构体末尾存一个数组，数组的元素是结构体指针：

#define N 6;
struct TreeNode
{
  int val;
  struct TreeNode* childArr[N];
};

这个方法和刚刚有着相似的问题，就是说我们规定N为6后，这个树的度就不能超过6了。而且当节点没有六个孩子，数组开辟的空间也就浪费了。

方案三：

我们刚刚的数组方案，最大问题就是不能调整元素个数，限制了树的度为6。在此我们可以用一个顺序表或者链表作为这个容纳孩子的指针的容器，这样一来就可以保证：不论有多少个孩子，顺序表和链表都具有自己扩容的特性，都能把指向孩子的指针存下来。

struct TreeNode
{
  int val;
  SeqList childSL;
};

这种方法已经十分不错了，但是在C语言中，顺序表与链表是需要手撕的，c++倒是可以直接用。所以这种方式其实不太适合C语言。

方案四：

最后一种方式叫做左孩子右兄弟结构，即每个结构体都只有固定的两个指针，一个指针指向自己最左侧的孩子，而另一个指针，指向自己的兄弟。

结构如下：

struct TreeNode
{
  int val;
  struct TreeNode* leftchild;
  struct TreeNode* rightbrother;
};

比如下面左侧的树结构，使用这个结构实现就是：

二叉树

二叉树的定义

二叉树是树的度最大为2的树。

二叉树其实并不是所有节点的度一定为2，只要小于等于二即可，比如上图左侧的树中，这颗树的度为2，而D节点的度为1，但是它依然是一颗二叉树。

此外，二叉树也不是树的度一定为2，而是小于等于2即可，比如上图右侧的树中，每个节点的度为1，但是它依然是一颗二叉树。

特殊的二叉树

满二叉树

定义：

满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。

此处也可以理解为，只要一颗二叉树，最后一层的节点度都为0，而除了最后一层，度都为2，那么这棵树就是满二叉树。

满二叉树十分规律，其高度与节点数也有着固定的关系。

假设某个满二叉树的高度为H，节点数为N：

我们观察上图的二叉树，由于每个节点的度都为2，即每个节点都有两个孩子，所以下一层的节点个数是上一层的两倍。这样一来，我们就可以发现，满二叉树的每一层的节点个数是一个以1为首项，以2为公比的等比数列。而这个等比数列的项数就是节点的高度H。所以求H与N的关系，本质上就是求这个等比数列的前H项和。

由带入公式可得： N = 2^H - 1

反过来：H = log (N+1)

这就是我们的已知节点求高度，和已知高度求节点的公式了。

完全二叉树

完全二叉树是指：前H-1层是满二叉树，最后一层可以不满，但是从左到右是连续的。

当然，最后一层只要求是连续的，所以最后一层也可以是满的，这样一来就是一个完全二叉树了，所以满二叉树是特殊的完全二叉树。

接下来我举几个反例帮助大家理解：

在左侧图中：由于前H-1层不是满的，所以不是完全二叉树。

在中间图中：最后一层不是连续的，所以不是完全二叉树。

在右侧图中：由于先使用了右侧的孩子，而左侧孩子是空的，所以不连续，不是完全二叉树。

完全二叉树，高度与节点数的关系：

对于一个高度为H的完全二叉树，其节点范围其实就是：第H层有一个节点，到第H层的节点是满的。

如下图中的所有情况都是高度为4的完全二叉树：

那么完全二叉树的高度H与节点数N的关系就呼之欲出了：

最少节点数目： N >= 2^H-1 即H-1层的满二叉树节点数+1

最多节点数目： N <= 2^H - 1 即H层的满二叉树节点数

二叉树的接口实现

结构分析

我们之前分析过树的实现方法，其中有一种方法：一个成员存值，每个孩子用一个指针成员来储存。

这种方法的缺点是，孩子指针数目确定后就无法更改了，导致树的度上限是确定的。

但是我们的二叉树刚好就是一个度最大为2的树，所以其实非常适合这种方法。

结构如下：

typedef char BTDataType;
typedef struct BinaryTreeNode
{
  BTDataType data;
  struct BinaryTreeNode* left;
  struct BinaryTreeNode* right;
}BTNode;

在此我们将这棵树的存储内容定义为char类型，此后需要存储其他的数据类型，只需要在typedef中修改即可。

比如将下图左侧的树转化为右侧结构示意图：

深度优先遍历

所谓深度优先遍历，其实就是优先到达层次比较深的地方，并且输出途径的节点所存的值。

比如此图中，我们为了到达更深的地方，我们访问完A节点后，就去访问D节点，再访问B节点。在这个过程中，虽然E节点里根节点比较近，但是我们访问完D后依然选择访问B节点，以达到往深处遍历的效果。

深度优先遍历分为三种，分别是前序遍历，中序遍历，后序遍历。

这三种遍历是如何来的？

我们设想：现在我们访问到了A节点，我是要先输出A节点本身的值，还是输出A节点左侧子树的值，还是A节点右侧子树值？这里一共有三种情况：优先输出A，访问完左子树再输出A，访问完左右子树再输出A。

在这个顺序中，A节点的次序分别位于前中后，也就有了前序中序后序三种遍历。

请注意此处的用词：“访问”与“输出”，后序我会用例子来讲解这两个用词的区别。

前序遍历

前序遍历，就是在访问到一个节点时，先输出这个节点的值，再访问左子树，最后访问右子树。

我们以这张图为示例，来展示前序遍历的过程：

1.从根节点A出发，访问A节点，此时先输出A，再访问左子树D。

2.访问到左子树D节点后，此时先输出D，再访问左子树B。

3.访问到左子树B节点后，此时先输出B，再访问左子树，但是此时左子树是不存在的（B的左子树访问完毕），访问B的右子树，B的右子树也不存在（B的右子树访问完毕）。

4.当B节点的左右子树都访问完毕，那么B也就访问完毕了。

5.而B是D的左子树，此时D的左子树访问完毕，访问D的右子树，由于D的右子树不存在（D的右子树访问完毕）。

6.当D节点的左右子树都访问完毕，D就访问完毕了，此时也就是A的左子树访问完毕，访问A的右子树E。

7.访问到到左子树E节点后，此时先输出E，然后访问E的左子树F。

.8.访问到到左子树F节点后，此时先输出F，再访问F的左子树，但是此时左子树是不存在的（F的左子树访问完毕），访问F的右子树，F的右子树也不存在（F的右子树访问完毕）。

9.当F节点的左右子树都访问完毕，那么F也就访问完毕了。

10.而F是E的左子树，此时E的左子树访问完毕，访问E的右子树G。

11.访问到右子树G节点后，此时先输出G，再访问左子树，但是此时左子树是不存在的（G的左子树访问完毕），访问G的右子树，G的右子树也不存在（G的右子树访问完毕）。

12.当G节点的左右子树都访问完毕，那么G也就访问完毕了。

13.E的左右子树FG都访问完毕，此时E就访问完毕了。

14.A的左右子树DE都访问完毕，此时A就访问完毕了。

前序遍历结束，结果为：ADBEFG

在这个过程中，我们不断地往深处递进，当一个节点访问完毕，就回归到上一级节点。这个过程就叫做递归，即递进与回归。

想要用函数来实现这个过程，就要使用函数中的递归，不停的调用下一级函数，遇到合适的情况就返回。

想要利用好递归，就需要考虑好，什么时候递进？递进到哪里去？什么时候回归？

前序遍历中，只要当前的节点不是空指针，那么就需要递进到左子树，右子树。

而当当前节点是空指针，我们就需要返回，再往下递进也访问不到值了。

所以当指针为空时，我们的回归语句需要放在递进语句的前面。

而在递进时，先递进左子树，再递进右子树。

代码如下：

// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{
  if (root == NULL)//回归
    return 0;
  printf("%c ", root->data);//输出
  BinaryTreePrevOrder(root->left);//递进
  BinaryTreePrevOrder(root->right);//递进
}//回归

上图中的if (root == NULL)就是一个回归的条件，当前为空，就说明递归到底了，此时不能执行递归，要直接返回，不让后面的语句触发。

而当前的节点不是空，就说明还需要递归，在访问左子树与右子树之前，先输出当前节点的值： printf("%c ", root->data);再递归左子树 BinaryTreePrevOrder(root->left);最后递归右子树 BinaryTreePrevOrder(root->right);

当一个非空节点访问完左右子树，这个节点也就访问完毕了，此时函数会自动回归。

中序遍历

有了前序遍历，后面两种遍历就好理解了。

中序遍历其实就是先访问左子树，再输出当前节点，最后访问右子树。

// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
  if (root == NULL)
    return 0;
  BinaryTreeInOrder(root->left);//访问左子树
  printf("%c ", root->data);//输出节点
  BinaryTreeInOrder(root->right);//访问右子树
}

此树的中序遍历结果为：BDAFEG

后序遍历

同理的，先访问左右子树，最后输出节点：

// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
  if (root == NULL)
    return;
  BinaryTreePostOrder(root->left);//访问左子树
  BinaryTreePostOrder(root->right);//访问右子树
  printf("%c ", root->data);//输出节点
}

此树的后序遍历结果为：BDFGEA

通过深度优先遍历还原二叉树（非接口）

已知某二叉树的前序遍历序列为ABEDC，中序遍历序列为BDEAC，请还原这颗二叉树

其实我们在拿到一颗二叉树的中序遍历 + 前序遍历与后序遍历之一，就可以非常轻易的还原一颗二叉树。

我们观察一下上面推出的三种遍历结果：

前序遍历：ADBEFG，中序遍历：BDAFEG，后序遍历：BDFGEA。

可以发现，前序遍历中，根节点一定在首位；后序遍历中，根节点一定在末尾。

而中序遍历，刚好根节点的左侧是左子树的所有节点，右侧是右子树的所有节点。

这样一来，我们就可以通过前序或者后序来确定根节点确定根节点后，通过中序确定左右子树。

我对一开始的题目进行一次分析：

前序：ABEDC 中序：BDEAC

首先通过前序确定根，前序遍历的根处于首位：那么根就是A。

然后再在中序中确定左右子树，中序遍历中左子树在根的左边，右子树在根的右边：那么左子树的中序是：BDE 右子树的中序是：C

那么我们就得到了这个结构：

接下来我们对BDE讨论：其中序为BDE，由前序遍历ABEDC可知BDE的前序为BED；

首先通过前序确定根，前序遍历的根处于首位：那么根就是B。

然后再在中序中确定左右子树，中序遍历中左子树在根的左边，右子树在根的右边：

由于B左边没有序列了，说明B的左子树是空树，右子树的中序是：DE

我们就还原到了这个结构：

再分析DE这棵树：其中序遍历为DE，通过前序遍历BED可知DE的前序遍历是ED；

首先通过前序确定根，前序遍历的根处于首位：那么根就是E。

然后再在中序中确定左右子树，中序遍历中左子树在根的左边，右子树在根的右边：

由于E左边没有序列了，说明E的左子树是空树，右子树的中序是：D

这样我们就还原出了树的结构：

所以利用前序中序后序遍历还原一颗树的过程，其实就是不断地寻找根节点，再去区分出左右子树的过程。

广度优先遍历

所谓广度优先遍历，其实就是优先遍历完每一层，再去到下一层遍历。

层序遍历

广度优先遍历，主要是指层序遍历，每一层从左到右依次输出。

在深度优先遍历中，我们通过递归来进到下一层的节点，可是在层序遍历中，我们要怎么去到兄弟或者是堂兄弟节点呢？

比如说，我们输出了D节点的数值之后，怎么得到E节点的数值呢？

我们的D节点与E节点的指针都存在A节点中，想要访问DE，就需要通过A，所以我们在访问A节点的时候，就需要想办法把DE两个节点的指针按照顺序存下来，保证左子树D先输出，右子树E后输出。这样一来，我们就可以得到前三个节点的层序遍历ADE。

那么我们又要怎么保证BCFG的输出？

BCFG节点的指针存在DE中，想要访问BCFG，就要想办法在访问DE节点时，按照指定顺序把BCFG的节点指针存下来。

通过以上两轮分析，我们可以发现，层序遍历的基本思路就是，通过上一层的节点，把下一层的指针存下来，再按照指定顺序输出。

既然要按照指定顺序，我们不妨使用队列结构来实现，队列的特点是先进先出，我们只要保证存入每一层节点的时候，左边的节点先进，右边的节点后进，我们的输出结果就是对的。

要注意，由于我们访问节点时，不仅仅要得到节点的值，还需要得到其左孩子和右孩子的指针，所以此处我们要利用队列存储结构体指针。

先展示代码，再进行接下来的分析：

此处使用了队列Queue结构，由于C语言并不自带队列结构，此处需要手撕，可以看这条博客：[数据结构与算法：队列]

// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
  Queue q;
  QueueInit(&q);//创建并初始化一个队列
  if (root)
    QueuePush(&q, root);//将根节点入队列
  while (!QueueEmpty(&q))//队列不为空，就说明还没有到最后一层
  {
    BTNode* front = QueueFront(&q);//取出当前队列的第一个元素
    QueuePop(&q);//将第一个元素出队列，避免影响后面的元素出队列
    printf("%c ", front->data);//输出当前节点的值
    if (front->left)//如果有左孩子，将其左孩子入队列
      QueuePush(&q, front->left);
    if (front->right)//如果有右孩子，将其右孩子入队列
      QueuePush(&q, front->right);
  }
  QueueDestroy(&q);//销毁队列
}

着重看while循环内部的逻辑：

我们利用front来接受当前队列的第一个元素，并printf输出它的数值，在输出数值之后，先把左孩子入队列，再把右孩子入队列，这样就可以保证左孩子比右孩子先输出，这是符合层序遍历的要求的。

我们再利用这张图来分析一下：

一开始将整棵树的根节点A入队列，此时队列的元素就是A

然后进入循环，先输出A，然后把A的左孩子D入队列，再把A的右孩子E入队列，此时队列元素为DE；（此时第一层输出完毕）

第二次进入循环，先输出队列第一个元素D，再存入D的左孩子B，右孩子C，此时队列元素为EBC；

第三次进入循环，先输出队列第一个元素E，再存入E的左孩子F，右孩子G，此时队列元素为BCFG；（此时第二层输出完毕）

第四次进入循环，先输出队列第一个元素B，再存入B的左孩子H，右孩子I，此时队列元素为CFGHI；

第五次进入循环，先输出队列第一个元素C，再存入C的左孩子J，右孩子K，此时队列元素为FGHIJK；

第六次进入循环，先输出队列第一个元素F，再存入F的左孩子L，右孩子M，此时队列元素为GHIJKLM；

第七次进入循环，先输出队列第一个元素G，再存入G的左孩子N，右孩子G，此时队列元素为HIJKLMNG；（此时第三层输出完毕）

我们观察黄色标注的字符，从上往下，就是层序遍历的输出。

当第一层A输出完毕，我们队列中刚好是第二层的所有元素DE；

当第二层DE输出完毕，我们队列中刚好是第三层的所有元素BCFG；

当第三层BCFG输出完毕，我们队列中刚好是第四层的所有元素HIJKLMNG；

每当上一层输出完，就把下一层的节点全部存入，既能满足层序遍历的要求，也解决了访问困难的问题。

求二叉树的节点个数

求二叉树的节点个数，是需要遍历这个二叉树的，当遍历到空指针，就不增加节点个数，遍历到非空指针，就说明当前这个节点是存在的，增加一个节点个数。

想要遍历这棵树，就需要递归，利用递归的思想，先问：何时递归？递归到哪里去？何时结束递归？

何时递归：当前节点为非空指针，说明这是一个存在的节点，需要继续递归。

递归到哪里去：由于我们下一层的指针都存储在上一层的节点中，所以我们在递归时，要对该节点的左孩子和右孩子都进行递归。

何时结束递归：当前节点为空指针，说明这是一个不存在的节点，开始回归。

下一个问题，我们要如何记录当前的节点数目？

由于函数在调用结束时，会销毁其内部创建的所有数据，并且还原所有对非指针变量的修改。

此时我们可以利用递归返回值会回到上一级递归的特性，每次都返回其左子树的节点个数+右子树节点个数+自己

那么就是：return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;

而当遇到空指针时，返回0，代表这个节点不存在，不计入个数。

代码如下：

// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
  if (root == NULL)//结束递归条件
    return 0;
  return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;//递归到左右子树
}

博客制作不易，还请留下一个免费的赞！

有问题欢迎指出，博主非常喜欢讨论问题！