第五章 树

5.1 树的基本概念

一、树的定义

树是n个节点的有限集合，当n=0的时候为空树。在一棵树中应该满足：

1. 有且仅有一个特定的称为根的节点
2. 当n>1的时候，其余几个点可分为m个互不相交的有限集合，其中每一个集合又是一棵树，这就是根的子树

显然，树的定义是递归的，树作为一种逻辑结构同时也是一种分层结构，具有两个特点：

1. 树的根节点没有钱去，除根节点之外的所有节点只有一个前驱
2. 树中所有节点可以有0个或者多个后继

二、基本术语

1. 根到节点K的路径上的节点称为K的祖先，而K是这些节点的子孙。路径上离K最近的节点E称为K的双亲，K是E的孩子。根节点是唯一没有双亲的节点，有相同双亲节点的称为兄弟。

2. 树中一个节点的孩子个数称之为该节点的度，树中节点的最大度数称为树的度。

3. 度大于0的节点称为分枝节点；度为0（也就是没有子女节点）的节点称之为叶子节点。

4. 节点的深度：自顶向下逐层累加

   节点的高度：自底向上逐层累加

   节点的层次从树根开始定义，根为第一层，以此类推。

   树的高度\深度就是树中节点的最大层数

5. 有序树和无序树

6. 路径和路径长度：路径是从根到该节点经过的节点集合，长度则是经过边的数量。树的路径长度是根到各个节点的路径长度的总和

7. 森林

三、树的性质

• 树中的结点数量等于所有节点度数之和加一
  因为每个节点都有一条和它父节点相连的边，但是根节点比较特殊，是没有父节点的，结点数-1等于度数
• 度为m的树中的第i层至多有$m^{i-1}$个结点
• 高度为h的m叉树最多有$\frac{m^h-1}{m-1}$个结点(知道高度和树的度求结点)
  推导：S=m^h-1+m^h-2+…+m+1，其实就是将各层最大结点数相加，这个结论记忆起来更符合逻辑
• 具有n个结点的m叉树的最小高度为$\lceil lo{g}_m(n(m-1)+1)\rceil$(知道树的度和节点数求最小高度)

5.2 二叉树的概念

一、二叉树的定义及其主要特征

定义
二叉树是另外一种树形结构，其特点是每个节点最多只有两颗子树，并且二叉树的子树有左右之分，并且有序，其次序不能任意颠倒。
二叉树和度为2的树的区别
度为二的树必须有三个结点，但是二叉树可以为空
度为二的树其结点是无序的，但是二叉树结点有序
特殊的二叉树

• 满二叉树
• 完全二叉树
  1.高度为h且有n个节点的二叉树当且仅当其每个节点都与高度为h的慢二叉树中编号1~n的结点一一对应时，称为完全二叉树
  2.如果$i\le \lfloor n/2\rfloor$，则节点为分支节点，否则为叶子结点
  3.叶子结点只会在层数最大的两层上出现
  
• 二叉排序树
• 平衡二叉树

二叉树的性质

1. 非空二叉树上的叶子结点等于度为2的节点数+1
2. 非空二叉树上第k层上最多有2^k-1个结点
3. 高度为h的二叉树最多有1+2+2²+…+2^h-1=2^h-1个结点（用等比数列求和）

完全二叉树性质

1. 对于有n个节点的完全二叉树：
   • i>1时，i的双亲为$\lceil i/2\rceil$
   • 当$2i\le n$时，节点i的左孩子编号为2i；当 $2i+1\le n$时，结点i的右孩子编号为2i+1
   • 节点i所在的层次（深度）为$\lceil lo{g}_{2}n\rceil +1$
2. 具有n个节点的完全二叉树的高度为$\lceil lo{g}_2(n+1)\rceil$或者$\lfloor lo{g}_{2}n\rfloor +1$

二、二叉树存储结构

顺序存储结构
链式存储结构

5.3 二叉树的遍

1.先序遍历

• 访问根节点
• 先序遍历左子树
• 先序遍历右子树

2.中序遍历

• 中序遍历左子树
• 访问根节点
• 中序遍历右子树

3.后序遍历

• 后序遍历左子树
• 后序遍历右子树
• 访问根节点
  递归遍历转化为非递归
  需要借助栈结构实现先进后出

