二叉树的设计与实现(树的开篇)

树与森林

树的介绍

树是一种全新的数据结构，它就像一棵树的树枝一样，不断延伸。

一棵树就像下面这样连接：


可以看到，现在一个结点下面可能会连接多个节点，并不断延伸，就像树枝一样，每个结点都有可能是一个分支点，延伸出多个分支，从位于最上方的结点开始不断向下，而这种数据结构，我们就称为树（Tree)，不能与其他分支上的结点相交

• 我们一般称位于最上方的结点为树的根结点（Root）因为整棵树正是从这里开始延伸出去的。
• 每个结点连接的子结点数目（分支的数目），我们称为结点的度（Degree），而各个结点度的最大值称为树的度。
• 每个结点延伸下去的下一个结点都可以称为一棵子树（SubTree）比如结点B及其之后延伸的所有分支合在一起，就是一棵A的子树。
• 每个结点的层次（Level）按照从上往下的顺序，树的根结点为1，每向下一层+1，比如G的层次就是3，整棵树中所有结点的最大层次，就是这颗树的深度（Depth），比如上面这棵树的深度为4，因为最大层次就是4。
• 与当前结点直接向下相连的结点，我们称为子结点（Child），比如B、C、D结点，都是A的子结点，就像族谱中的父子关系一样，下一代一定是子女，相反的，那么A就是B、C、D的父结点（Parent），也可以叫双亲结点。
• 如果某个节点没有任何的子结点（结点度为0时）那么我们称这个结点为叶子结点（因为已经到头了，后面没有分支了，这时就该树枝上长叶子了那样）比如K、L、F、G、M、I、J结点，都是叶子结点。
• 如果两个结点的父结点是同一个，那么称这两个节点为兄弟结点（Sibling）比如B和C就是兄弟结点，因为都是A的孩子。
• 从根结点开始一直到某个结点的整条路径的所有结点，都是这个结点的祖先结点（Ancestor）比如L的祖先结点就是A、B、E

森林的介绍

森林其实很好理解，一片森林肯定是是由很多棵树构成的，比如下面的三棵树：



它们共同组成了一片森林，因此，m（m≥0）棵树的集合我们称为森林（Forest）

二叉树

二叉树的介绍

二叉树（Binary Tree）它是一种特殊的树，它的度最大只能为2

并且二叉树任何结点的子树是有左右之分的，不能颠倒顺序，比如A结点左边的子树，称为左子树，右边的子树称为右子树。
二叉树有5种基本形态，分别是：

当然，对于某些二叉树我们有特别的称呼，比如，在一棵二叉树中，所有分支结点都存在左子树和右子树，且叶子结点都在同一层：

这样的二叉树我们称为满二叉树，可以看到整棵树都是很饱满的，没有出现任何度为1的结点，当然，还有一种特殊情况：

可以看到只有最后一层有空缺，并且所有的叶子结点是按照从左往右的顺序排列的，这样的二叉树我们一般称其为完全二叉树，所以，一棵满二叉树，一定是一棵完全二叉树。

并且得明确完全二叉树的核心定义：

• 除了最后一层外，其他每一层的节点数都必须是满的。
• 最后一层的所有节点必须连续、靠左排列，不能出现中间有空缺的情况。

树和森林的转换

我们以下面的这棵树为例：

有一种简单的方法，我们可以直接将所有的兄弟结点连起来（橙色横线）：

接着擦掉所有结点除了最左边结点以外的连线：

所有的黑色连线偏向左边，橙色连线偏向右边：

无论一棵树长成啥样，转换为二叉树后，根节点一定没有右子树。

二叉树的性质

由于二叉树结构特殊，我们可以总结出以下的五个性质：

• 性质一： 对于一棵二叉树，第i层的最大结点数量为 $2^{i−1}$ 个，比如二叉树的第一层只有一个根结点，也就是 $2^0=1$ ，而二叉树的第三层可以有 $2^2=4$ 个结点。

