算法快学笔记（六）：揭开“树”的面纱

蔚落 2022-04-10 13:53 161阅读 0赞

算法世界中，树结构是较大的一块知识体系，从二叉树，到B树，到红黑树，赫夫曼树等耳熟能详的算法都可以归纳到“树”这一体系。本文先只对树以及二叉树的基本概念进行阐述，更多算法的讲解请参阅后续博文。

# 1. 树 #

树是一种数据结构，它是由n（n>=1）个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树。一颗简单的树如下：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70]

数的定义很简单，但是有两点需要强调：

1.  N>0时：只能有一个根节点，不能有多个根节点
2.  子树的个数没有限制，但是子树之间一定不能相交,下面的数就是一颗不合法的树：  
    ![在这里插入图片描述][20190111113226450.jpg]

## 1.1 树的相关名词 ##

*  节点的度：一个节点含有的子树的个数称为该节点的度；
 *  叶节点或终端节点：度为0的节点称为叶节点；
 *  非终端节点或分支节点：度不为0的节点；
 *  双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
 *  孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；
 *  兄弟节点：具有相同父节点的节点互称为兄弟节点；
 *  树的度：一棵树中，最大的节点的度称为树的度；
 *  节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
 *  树的高度或深度：树中节点的最大层次；
 *  堂兄弟节点：双亲在同一层的节点互为堂兄弟；
 *  节点的祖先：从根到该节点所经分支上的所有节点；
 *  子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
 *  森林：由m（m>=0）棵互不相交的树的集合称为森林；

## 1.2 树的存储结构 ##

通过结合顺序以及链式存储，可以实现对树结构的存储。主要有三种存储方式：（1）双亲表示法 （2）双亲孩子表示法（3）孩子兄弟表示法

### 1.2.1 双亲表示法 ###

对于双亲表示法，除了需要知道节点本身的data信息，还需要着重关注该节点的父节是谁，最后可以根据需要来调整存储的结构。

例如，要存储下面的树：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 1]

1.  如果只关心parent,则可以采用下面的结构进行顺序存储  
    ![在这里插入图片描述][20190111113251772.jpg]

这样的存储结构，可以很容易的根据parent列的值找到对应的parent(时间复杂度为O(1)),但想要知道某个节点的有哪些子节点，则需要遍历整个树

1.  在存了parent的信息后，还可以增加该节点的长子信息（该节点最左边的子节点）  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 2]
2.  如果使用的场景不关心长子的信息，而是关心又兄弟的话，则可以采用下面的存储结构  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 3]
3.  从前面几个例子可以看出，除了parent是必须的，其他的信息如果你需要都可以对结构进行扩展。

### 1.2.2 双亲孩子表示法 ###

对于基本的双亲表示法，想要找到parent很容易，但是如果有多个子节点，想要找到所有的子节点就不是很方便，如何才能做到了？看看下面的顺序+链表的存储结构：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 4]

上面的结构有以下优点：

*  很容易找到parent节点
 *  很容易找到所有的子节点

### 1.2.3 孩子兄弟表示法 ###

通过名字可以看出，该表示法关心的是孩子和兄弟，具体是哪个孩子哪个兄弟了？

*  孩子：最左侧的孩子
 *  兄弟：该节点右边的兄弟

节点的结构为：节点本身|最左侧孩子节点|右边的兄弟，最终表示的结果如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 5]

该结构由于没存parent的信息，因为查找某个节点的parent的比较麻烦，但是可以将该结构增加一个parent信息。

如果仔细观察该结构的节点，会发现任何一个节点现在最多只有两个节点了，一不小心居然将一颗复杂的树转化成了二叉树。二叉树是啥？往后看！

# 2. 二叉树 #

如果一棵树每个结点最多有两个子树，那么这课树就是二叉树。

1.  每个节点最多有两个子树
2.  树的结点无左、右之分，而二叉树的结点有左、右之分
3.  即使只有一颗子树，也要区分左右

## 2.1 二叉树的性质 ##