4.层次遍历

层次遍历的意思是按照二叉树的层，从低层逐渐遍历到高层。要进行层次遍历，需要借助一个队列，先将根节点入队，如果他有左、右子树，则分别将他们入队。然后该节点出队

5.由遍历序列构造二叉树

由二叉树的先序序列和中序序列可以唯一的确定一棵二叉树。

由二叉树的后序序列和中序序列可以唯一的确定一棵二叉树。

层次遍历和中序遍历也可以唯一确定一棵二叉树

总之，一定要有中序遍历才能确定二叉树

TIPS:

1. 无论是前中后序遍历，其同一层节点的相对顺序都是不变的
2. 在前序遍历中，祖先节点在子孙节点前；在中序遍历中，父节点在其两个子节点中间；在后序遍历中，祖先节点会在子孙节点后面
3. 在中序遍历中，其根节点左边的序列为其左子树，右边的序列为其右子树；在一个子树序列中，可以随意选择其中的一个元素作为父节点，其左右子树则分布在其两遍。
4. 在前序遍历中，其根节点是序列的第一个元素
5. 在后序遍历中，其根节点是序列的最后一个元素
6. 在层次遍历中，一个树或者子树序列的第一个元素一定是根节点，而该树所属的子树的元素在序列的位置一定是紧密相连的
7. 使用上述的3、4、5、6点可以通过两个序列推出一颗固定的树（除了前序和后序之外）

给出两个序列，倒推出二叉树结构，一般使用的是递推法，比如给出了前序和中序序列后：

用后序和中序倒推也类似

前序和后序无法确认顺序是因为无法确认节点的左右顺序，比如说前序遍历为AB，后序遍历为BA，那么该树可能是B为左节点，A为根节点的树，也可能是B为右节点，A为根节点的树。层次遍历和后序遍历也同理

5.4 线索二叉树

一、线索二叉树概述

由于二叉树只存储了其子节点的信息，所以是无法直接得出某个节点p的前驱的。为了解决这个问题，使用如下算法：设置指针q和pre，pre是指针q指向的节点的前驱。如果发现指针q指向了p，则指针pre指向的节点就是p的前驱。这种方法需要二度遍历二叉树，时间开销为O(n)

以中序遍历为例子，代码如下：

一般二叉树面对需要频繁查找前驱和后继的场景性能不好，而且遍历操作必须从根开始，因此，使用优化过的**线索二叉树（又称为线索链表）**可以很好的应对这种情况。

在一棵二叉树中，一些节点的左节点指针或者右节点指针是空的，这些空指针被我们称为空链域。对于n个节点的二叉树，会有n+1个空链域，可以使用这些来记录前驱和后继信息。这些表示前驱和后继的指针称之为线索。

线索二叉树存储结构：

tag=1表示当前的指针作为线索，tag=0表示指向孩子

当rtag=1时，*rchild指向的是当前节点的后继；当ltag=1时，*lchild指向的是当前节点的前驱
二叉树线索化实际上就是在遍历二叉树的时候，顺便将其前驱和后继连接起来。线索二叉树可以很容易地或者找到某个节点的前驱和后继

TIPS：

1. 后序线索二叉树并不能解决求后续后继的问题，可能节点有两个子节点，从而没有空余的指针用于线索化指向后继。
2. 后序线索二叉树遍历的时候，最后访问跟节点，如果从右孩子x返回访问父节点，则由于节点x的右孩子不一定为空，所以导致通过指针无法遍历整棵树，所以需要借助栈的帮助

二、二叉树线索化

1.中序遍历二叉树线索化