• 性质二： 对于一棵深度为k的二叉树，可以具有的最大结点数量为：

  $$n = 2^0 + 2^1 + 2^2 + \dots + 2^{k-1} $$

  我们发现，实际上每一层的结点数量，组成了一个等比数列，公比q为2，结合等比数列求和公式，我们可以将其简化为：

  $$S_n = \frac{a_1 \times (1 - q^n)}{1 - q} = \frac{1 \times (1 - 2^k)}{1 - 2} = -(1 - 2^k) = 2^k - 1 $$

  所以一棵深度为k的二叉树最大结点数量为$n = 2^k - 1$，顺便得出，结点的边数为 $E=n−1$。

• 性质三： 假设一棵二叉树中度为0、1、2的结点数量分别为$n_0$、$n_1$、$n_2$​，由于一棵二叉树中只有这三种类型的结点，那么可以直接得到结点总数：

  $$n = n_0 + n_1 + n_2 $$

  我们不妨换一个思路，我们从二叉树的边数上考虑，因为每个结点有且仅有一条边与其父结点相连，那么边数之和就可以表示为：

  $$E = n_1 + 2n_2 $$

  度为1的结点有一条边，度为2的结点有两条边，度为0的结点没有，加在一起就是整棵二叉树的边数之和，结合我们在性质二中推导的结果，可以得到另一种计算结点总数的方式：

  $$E = n - 1 = n_1 + 2n_2 $$

  $$n = n_1 + 2n_2 + 1 $$

  再结合我们第一个公式：

  $$n = n_0 + n_1 + n_2 = n_1 + 2n_2 + 1 $$

  综上，对于任何一棵二叉树，如果其叶子结点个数为 n0n0​ ，度为2的结点个数为 n2n2​ ，那么两者满足以下公式：

  $$n_0 = n_2 + 1 $$

  （性质三的推导过程比较复杂，如果觉得麻烦推荐直接记忆）

• 性质四： 完全二叉树除了最后一层有空缺外，其他层数都是饱满的，假设这棵二叉树为满二叉树，那么根据我们前面得到的性质，假设层数为k，那么结点数量为：$n = 2^k - 1$ ，根据完全二叉树的性质，最后一层可以满可以不满，那么一棵完全二叉树结点数n满足：

  $$2^{k-1} - 1 < n \le 2^k - 1 $$

  因为n肯定是一个整数，那么可以写为：

  $$2^{k-1} \le n \le 2^k - 1 $$

  现在我们只看左边的不等式，我们对不等式两边同时取对数，得到：

  $$k - 1 \le \log_2 n $$

  综上所述，一棵具有n个结点的完全二叉树深度为 $k = \lfloor \log_2 n \rfloor + 1$ 。

  （性质四的推导过程比较复杂，如果觉得麻烦推荐直接记忆）

• 性质五： 一颗有n个结点的完全二叉树，由性质四得到深度为 $k = \lfloor \log_2 n \rfloor + 1$ 现在对于任意一个结点i，结点的顺序为从上往下，从左往右：

  • 对于一个拥有左右孩子的结点来说，其左孩子为2i，右孩子为2i + 1。
  • 如果i = 1，那么此结点为二叉树的根结点，如果i > 1，那么其父结点就是$\lfloor i/2 \rfloor$，比如第3个结点的父结点为第1个节点，也就是根结点。
  • 如果2i > n，则结点i没有左孩子，比如下面图中的二叉树，n为5，假设此时i = 3，那么2i = 6 > n = 5 说明第三个结点没有左子树。
  • 如果2i + 1 > n，则结点i没有右孩子。
    

• 性质六： 给定结点数量，可以构造多少条不同的二叉树？
  
  卡特兰数公式:

  $$C_n = \frac{1}{n+1}C_{2n}^n = \frac{1}{n+1} \times \frac{(2n)!}{n! \times (2n-n)!} = \frac{(2n)!}{n! \times (n+1)!} $$