1.  在非空二叉树中，第i层的结点总数不超过2^(i-1)；
2.  深度为h的二叉树最多有2^h-1 个结点(h>=1)，最少有h个结点；
3.  对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；
4.  具有n个结点的完全二叉树的深度为|Log\_2^N|+1 （注：\[ \]表示向下取整）
5.  对于一颗有n个节点的完全二叉树的节点按照层次编号，对于任一节点i
    
    1.  如果i=1,则节点i是根，如果i>1,则父节点是i/2
    2.  如果2i>n,则节点无左孩子，否则其左孩子是节点2i
    3.  如果2i+1>n,则节点i无右孩子，否则其右孩子是2i+1

## 2.2 二叉树的分类 ##

1.  满二叉树：除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。
2.  完全二叉树：若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。  
    完全二叉树的例子如下：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 6]
3.  平衡二叉树：平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
4.  斜树：所有节点只有左节点或是右节点的树。

## 2.3 二叉树的存储 ##

二叉树的存储方式可以用前面介绍的树的存储方式，但由于二叉树每个节点最多有两个孩子，可以通过链表的方式来存储二叉树。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 7]

如有需要，可以在结构体中放一个parent的指针。

## 2.4 二叉树的遍历 ##

根据不同的遍历顺序，二叉树的遍历方式可以分为以下几种：

1.  先序遍历：根->左子树->右子树（先序）  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 8]
2.  中序遍历：左子树->根->右子树（中序）  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 9]
3.  后序遍历：左子树->右子树->根（后序）  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 10]
4.  层次遍历：一层一层的遍历

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 11]

# 3. 树,森林，二叉树的转换 #

## 3.1 树转为二叉树 ##

前文提到的孩子兄弟表示法是一种方式，还可以通过如下方式进行转换

1.  在所有兄弟之间加一条连线
2.  只保留每个节点与第一个子节点的连线，与其他子节点的连线都删掉
3.  以根节点为中心点，将树顺时针旋转一定的角度，使层次分明。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 12]

## 3.2 森林转为二叉树 ##

森林转为二叉树的步骤如下：

1.  把每颗树转为二叉树
2.  第一颗树不懂，从第二颗开始，依次把后一颗二叉树的根节点左右前一颗二叉树的右孩子。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 13]

## 3.3 二叉树转为树 ##

是树转换为二叉树的逆过程。

1.加线。若某结点X的左孩子结点存在，则将这个左孩子的右孩子结点、右孩子的右孩子结点、右孩子的右孩子的右孩子结点…，都作为结点X的孩子。将结点X与这些右孩子结点用线连接起来。

2.去线。删除原二叉树中所有结点与其右孩子结点的连线。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 14]

## 3.4 二叉树转为森林 ##

假如一棵二叉树的根节点有右孩子，则这棵二叉树能够转换为森林，否则将转换为一棵树。

1.从根节点开始，若右孩子存在，则把与右孩子结点的连线删除。再查看分离后的二叉树，若其根节点的右孩子存在，则连线删除…。直到所有这些根节点与右孩子的连线都删除为止。

2.将每棵分离后的二叉树转换为树。

如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 15]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70]: /images/20220328/f82e2b440dd34412a12f70cf91669ef2.png
[20190111113226450.jpg]: /images/20220328/97405e73878e478aa5226005faf87682.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 1]: /images/20220328/011ed590649749d3907300dca95624d4.png
[20190111113251772.jpg]: /images/20220328/522ab52c9c7949c39116ae1b8ea805a7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 2]: /images/20220328/57333af278fb488ea6b9fbbf1cf68611.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 3]: /images/20220328/9d71678eba244d888a4a6517deb6e6a7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 4]: /images/20220328/38a6437ad07241c58b271908f142457b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 5]: /images/20220328/33408b81870f442699969d160a701cee.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 6]: /images/20220328/44355a1b3fb84fa882087f042d640ffc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 7]: /images/20220328/877d81e994ac44b080a47dfaec9f0294.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 8]: /images/20220328/b8603891c6484bb2a49fa1923b0f642f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 9]: /images/20220328/d7fb0b976a654284a0731ab3e11d2ff7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 10]: /images/20220328/88748564ab3043b68c2167ae0b3ec001.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 11]: /images/20220328/db468eec005143d2ad739408a5c6a8ef.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 12]: /images/20220328/216073d88ae642a0bfadcae5f2bab52d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 13]: /images/20220328/61777ca6ae834db9b0e71b9f4490cf65.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 14]: /images/20220328/384326e354744434a5367e808a1ae528.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 15]: /images/20220328/96affd6614f049718dc0679b31f8b92a.png