// 中序线索化二叉树
ThreadNode *pre=NULL;   //全局变量pre，用于指向当前访问节点的前驱
void inThread(ThreadTree t){
    if (t!=NULL){
      inThread(t->lchild);
      visit(t);
      inThread(t->rchild);
    }
}
void visit(ThreadNode *q){
    if (q->lchild==NULL){   //如果左子节点为空，则让左子节点指向前驱
        q->lchild=pre;
        q->ltag=1;
    }
    // 如果当前节点有前驱并且前驱的右子节点为空，则让前驱的右子节点指向当前节点
    // 因为当前节点是前驱节点的后继
    if (pre!=NULL && pre->rchild==NULL){
        pre->rchild=q;
        pre->rtag=1;
    }
    pre=q;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2.先序遍历二叉树线索化

// 先序遍历线索化
ThreadNode *pre=NULL;   //全局变量pre，用于指向当前访问节点的前驱
void createOreThread(ThreadTree t){
    pre=NULL;
    if (t!=NULL){
        preThread(t);
        if (pre->rchild==NULL){
            pre->rtag=1;//特殊处理最后一个节点
        }
    }
}

void preThread(ThreadTree t){
    if (t!=NULL){
        visit(t);
        // 当ltag=0的时候，证明当前节点是有左子树的，否则的话其lchild指向的是他的前驱
        if (t->ltag==0){
            inThread(t->lchild);
        }
        inThread(t->rchild);
    }
}

void visit(ThreadNode *q){
    if (q->lchild==NULL){   //如果左子节点为空，则让左子节点指向前驱
        q->lchild=pre;
        q->ltag=1;
    }
    // 如果当前节点有前驱并且前驱的右子节点为空，则让前驱的右子节点指向当前节点
    // 因为当前节点是前驱节点的后继
    if (pre!=NULL && pre->rchild==NULL){
        pre->rchild=q;
        pre->rtag=1;
    }
    pre=q;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

主要和中序遍历的区别在于：需要特殊处理最后节点，并且访问lchild的时候需要防止循环问题

2.后序遍历二叉树线索化

和中序遍历二叉树线索化类似，但是需要单独处理最后节点问题。但是不会有中序线索化那种循环问题

三、寻找线索二叉树的前驱和后继

1.中序线索二叉树找前驱和后继

后继

1. 如果p->rtag=1，那么后继就是rchild
2. 如果p->rtag=0，证明该节点还有右子树，那么选取该子树的最左下节点就是当前节点的后继（不一定是叶节点）

第二步的代码如下:

//找到一棵树中第一个被中序遍历的结点，就是最左下的结点（不一定是叶节点）
ThreadNode* firstNode(ThreadNode *p){
    while (p->ltag==0)
        p=p->lchild;
    return p;
}

ThreadNode* nextNode(ThreadNode *p){
    // 右子树中最左下节点
    if (p->rtag==0) return firstNode(p->rchild);
    else return p->rchild;
}
1
2
3
4
5
6
7
8
9
10
11
12

利用上述代码还能实现无递归的中序二树遍历

// 无递归的中序二树遍历
void inOrder(ThreadNode *t){
    for (ThreadNode *p=firstNode(t);p!=NULL;p=nextNode(p))
        visit(p);
}
1
2
3
4
5

前驱
和后继类似

1. 如果p->ltag=1，那么前驱就是lchild
2. 如果p->ltag=0，证明该节点还有左子树，那么选取该子树的最右下节点就是当前节点的后继（不一定是叶节点）

//找到一棵树中最后一个被中序遍历的结点，就是最右下的结点（不一定是叶节点）
ThreadNode* lastNode(ThreadNode *p){
    while (p->rtag==0)
        p=p->rchild;
    return p;
}


1
2
3
4
5
6
7
8

同样，通过该法可以实现无递归的中序二树逆序遍历

// 无递归的中序二叉树逆序遍历
void revOrder(ThreadNode *t){
    for (ThreadNode *p=lastNode(t);p!=NULL;p=preNode(p))
        visit(p);
}
1
2
3
4
5

2.先序线索二叉树找前驱和后继

先序遍历为根 左 右

后继

1. 如果p->rtag=1，那么后继就是rchild
2. 如果p->rtag=0，证明该节点还有右子树，但是是否有左子树不得知。
   • 如果有左子树，那么左子树的跟就是它的后继
   • 如果没有左子树，那么右子树的根就是其他的后继

前驱

1. 如果p->ltag=1，那么前驱就是lchild
2. 如果p->ltag=0，证明没有前驱的相关信息，而在先序遍历中，其前驱不在其子树中，因此这种情况通过线索二叉树是无法得出当前节点的前驱的。

在情况2中，可以采用最原始的遍历法找前驱，也可以将树改造为三叉树，这种树一个结点中除了有指向左右节点指针，还有一个指向父节点的指针。

3.后序线索二叉树找前驱和后继

后序遍历的顺序为左 右 根

前驱

1. 如果p->ltag=1，那么前驱就是lchild
2. 如果p->ltag=0，证明该树有左子树，判断情况如下:
   • 如果p有右孩子，则前驱为右孩子
   • 如果没有右孩子，则前驱为左孩子

后继

1. 如果p->rtag=1，那么后继就是rchild
2. 如果p->rtag=0，而在后续遍历中，其后继都不在其子树中，因此这种情况通过线索二叉树是无法得出当前节点的后继的。

在情况2中，先序线索二叉树找前驱一样，和可以采用最原始的遍历法找前驱，也可以将树改造为三叉树，这种树一个结点中除了有指向左右节点指针，还有一个指向父节点的指针。

5.4 树、森林

一、树的存储结构

1.双亲表示法

这种存储方式采用一组连续的空间来存储每个节点，同时在每个节点之中增设一个伪指针，指示其双亲节点在数组中的位置。该存储结构利用了每个节点只有唯一双亲的性质，可以快速得到每个节点的双亲节点，但是求孩子节点需要遍历整个结构。

2.孩子表示法

孩子表示法是将每个节点的孩子节点都用单链表连接起来形成一个线性结构，此时n个节点就有n个孩子链表。这种存储方式寻找子女操作非常直接，但是寻找双亲需要遍历n个节点中孩子链表指针域所指向的n个孩子链表。

3.孩子兄弟表示法

孩子兄弟表示法又称为二叉树表示法。孩子兄弟表示法包括三部分内容：节点之、指针节点第一个孩子节点的指针、指向节点下一个兄弟节点的指针。也就是说，节点的第一个指针用于指向其孩子节点，第二个指针用于指向同一层的其他节点，通常称为“左孩子右兄弟”。这种存储表示法比较灵活，可以通过该方法实现将树转化为二叉树

二、树、森林与二叉树的转换（施工中🚧）

！本节施工中🚧非最终版

二叉树和树可以相互转换；二叉树和森林可以相互转换，但是树本来就是数量为1的森林，因此没有树转化为森林这一说

二叉树和树都可以采用二叉链表作为存储结构，因此以二叉链表作为媒介可以导出树和二叉树的一个对应关系。有关树和二叉树的转换详见孩子兄弟表示法

将森林转化为二叉树的规则和树类似，先将森林中的每棵树转化为二叉树，由于任何一刻树对应的二叉树右子树必为空，因此将第二棵二叉树视为第一棵树根的右兄弟，以此类推。

森林中树的个数就是起对应的二叉树的根节点A及其右兄弟的个数，或者解释为对应二叉树从根节点A开始不断地往右孩子访问，所访问到的节点数。因为在森林对应的二叉树中，根节点及其右孩子在森林中都是一棵独立的树。

三、树和森林的遍历

树的遍历是用某种方式访问树的每个节点并且只访问一次，主要有两种方式：

1. 先根遍历：如果树非空，先访问根节点，再依次遍历根节点每棵子树，遍历每棵子树仍遵循先根后子树的规则。
2. 后根遍历：如果树非空。先一次遍历根节点的每棵子树，再访问根节点，遍历子树时仍遵循该规则。
3. 层次遍历：使用队列实现，和二叉树的层次遍历类似

注意：请区分先根遍历和二叉树的先序遍历

森林也有两种遍历方法：


树的后根遍历序列和它对应的二叉树中根遍历序列一致，其余对应关系如下表：

树的应用——并查集（不太熟）

并查集的三个基本操作为：

1. Union(S,root1, root2)
2. Find(S,x)
3. Initial(S)

并查集的存储结构是树（森林）的双亲，每个子集用一棵树表示，所有表示子集合的树构成全集合的森林，存放在双亲表示数组内。通常用数组元素的下标带遍元素名，用根节点的下标代表子集合名。

5.5 树与二叉树的应用

一、二叉排序树（BST）

定义

二叉排序树是有以下特征的二叉树：

1. 如果左子树非空，则左子树所有节点值均小于根节点的值
2. 如果右子树非空，则右子树上所有节点的值均大于根节点的值
3. 左右节点也分别是一棵二叉排序树

根据定义，左子树节点值 < 根节点值 < 右子树节点值

二叉排序树的查找

二叉排序树查找从根节点开始，如果二叉排序树非空，则先用给定值和根节点比较，如果相等则成功；如果不相等则比较：如果小于根节点则在根节点左子树上查找；如果大于根节点则在根节点右子树上查找。

二叉排序树的插入

二叉排序树是一种动态树表，其特点是树的结构会根据插入节点而改变。插入节点的过程如下：如果树为空，则直接插入；否则，如果插入关键字k小于根节点值则插入到左子树；如果关键字k大于根节点值则插入到右子树。插入的节点一定是一个新添加的叶节点。

查找效率

若排序树为平衡二叉树，则它的平均查找长度为O(log₂n)，如果二叉排序树只是一个只有右（左）孩子的单支树，则平均查找长度为O(n)。

二、平衡二叉树

定义

为了避免树的高度增长过快，降低二叉排序树的性能，规定在插入和删除二叉树节点是，要保证任意节点的左右子树高度差的绝对值不超过1。如果出现了不平衡，则需要通过调整个节点的位置关系使得重新平衡。节点左子树和右子树的高度差称为该节点的平衡因子

插入

平衡二叉树的插入过程前半部分和二叉排序树一样。但是如果插入后出现了不平衡，则需要进行调整，主要分为以下四种情况：

（1）LL平衡旋转（右单旋转）：

（2）RR平衡旋转（左单旋转）：

（3）LR平衡旋转（先左后右双旋转）：

查找

三、哈夫曼树和哈夫曼编码

在许多应用中，树的某一个节点会被赋予一个权重，称为该节点的权
带权路径长度：从树的根到任意节点的路径长度与该节点上的权的积，称之为该节点的
树的带权路径长度WPL：树中的所有叶节点的带权路径之和
最优二叉树：在含有n个带权也节点的二叉树中，其中带权路径长度之和最小的二叉树称为哈夫曼树

1.哈夫曼树的构造

算法描述：

1. 将n个节点分别作为n棵仅有一个节点的二叉树构造出森林F
2. 构造一个新节点，选择F中根节点权重最小的两棵树作为它的左右子树，并且将新节点的权值置为左右两棵子树的根节点的权值之和
3. 从F中删除两棵子树，并且将新得到的树加入F中
4. 重复2、3步直到F中只有一棵树

哈夫曼树的构造具有以下特点

• 每个初始节点都最终成为叶节点，而且权值越小的节点到根节点的路径长度越大
• 构造中新建了n-1个节点，因此哈夫曼树的节点总数为2n-1，换句话说，一棵哈夫曼树有n个叶节点，那么他就有n-1个非叶节点
• 每次构构造选择2棵树作为新节点的孩子节点，因此哈夫曼树不存在度为1的节点
• 哈夫曼树形态可能不一样，但是树的带权路径长度都是一样的

哈夫曼编码

哈夫曼编码可以将每一个出现的字符当作是一个独立的结点，其权值为它出现的频度，构造出的哈夫曼树可以压缩二进制编码的长度。哈夫曼编码将频率较高的编码安排在路径长度较短的位置，将频率较低的编码安排在路径长度较长的位置，从而实现了数据压缩

在编码中，如果没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码。如果使用的是非前缀编码，那么在解码的时候会引发歧义。在树结构中，前缀编码的表现形式是所有编码均为叶子结点

四、并查集

并查集是一种简单的集合表示，是一种集合。该种集合存储结构上使用数组进行存储。逻辑结构上采用树和森林的逻辑结构。

一个并查集C中有n个元素，这n个元素存放在一个大小为n的数组中，其中数组下标为元素名，数组元素值为当前元素的父节点名。而根节点的下标则为子集合名，根节点的值为-1，表示他没有父节点。比如a[4]=5表示的是：集合中4号元素的父节点为5号元素。可以看出，并查集存储逻辑采用的是树的双亲表示法

一个并查集数组中能表示若干个树，一棵树是一个子集。这些树构成的森林则是全集合。要寻找元素是否位于同一子集，只需要查找他们的根元素是否为同一个。而并查集中的Find操作，是寻找指定元素的根节点，而非是寻找元素本身。