二叉树的构建

二叉树的存储形式也可以使用我们前面的两种方式，一种是使用数组进行存放，还有一种就是使用链式结构，只不过之前链式结构需要强化一下才可以表示为二叉树。

我们在前面使用链表的时候，每个结点不仅存放对应的数据，而且会存放一个指向下一个结点的指针：

而二叉树也可以使用这样的链式存储形式，只不过现在一个结点需要存放一个指向左子树的指针和一个指向右子树的指针了：

通过这种方式，我们就可以通过连接不同的结点形成一颗二叉树了，这样也更便于我们去理解它，我们首先定义一个结构体：

typedef char E;

struct TreeNode {
    E element;    //存放元素
    struct TreeNode * left;   //指向左子树的指针
    struct TreeNode * right;   //指向右子树的指针
};

typedef struct TreeNode * Node;

比如我们现在想要构建一颗像这样的二叉树：

首先我们需要创建好这几个结点：

int main(){
    Node a = malloc(sizeof(struct TreeNode));   //依次创建好这五个结点
    Node b = malloc(sizeof(struct TreeNode));
    Node c = malloc(sizeof(struct TreeNode));
    Node d = malloc(sizeof(struct TreeNode));
    Node e = malloc(sizeof(struct TreeNode));
  	a->element = 'A';
    b->element = 'B';
    c->element = 'C';
    d->element = 'D';
    e->element = 'E';
}

接着我们从最上面开始，挨着进行连接，首先是A这个结点：

int main(){
    ...

    a->left = b;   //A的左孩子是B
    a->right = c;   //A的右孩子是C
}

然后是B这个结点：

int main(){
    ...
      
    b->left = d;   //B的左孩子是D
    b->right = e;   //B的右孩子是E
  
  	//别忘了把其他的结点改为NULL
  	...
}

这样的话，我们就成功构建好了这棵二叉树。

二叉树的遍历

前序遍历

前面我们通过使用链式结构，成功构建出了一棵二叉树，接着我们来看看如何遍历一棵二叉树，也就是说我们想要访问二叉树的每一个结点，由于树形结构特殊，遍历顺序并不唯一，所以一共有四种访问方式：前序遍历、中序遍历、后序遍历、层序遍历。 不同的访问方式输出都结点顺序也不同。

首先我们来看最简单的前序遍历：

前序遍历是一种勇往直前的态度，走到哪就遍历到那里，先走左边再走右边，比如上面的这个图，首先会从根节点开始：

从A开始，先左后右，那么下一个就是B，然后继续走左边，是D，现在ABD走完之后，B的左边结束了，那么就要开始B的右边了，所以下一个是E，E结束之后，现在A的左子树已经全部遍历完成了，然后就是右边，接着就是C，C没有左子树了，那么只能走右边了，最后输出F，所以上面这个二叉树的前序遍历结果为：ABDECF

• 打印根节点
• 前序遍历左子树
• 前序遍历右子树
  接着我们来通过代码实现一下，首先先把咱们这棵二叉树组装好：

int main(){
    Node a = malloc(sizeof(struct TreeNode));
    Node b = malloc(sizeof(struct TreeNode));
    Node c = malloc(sizeof(struct TreeNode));
    Node d = malloc(sizeof(struct TreeNode));
    Node e = malloc(sizeof(struct TreeNode));
    Node f = malloc(sizeof(struct TreeNode));
    a->element = 'A';
    b->element = 'B';
    c->element = 'C';
    d->element = 'D';
    e->element = 'E';
    f->element = 'F';

    a->left = b;
    a->right = c;
    b->left = d;
    b->right = e;
    c->right = f;
    c->left = NULL;
    d->left = e->right = NULL;
    e->left = e->right = NULL;
    f->left = f->right = NULL;
}

组装好之后，我们来实现一下前序遍历的函数：

void preOrder(Node root){   //传入的是二叉树的根结点
    
}

那么现在我们拿到根结点之后该怎么去写呢？既然是走到哪里打印到哪里，那么我们就先打印一下当前结点的值：

void preOrder(Node root){
    printf("%c", root->element);   //不多bb先打印再说
}

打印完成之后，我们就按照先左后右的规则往后遍历下一个结点，这里我们就直接使用递归来完成：

void preOrder(Node root){
    printf("%c", root->element);
    preOrder(root->left);   //将左孩子结点递归交给下一级
    preOrder(root->right);  //等上面的一系列向左递归结束后，再以同样的方式去到右边
}

不过还没，我们的递归肯定是需要一个终止条件的，不可能无限地进行下去，如果已经走到底了，那么就不能再往下走了，所以：

void preOrder(Node root){
    if(root == NULL) return;   //如果走到NULL了，那就表示已经到头了，直接返回
    printf("%c", root->element);
    preOrder(root->left);
    preOrder(root->right);
}

中序遍历

那么前序遍历我们了解完了，接着就是中序遍历了，中序遍历在顺序上与前序遍历不同，前序遍历是走到哪就打印到哪，而中序遍历需要先完成整个左子树的遍历后再打印，然后再遍历其右子树。
我们还是以上面的二叉树为例：

首先需要先不断遍历左子树，走到最底部，但是沿途并不进行打印，而是到底之后，再打印，所以第一个打印的是D，接着由于没有右子树，所以我们回到B，此时再打印B，然后再去看B的右结点E，由于没有左子树和右子树了，所以直接打印E，左边遍历完成，接着回到A，打印A，然后对A的右子树重复上述操作。所以说遍历的基本规则还是一样的，只是打印值的时机发生了改变。

• 中序遍历左子树
• 打印结点
• 中序遍历右子树
  所以这棵二叉树的中序遍历结果为：DBEACF
  
  那么怎么才能将打印调整到左子树全部遍历结束之后呢？其实很简单：

void inOrder(Node root){
    if(root == NULL) return;
    inOrder(root->left);  //先完成全部左子树的遍历
    printf("%c", root->element);   //等待左子树遍历完成之后再打印
    inOrder(root->right);   //然后就是对右子树进行遍历
}

后序遍历

接着我们来看一下后序遍历，后序遍历继续将打印的时机延后，需要等待左右子树全部遍历完成，才会去进行打印。

首先还是一路向左，到达结点D，此时结点D没有左子树了，接着看结点D还有没有右子树，发现也没有，左右子树全部遍历完成，那么此时再打印D，同样的，D完事之后就回到B了，此时接着看B的右子树，发现有结点E，重复上述操作，E也打印出来了，接着B的左右子树全部OK，那么再打印B，接着A的左子树就完事了，现在回到A，看到A的右子树，继续重复上述步骤，当A的右子树也遍历结束后，最后再打印A结点。

• 后序遍历左子树
• 后序遍历右子树
• 打印结点
  所以最后的遍历顺序为：DEBFCA
  
  所以，按照这个思路，我们来编写一下后序遍历：

void postOrder(Node root){
    if(root == NULL) return;
    postOrder(root->left);
    postOrder(root->right);
    printf("%c", root->element);   //时机延迟到最后
}

层序遍历

最后我们来看层序遍历，实际上这种遍历方式是我们人脑最容易理解的，它是按照每一层在进行遍历：

层序遍历实际上就是按照从上往下每一层，从左到右的顺序打印每个结点，比如上面的这棵二叉树，那么层序遍历的结果就是：ABCDEF，像这样一层一层的挨个输出。

我们可以利用队列来实现层序遍历，首先将根结点存入队列中，接着循环执行以下步骤：

• 进行出队操作，得到一个结点，并打印结点的值。
• 将此结点的左右孩子结点依次入队。
  不断重复以上步骤，直到队列为空。