第五章 树

img

5.1. 树的概念

5.1.1. 树的基本定义

树:n(n>=0)个节点的有限集合，是一种逻辑结构，当n=0时为空树，且非空树满足:

  • 有且仅有一个特定的称为根的节点
  • 当n>1时，其余结点可分为m (m >0) 个互不相交的有限集合T1,T2,...,Tm，其中每个集合本身又是一棵树，并且称为根结点的子树

互不相交就是仅有一个前驱

树是一种递归的数据结构

非空树特点：

  • 有且仅有一个根节点
  • 没有后继的结点称为“叶子结点”（或终端节点）
  • 有后继的结点称为“分支结点” (或非终端结点)
  • 除了根节点外，任何一个结点都有且仅有一个前驱
  • 每个结点可以有0个或多个后继

基本术语

img

  • 祖先结点：从自己出发走到根结点的最短路这条路径上的所有节点都是祖先节点
  • 子孙结点：自己的之下都是子孙节点
  • 双亲结点 (父节点) ：和自己相连的上一个就是父节点
  • 孩子结点：和自己相连的下面一个
  • 兄弟结点：我自己同一个父节点的
  • 堂兄弟结点：同一层的节点

路径：两个结点的间的路径只能从上往下

路径长度：从一个结点到另一个结点所经过了几条边

树的路径长度是指树根到每个节点的路径长的总和

属性:

image-20250401223453712

叶子结点的度为0

节点的深度一般是从1开始的，但是有的教材会从0开始，都一样，该怎么算就怎么算就行

有序树和无序树

  • 有序树–逻辑上看，树中结点的各子树从左至右是有次序的，不能互换
  • 无序树–逻辑上看，树中结点的各子树从左至右是无次序的，可以互换

森林是m(>=0)棵互不相交的树的集合。

image-20250401223710824

5.1.2. 树的常考性质

img

  • 常见考点1: 树中的结点数=总度数+1

    • 结点的度：节点有几个孩子

  • 常见考点2:

    度为m的树、m叉树的区别：

    树的度–各结点的度的最大值；m叉树–每个结点最多只能有m个孩子的树

    • image-20250401224343386

  • 常见考点3: 度为m的树第 i 层至多有m^{i}-1个结点

    • image-20250401224506271

  • 常见考点4: 高度为h的m叉树至多有\frac{m^{h}-1}{m-1}个结点。

    • 图中是q的n次方并非q*n

    • image-20250401224557878

  • 常见考点5:

    高度为h的m叉树至少有h个结点；高度为h、度为m的树至少有h+m-1个结点。

    • image-20250401224719057

  • 常见考点6: 具有n个结点的m叉树的最小高度为\log_{m}[n(m-1)+1]

    • 第二行是m的h次方不是m*h

    • image-20250401225029295

5.2. 二叉树

img

5.2.1. 二叉树的定义

二叉树是n (n>=0)个结点的有限集合:

  • 或者为空二叉树，即n =0。
  • 或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。
  • 左子树和右子树又分别是一棵二叉树。

特点：

  • 每个结点至多只有两棵子树

  • 左右子树不能颠倒 (二叉树是有序树)

  • 二叉树可以是空集合，根可以有空的左子树和空的右子树

    image-20250402145923473

5.2.2. 特殊二叉树

image-20250402150305392

完全二叉树如果有一个节点只有一个孩子，那这个孩子只可能是左孩子不可能是右孩子

二叉排序树：

一棵二叉树或者是空二叉树，或者是具有如下性质的二叉树:

  • 左子树上所有结点的关键字均小于根结点的关键字
  • 右子树上所有结点的关键字均大于根结点的关键字
  • 左子树和右子树又各是一棵二叉排序树

img

查找元素起来很方便，就直接是二分查找

平衡二叉树：树上任一结点的左子树和右子树的深度之差不超过1。

左边是平衡的，右边是不平衡的

这个是希望树往宽的生长而不是往深的生长

平衡二叉搜索树能有更高的搜索效率

image-20250402150602250

5.2.3. 二叉树的性质

image-20250402151214842

image-20250402151449752

image-20250402151402781

下面是完全二叉树的常考性质

常见考点1：

image-20250402151818934

图中是第一个式子的推导过程

image-20250402151953671

这是第二个式子的推导过程

image-20250402152715525

image-20250402152820935

5.2.4. 二叉树存储实现

二叉树的顺序存储：

基本只用来存储完全二叉树，对于非完全二叉树来说，存储密度太低了，浪费了很多的空间，所以非完全二叉树不用顺序存储

二叉树的顺序存储中，一定要把二叉树的结点编号与完全二叉树对应起来

image-20250402153120501

几个重要常考的基本操作：

  • i 的左孩子：2i
  • i 的右孩子：2i+1
  • i 的父节点：i/2
  • i 所在的层次：log(n+1)或者logn +1

若完全二叉树中共有n个结点，则

  • 判断i是否有左孩子?
    • 2i<=n
  • 判断i是否有右孩子?
    • 2i+1<=n
  • 判断i是否是叶子/分支结点?
    • i>n/2
1
2
3
4
5
6
7
8
9
10
11
12
13
#define MaxSize 100
 
struct TreeNode{
   ElemType value; //结点中的数据元素
   bool isEmpty;   //结点是否为空
};
 
main(){
   TreeNode t[MaxSize];
   for (int i=0; i<MaxSize; i++){
      t[i].isEmpty = true;
   }
}

image-20250402154158995

链式存储

重点：n个结点的二叉链表共有n+1个空链域

image-20250402153906362

二叉树从无到有的过程：

（这样构建也太麻烦了，还是看看后面怎么递归建立吧）

image-20250402153949465

image-20250402154126495

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
//二叉树的结点
 
struct ElemType{
   int value;
};
 
typedef struct BiTnode{
   ElemType data;          //数据域
   struct BiTNode *lchild, *rchild; //左、右孩子指针
}BiTNode, *BiTree;
 
//定义一棵空树
BiTree root = NULL;
 
//插入根节点
root = (BiTree) malloc (sizeof(BiTNode));
root -> data = {1};
root -> lchild = NULL;
root -> rchild = NULL;
 
//插入新结点
BiTNode *p = (BiTree) malloc (sizeof(BiTNode));
p -> data = {2};
p -> lchild = NULL;
p -> rchild = NULL;
root -> lchild = p; //作为根节点的左孩子
  • 二又树的顺序存储中，一定要把二叉树的结点编号与完全二叉树对应起来
  • 最坏情况:高度为 h 且只有 h 个结点的单支树 (所有结点只有右孩子)，也至少需要 2^h-1个存储单元
  • 结论:二叉树的顺序存储结构，只适合存储完全二叉树

5.3. 二叉树的遍历和线索二叉树

5.3.1. 二叉树的先中后序遍历

  • 遍历：按照某种次序把所有结点都访问一遍
  • 层次遍历：基于树的层次特性确定的次序规则

img

二又树的递归特性:
【1】要么是个空二叉树
【2】要么就是由“根节点+左子树+右子树”组成的二叉树

image-20250402161830960

image-20250402162212948

image-20250402162315499

【二叉树的先中后遍历】

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef struct BiTnode{
   ElemType data;          
   struct BiTNode *lchild, *rchild; 
}BiTNode, *BiTree;
 
void PreOrder(BiTree T){
   if(T!=NULL){
      visit(T);                 //访问根结点
      PreOrder(T->lchild);      //递归遍历左子树
      PreOrder(T->rchild);      //递归遍历右子树
   }
}
 
1
2
3
4
5
6
7
8
9
10
11
12
typedef struct BiTnode{
   ElemType data;          
   struct BiTNode *lchild, *rchild; 
}BiTNode, *BiTree;
 
void InOrder(BiTree T){
   if(T!=NULL){
      InOrder(T->lchild);       //递归遍历左子树
      visit(T);                 //访问根结点
      InOrder(T->rchild);       //递归遍历右子树
   }
}
1
2
3
4
5
6
7
8
9
10
11
12
typedef struct BiTnode{
   ElemType data;          
   struct BiTNode *lchild, *rchild; 
}BiTNode, *BiTree;
 
void PostOrder(BiTree T){
   if(T!=NULL){
      PostOrder(T->lchild);       //递归遍历左子树    
      PostOrder(T->rchild);       //递归遍历右子树
      visit(T);                 //访问根结点
   }
}

5.3.2. 二叉树的层序遍历

102. 二叉树的层序遍历 - 力扣（LeetCode）

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
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        queue<TreeNode*> q;
        if(root==nullptr)
            return res;
        q.push(root);
        while(!q.empty())
        {
            int size=q.size();
            vector<int> v;
            for(int i=0;i<size;i++)
            {
                auto p=q.front();
                q.pop();
                v.push_back(p->val);
                if(p->left)
                    q.push(p->left);
                if(p->right)
                    q.push(p->right);
            }
            res.push_back(v);
        } 
        return res;
    }
};

算法思想:

  • 1.初始化一个辅助队列
  • 2.根结点入队
  • 3.若队列非空，则队头结点出队，访问该结点，并将孩子插入队尾(如果有的话)
  • 4.重复3直至队列为空
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
//二叉树的结点(链式存储)
typedef struct BiTnode{
   ElemType data;          
   struct BiTNode *lchild, *rchild; 
}BiTNode, *BiTree;
 
//链式队列结点
typedef struct LinkNode{
   BiTNode * data;
   typedef LinkNode *next;
}LinkNode;
 
typedef struct{
   LinkNode *front, *rear;  
}LinkQueue;
 
//层序遍历
void LevelOrder(BiTree T){
   LinkQueue Q;
   InitQueue (Q);          //初始化辅助队列
   BiTree p;
   EnQueue(Q,T);           //将根节点入队
   while(!isEmpty(Q)){     //队列不空则循环
      DeQueue(Q,p);        //队头结点出队
      visit(p);            //访问出队结点
      if(p->lchild != NULL)
         EnQueue(Q,p->lchild);   //左孩子入队
      if(p->rchild != NULL)
         EnQueue(Q,p->rchild);   //右孩子入队
   }
}

这种写法会让在队列里面的节点并不是同一层的节点，所以笔者更推荐上面的写法，上面的写法做很多题也很方便

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

  • 一个前序遍历序列可能对应多种二叉树形态。同理，一个后序遍历序列、一个中序遍历序列、一个层序遍历序列也可能对应多种二叉树形态。

    即：若只给出一棵二叉树的 前/中/后/层序遍历序列 中的一种，不能唯一确定一棵二叉树。

由二叉树的遍历序列构造二叉树：

注：必须得有中序才可以，只有前序和后序不可以唯一确定一颗二叉树

原因：因为前后层序是确定根节点的，只有中序遍历才能够划分左右子树

前序+中序遍历序列

105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）

[Day25 | 二叉树 从中序与后序遍历构造二叉树&&最大二叉树 | Darlingの妙妙屋](https://darling-123456.github.io/2024/10/24/刷题记录/代码随想录 Day25 二叉树：从中序与后序遍历构造二叉树&&最大二叉树/)

代码随想录 | Day25 | 二叉树：从中序与后序遍历构造二叉树&&最大二叉树_根据中序和后序画二叉树-CSDN博客

1.前序第一个肯定是根节点

2.根据根节点在中序中的位置，判断左右子树，在根节点左边的肯定是左子树，在根节点右边的肯定是右子树

3.重复1,2，过程，在结点数不为1的子树中继续寻找根节点和左右子树

image-20250402165651936

后序+中序遍历序列

106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode）

[Day25 | 二叉树 从中序与后序遍历构造二叉树&&最大二叉树 | Darlingの妙妙屋](https://darling-123456.github.io/2024/10/24/刷题记录/代码随想录 Day25 二叉树：从中序与后序遍历构造二叉树&&最大二叉树/)

代码随想录 | Day25 | 二叉树：从中序与后序遍历构造二叉树&&最大二叉树_根据中序和后序画二叉树-CSDN博客

1.后序最后一个肯定是根节点

2.根据根节点在中序中的位置，判断左右子树，在根节点左边的肯定是左子树，在根节点右边的肯定是右子树

3.重复1,2，过程，在结点数不为1的子树中继续寻找根节点和左右子树

image-20250402170144748

层序+中序遍历序列

1.层序第一个肯定是根节点

2.根据根节点在中序中的位置，判断左右子树，在根节点左边的肯定是左子树，在根节点右边的肯定是右子树

3.重复1,2，过程，在结点数不为1的子树中继续寻找根节点和左右子树

image-20250402170413817

image-20250402170654193

5.3.4. 线索二叉树的概念

image-20250403213714775

image-20250403212831327

线索二叉树的概念与作用

  • n 个结点的二叉树，有 n+1 个空链域，可用来记录前驱、后继的信息。
  • 指向前驱、后继的指针被称为“线索”，形成的二叉树被称为线索二叉树。
  • 在二叉树的结点上加上线索的二叉树称为线索二叉树，对二叉树以某种遍历方式（如先序、中序、后序或层次等）进行遍历，使其变为线索二叉树的过程称为对二叉树进行线索化。
  • 线索二叉树的结点在原本二叉树的基础上，新增了左右线索标志 tag。当 tag == 0 时，表示指针指向孩子；当 tag == 1 时，表示指针是“线索”。
  • image-20250403213056978
1
2
3
4
5
6
//线索二叉树结点
typedef struct ThreadNode{
   ElemType data;
   struct ThreadNode *lchild, *rchild;
   int ltag, rtag;                // 左、右线索标志
}ThreadNode, *ThreadTree;

中序线索化的存储

img

先序线索化的存储

img

后序线索化的存储

img

只要是叶子结点，ltag和rtag都是1而不是0

中序线索化的序列的第一个结点的left为nullptr，最后一个结点的right指针为nullptr

先序线索化的序列的最后一个结点的right指针为nullptr

后序线索化的序列的第一个结点的left为nullptr

LCR 053. 二叉搜索树中的中序后继 - 力扣（LeetCode）

寻找中序后继的题目，按照咸鱼的思路写就行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    TreeNode* res=nullptr;
    TreeNode* pre=nullptr;
    void tra(TreeNode* t, TreeNode* p)
    {
        if(t==nullptr)
            return ;
        tra(t->left,p);
        if(pre!=nullptr&&p->val==pre->val)
            res=t;
        pre=t;
        tra(t->right,p);
    }
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        tra(root,p);
        return res;
    }
};

5.3.5. 二叉树的线索化

img

image-20250406154859793

中序线索化：

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
37
38
39
typedef struct ThreadNode{
   int data;
   struct ThreadNode *lchild, *rchild;
   int ltag, rtag;                // 左、右线索标志
}ThreadNode, *ThreadTree;
 
//全局变量pre, 指向当前访问的结点的前驱
TreadNode *pre=NULL;
 
void InThread(ThreadTree T){
    if(T!=NULL){
        InThread(T->lchild);    //中序遍历左子树
        visit(T);               //访问根节点
        InThread(T->rchild);    //中序遍历右子树
    }
}
 
void visit(ThreadNode *q){
   if(q->lchid = NULL){                 //左子树为空，建立前驱线索   
      q->lchild = pre;
      q->ltag = 1;
   }
 
   if(pre!=NULL && pre->rchild = NULL){ 
      pre->rchild = q;           //建立前驱结点的后继线索
      pre->rtag = 1;
   }
   pre = q;
}
 
//中序线索化二叉树T
void CreateInThread(ThreadTree T){
   pre = NULL;                //pre初始为NULL
   if(T!=NULL);{              //非空二叉树才能进行线索化
      InThread(T);            //中序线索化二叉树
      if(pre->rchild == NULL)
         pre->rtag=1;         //处理遍历的最后一个结点
   }
}

先序线索化：

image-20250406155536217

image-20250406155600033

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
37
38
39
40
41
42
typedef struct ThreadNode{
   int data;
   struct ThreadNode *lchild, *rchild;
   int ltag, rtag;                // 左、右线索标志
}ThreadNode, *ThreadTree;
 
//全局变量pre, 指向当前访问的结点的前驱
TreadNode *pre=NULL;
 
//先序遍历二叉树，一边遍历一边线索化
void PreThread(ThreadTree T){
   if(T!=NULL){
      visit(T);
      if(T->ltag == 0)         //lchild不是前驱线索
         PreThread(T->lchild);
      PreThread(T->rchild);
   }
}
 
void visit(ThreadNode *q){
   if(q->lchid = NULL){                 //左子树为空，建立前驱线索   
      q->lchild = pre;
      q->ltag = 1;
   }
 
   if(pre!=NULL && pre->rchild = NULL){ 
      pre->rchild = q;           //建立前驱结点的后继线索
      pre->rtag = 1;
   }
   pre = q;
}
 
//先序线索化二叉树T
void CreateInThread(ThreadTree T){
   pre = NULL;                //pre初始为NULL
   if(T!=NULL);{              //非空二叉树才能进行线索化
      PreThread(T);            //先序线索化二叉树
      if(pre->rchild == NULL)
         pre->rtag=1;         //处理遍历的最后一个结点
   }
}

后序线索化：

image-20250406155731003

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
37
38
39
40
typedef struct ThreadNode{
   int data;
   struct ThreadNode *lchild, *rchild;
   int ltag, rtag;                // 左、右线索标志
}ThreadNode, *ThreadTree;
 
//全局变量pre, 指向当前访问的结点的前驱
TreadNode *pre=NULL;
 
//后序遍历二叉树，一边遍历一边线索化
void PostThread(ThreadTree T){
   if(T!=NULL){
      PostThread(T->lchild);
      PostThread(T->rchild);
      visit(T);                  //访问根节点
   }
}
 
void visit(ThreadNode *q){
   if(q->lchid = NULL){                 //左子树为空，建立前驱线索   
      q->lchild = pre;
      q->ltag = 1;
   }
 
   if(pre!=NULL && pre->rchild = NULL){ 
      pre->rchild = q;           //建立前驱结点的后继线索
      pre->rtag = 1;
   }
   pre = q;
}
 
//后序线索化二叉树T
void CreateInThread(ThreadTree T){
   pre = NULL;                //pre初始为NULL
   if(T!=NULL);{              //非空二叉树才能进行线索化
      PostThread(T);            //后序线索化二叉树
      if(pre->rchild == NULL)
         pre->rtag=1;         //处理遍历的最后一个结点
   }
}

5.3.6. 在线索二叉树中找前驱/后继

img

image-20250406162528008

疑惑点：线索二叉树不是左孩子指向前驱，右孩子指向后继吗？那为什么有找不到前序和后继的情况？

如果当前有孩子的话，是不会进行线索化的，只有叶子节点或者结点的孩子中为空的指针才会被线索化

个人对下面表格的理解：即先序为啥找不到前驱，后序为啥找不到后继

先序线索二叉树找不到前驱是因为遍历顺序是根左右，如果当前结点没有被线索化，即ltag和rtag都为0，则从根结点即“当前结点”出发，找不到前驱，只能找到叫做左或者右的后继

后序线索二叉树也同理，找不到后继是因为遍历顺序是左右根，如果当前结点没有被线索化，即ltag和rtag都为0，则从根结点即“当前结点”出发，找不到后继，只能找到叫做左或者右的前驱

但是中序线索二叉树就不一样了，是左根右，你从当前结点出发，不管当前结点有没有被线索化，都可以找到前驱和后继

注：中序线索二叉树能找到左子树最右边结点或者右子树最左边的节点（即tag==0的情况）是因为 我们的当前结点的前驱和后继都是当前结点的子代，都可以通过当前结点找到

而前序线索二叉树是根左右，我们当前结点的的前驱是当前结点的祖先，那当然不可能通过当前结点找到

而后序线索二叉树是左右根，我们当前结点的的后继是当前结点的祖先，那当然不可能通过当前结点找到

土办法：从根节点重新遍历一次寻找前驱或者后继

如果给了一个线索二叉树中的一个结点p

1.如果是中序线索二叉树的话，我们可以从这个结点开始进行正向的中序遍历，也可以进行逆向的中序遍历，但都不会得到完整序列，只是从p开始而已

2.如果是先序线索二叉树的话，我们可以从这个结点开始进行正向的先序遍历，因为对于没有线索化的节点，我们只能找到后继找不到前驱，除非有父节点

3.如果是后序线索二叉树的话，我们可以从这个结点开始进行逆向的后序遍历，因为对于没有线索化的节点，我们只能找到前驱找不到后继，除非有父节点

最常考的还是手算

中序线索二叉树找到指定结点 * p 的中序后继 next：

  1. 若p->rtag==1，则next = p->rchild；

    说明 p的rchild是一个叶子节点

  2. 若p->rtag==0，则 next 为 p 的右子树中最左下结点。

    说明p是右子树的根节点

image-20250406160451264

image-20250406160856787

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 找到以p为根的子树中，第一个被中序遍历的结点
ThreadNode *FirstNode(ThreadNode *p){
    // 循环找到最左下结点（不一定是叶结点）
    while(p->ltag==0)
        p=p->lchild;
    return p;
}
 
// 在中序线索二叉树中找到结点p的后继结点
ThreadNode *NextNode(ThreadNode *p){
    // 右子树中最左下的结点
    if(p->rtag==0)
        return FirstNode(p->rchild);
    else
        return p->rchild;
}
 
// 对中序线索二叉树进行中序循环（非递归方法实现）
void InOrder(ThreadNode *T){
    for(ThreadNode *p=FirstNode(T); p!=NULL; p=NextNode(p)){
        visit(p);
    }
}

中序线索二叉树找到指定结点 * p 的中序前驱 pre：

  1. 若p->ltag==1，则pre = p->lchild；
  2. 若p->ltag==0，则 next 为 p 的左子树中最右下结点。

image-20250406161046861

image-20250406161213556

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 找到以p为根的子树中，最后一个被中序遍历的结点
ThreadNode *LastNode(ThreadNode *p){
    // 循环找到最右下结点（不一定是叶结点）
    while(p->rtag==0)
        p=p->rchild;
    return p;
}

// 在中序线索二叉树中找到结点p的前驱结点
ThreadNode *PreNode(ThreadNode *p){
    // 左子树中最右下的结点
    if(p->ltag==0)
        return LastNode(p->lchild);
    else
        return p->lchild;
}

// 对中序线索二叉树进行中序循环（非递归方法实现）
void RevOrder(ThreadNode *T){
    for(ThreadNode *p=LastNode(T); p!=NULL; p=PreNode(p))
        visit(p);
}

先序线索二叉树找到指定结点 * p 的先序后继 next：

  1. 若p->rtag==1，则next = p->rchild；

  2. 若p->rtag==0：

    1. 若 p 有左孩子，则先序后继为左孩子；
    2. 若 p 没有左孩子，则先序后继为右孩子。

image-20250406161503141

先序线索二叉树找到指定结点 * p 的先序前驱 pre：

  1. 前提：改用三叉链表，可以找到结点 * p 的父节点。如果找不到父节点，p结点本身也不是左孩子是一颗子树而且不是叶子的话，就找不到先序前驱
  2. 如果能找到 p 的父节点，且 p 是左孩子：p 的父节点即为其前驱；
  3. 如果能找到 p 的父节点，且 p 是右孩子，其左兄弟为空：p 的父节点即为其前驱；
  4. 如果能找到 p 的父节点，且 p 是右孩子，其左兄弟非空：p 的前驱为左兄弟子树中最后一个被先序遍历的结点；
  5. 如果 p 是根节点，则 p 没有先序前驱。

image-20250406161714983

image-20250406161904238

后序线索二叉树找到指定结点 * p 的后序前驱 pre：

  1. 若p->ltag==1，则pre = p->lchild；
  2. 若p->ltag==0：
    • 若 p 有右孩子，则后序前驱为右孩子；
    • 若 p 没有右孩子，则后续前驱为左孩子。

后序线索二叉树找到指定结点 * p 的后序后继 next：

  1. 前提：改用三叉链表，可以找到结点 * p 的父节点。
  2. 如果能找到 p 的父节点，且 p 是右孩子：p 的父节点即为其后继；
  3. 如果能找到 p 的父节点，且 p 是左孩子，其右兄弟为空：p 的父节点即为其后继；
  4. 如果能找到 p 的父节点，且 p 是左孩子，其右兄弟非空：p 的后继为右兄弟子树中第一个被后序遍历的结点；
  5. 如果 p 是根节点，则 p 没有后序后继。

image-20250406162136996

image-20250406162322277

5.4. 树和森林

img

image-20250406163614232

5.4.1. 树的存储结构

image-20250406164818695

双亲表示法（顺序存储）：每个结点中保存指向双亲的“指针”。

image-20250406163811100

image-20250406163844816

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//数据域：存放结点本身信息。
//双亲域：指示本结点的双亲结点在数组中的位置。
#define MAX_TREE_SIZE 100  //树中最多结点数
 
typedef struct{      //树的结点定义
   ElemType data; 
   int parent;      //双亲位置域
}PTNode;
 
typedef struct{                   //树的类型定义
   PTNode nodes[MAX_TREE_SIZE];   //双亲表示
   int n;                         //结点数
}PTree;

image-20250406163939373

**增：**新增数据元素，无需按逻辑上的次序存储；（需要更改结点数n）

删：（叶子结点）：
① 将伪指针域设置为-1；
②用后面的数据填补；（需要更改结点数n）

查询：
①优点-查指定结点的双亲很方便；
②缺点-查指定结点的孩子只能从头遍历，空数据导致遍历更慢；

优点: 查指定结点的双亲很方便
缺点:查指定结点的孩子只能从头遍历

孩子表示法（顺序+链式存储）
孩子表示法:顺序存储各个节点，每个结点中保存孩子链表头指针。

image-20250406164112061

image-20250406164209904

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct CTNode{
   int child;    //孩子结点在数组中的位置
   struct CTNode *next;    // 下一个孩子
};
 
typedef struct{
   ElemType data;
   struct CTNode *firstChild;    // 第一个孩子
}CTBox;
 
typedef struct{
   CTBox nodes[MAX_TREE_SIZE];
   int n, r;   // 结点数和根的位置
}CTree;

image-20250406164345769

孩子兄弟表示法（链式存储）
用孩子兄弟表示法可以将树转换为二叉树的形式。

image-20250406164615516

image-20250406164711923

1
2
3
4
5
//孩子兄弟表示法结点
typedef struct CSNode{
    ElemType data;
    struct CSNode *firstchild, *nextsibling;	//第一个孩子和右兄弟结点
}CSNode, *CSTree;

5.4.2. 树和森林 与二叉树之间的转换

image-20250406164947663

image-20250406170017339

树和森林 -> 二叉树

其实就是写出来孩子兄弟表示法表示的树和森林

image-20250406165312347

image-20250406165438855

二叉树->树

image-20250406165633021

二叉树->森林

image-20250406165910035

5.4.3. 树和森林的遍历

image-20250406170855809

树的先根遍历
若树非空，先访问根结点，再依次对每棵子树进行先根遍历；（与对应二叉树的先序遍历序列相同）
树的先根遍历序列与这棵树相应二叉树的先序序列相同

image-20250406170235022

1
2
3
4
5
6
7
void PreOrder(TreeNode *R){
   if(R!=NULL){
      visit(R);    //访问根节点
      while(R还有下一个子树T)
         PreOrder(T);      //先跟遍历下一个子树
   }
}

树的后根遍历
若树非空，先依次对每棵子树进行后根遍历，最后再访问根结点。（深度优先遍历）
树的后根遍历序列与这棵树相应二叉树的中序序列相同

image-20250406170401330

1
2
3
4
5
6
7
8
void PostOrder(TreeNode *R){
   if(R!=NULL){
      while(R还有下一个子树T)
         PostOrder(T);      //后跟遍历下一个子树
      visit(R);    //访问根节点
   }
}

层序遍历（队列实现）

和二叉树一样的思路

  1. 若树非空，则根结点入队；
  2. 若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队；
  3. 重复以上操作直至队尾为空；

image-20250406170453205

森林的遍历

  • 先序遍历：等同于依次对各个树进行先根遍历；也可以先转换成与之对应的二叉树，对二叉树进行先序遍历；

image-20250406170626547

image-20250406170656817

  • 中序遍历：等同于依次对各个树进行后根遍历；也可以先转换成与之对应的二叉树，对二叉树进行中序遍历；

image-20250406170726016

image-20250406170759061

image-20250406170833829

5.5. 应用

5.5.1. 哈夫曼树

image-20250406172827729

1、哈夫曼树定义

  1. 结点的权:有某种现实含义的数值(如:表示结点的重要性等)
  2. 结点的带权路径长度：从树的根到该结点的路径长度(经过的边数)与该结点上权值的乘积。
  3. 树的带权路径长度:树中所有叶结点的带权路径长度之和 (WPL,Weighted Path Length)。
  4. 哈夫曼树的定义：在含有n个带权叶结点的二叉树中，其中带权路径长度(WPL) 最小的二叉树，也称最优二叉树。

image-20250406171853348

image-20250406171934659

2、哈夫曼树的构造（重点）

一共合并n-1次

image-20250406172139008

构造哈夫曼树的注意事项：

  • 每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大
  • 哈夫曼树的结点总数为2n - 1
    • 叶子结点为n，非叶子节点为n-1个，叶子结点比非叶子节点多一个
  • 哈夫曼树中不存在度为1的结点
  • 哈夫曼树并不唯一，但WPL必然相同且为最优

image-20210926174150209

3、哈杜曼编码（重点）

image-20250406172415178

image-20250406172506789

  • 固定长度编码：每个字符用相等长度的二进制位表示
  • 可变长度编码：允许对不同字符用不等长的二进制位表示
  • 若没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码、
    • 前缀编码解码无歧义
    • image-20250406172856327

曼树得到哈夫曼编码–字符集中的每个字符作为一个叶子结点，各个字符出现的频度作为结点的权值，根据之前介绍的方法构造哈夫曼树 。

因为哈夫曼树不唯一，所以哈夫曼编码也不唯一

哈夫曼编码还可以用于数据的压缩

重点：

哈夫曼树并非只有下图这个形状，要严格构造出来一颗子树后要严格按照取集合中的最小值来构造

image-20250406225005948

还可以是下面这种的，还可以是别的各种形状的，不要刻板印象了

image-20250406225128861

5.5.2 并查集

image-20250406182211998

并查集：一种简单的集合表示，它支持以下三种操作

1.IniTial(S):将集合s中的每个元素都初始化为只有一个单元素的子集合

2.Union(S,Root1,Root2):把s中的子集合Root2并入子集合Root1。要求Root1和Root2不相交，否则不执行

3.Find(S,x):查找集合S中单元素X所在的子集合，并返回该子集合的根节点

S表示一个森林，每个集合都是这森林中的一颗树

查的操作：

1.查一个元素属于哪个集合，从指定元素出发找到根节点

2.查两个元素是不是一个集合的，分别找这两个元素的根节点，相同就是同一个集合，否则不是

image-20250406173940456

并的操作：

两个集合并为一个集合，让一棵树成为另一棵树的子树

image-20250406174711383

使用双亲表示法更好实现并查集，会让查和并更好的实现

因为我们要实现查的操作要找根节点，那就是一级一级的去找父节点，找父节点自然是双亲表示法比较好了

而并的操作只需要让另外一个子树的根节点指向当前子树的根节点就好了

image-20250406175057715

并查集的存储结构

image-20250406175328850

并查集的代码实现

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
#define SIZE 13
int UFSets[SIZE];//集合元素数组 表示的是森林

//初始化并查集
void Inittial(int S[])
{
	for (int i = 0; i < SIZE; i++)
		s[i] = -1;
}

//Find 查操作，找x所属集合 返回x所属集合的根节点
int Find(int S[], int x)
{
	//循环寻找x的跟
	while (S[x] >= 0)
		x = S[X];
	//根的值是-1，小于0
	return x;
}

//Union 并操作，将两个集合并成一个
void Union(int S[], int Root1, int Root2)
{
	//要求Root1和Root2不是同一个子树
	if (Root1 == Root2)
		return;
	//把Root2接到Root1上面
	S[Root2] = Root1;
}

image-20250406180949137

Union优化

这个优化感觉很糟糕，因为一个子树的节点数量大并不能说明这个子树的高度就高

如果一个子树节点很多但所有结点全是根结点的孩子，那这棵树只有两层而已，另外一个节点少但是高度高的接过来反而高度比原来两个子树都更高，查找的就更慢了

image-20250406181105283

image-20250406182117770

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//Union优化 
void Union(int S[], int Root1, int Root2)
{
	//要求Root1和Root2不是同一个子树
	if (Root1 == Root2)
		return;
	//把Root2接到Root1上面
	if (S[Root2] > S[Root1]) {//Root2结点数更少
		S[Root1] += S[Root2];//累加结点总数
		S[Root2] = Root1;//小树合并到大树
	}
	else {
		S[Root2] += S[Root1];//累加结点总数
		S[Root1] = Root2;//小树合并到大树
	}
}
find优化：压缩路径

image-20250406182507435

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//Find“查”操作优化,先找到根节点,再进行“压缩路径”
int Find(int S[], int x) 
{
	int root = x;
	while (S[root] >= 0)
		root = S[root];//循环找到根
	//压缩路径
	while (x != root) 
	{
		//t指向x的父节点
		int t = S[x];
		//x直接挂到根节点下
		S[x] = root;
		x = t;
	}
	//返回根节点编号
	return root;
}

image-20250406182743744

image-20250406182809644

image-20250406183050612

每次将两个独立元素通过union的是时候都要找两个独立元素的根节点，然后才能进行合并，所以最终的构造一个并查集的复杂度和find的复杂度有关

然后n个元素要union进行n-1次，所以就是find的复杂度*n就是最后的复杂度

image-20250406183310861

对union小树接大树优化的困惑解答

在并查集的 union 操作优化中，按秩合并（Union by Rank） 的核心目标是通过合理的合并策略减少树的高度增长，从而提升后续 find 操作的效率。关于你提到的疑问（小树接大树 vs 高度低的接高度高的），以下是详细分析：

1.两种常见的“秩”定义

并查集的优化策略中，“秩”可以有两种定义方式：

  • 树的高度（Height）：表示以当前节点为根的树的最大深度。
  • 树的节点数量（Size）：表示以当前节点为根的树包含的节点总数。

两种定义各有优劣，但最终目标都是通过控制合并方向来减少树的高度。

2.为何“小树接大树”可以优化？

当选择 节点数量作为秩 时，合并策略是让节点数量少的树（小树）的根节点连接到节点数量多的树（大树）的根节点。这种优化策略的有效性体现在：

  • 合并后的树高度不会显著增加：如果小树的高度较大，但节点数量少，即使合并到大树上，大树原有的高度仍可能保持不变（除非两棵树高度相同）。例如：
    • 大树高度为 3，小树高度为 4，合并后大树高度仍为 4。
    • 但若大树高度为 4，小树高度为 3，合并后大树高度仍为 4。
  • 路径压缩的辅助优化：后续的find操作会通过路径压缩将树的高度压平，减少实际访问路径长度

3.“高度低的接高度高的”是否更优？

若选择 高度作为秩（即高度低的树合并到高度高的树），理论上可以避免合并后高度增加的问题。例如：

  • 大树高度为 3，小树高度为 2，合并后大树高度仍为 3。
  • 若两棵树高度相同，合并后新树高度加 1

但这种策略需要维护树高度的准确信息，而 路径压缩会破坏高度的实时性。

例如：路径压缩后，树的实际高度可能小于记录的秩（高度），导致合并时误判

4.两种策略的对比与选择

策略 优点 缺点
按节点数量（小树接大树） 合并后树的总高度增长较慢 可能出现小树高度 > 大树高度
按树高度（低接高） 严格避免合并后高度增加 需要维护精确高度，路径压缩后可能失效

实际应用中，优先选择按节点数量合并，原因如下：

  1. 实现简单：只需维护节点数量，无需频繁更新高度。
  2. 与路径压缩兼容：路径压缩会动态压平树结构，弥补合并导致的潜在高度增长
  3. 时间复杂度稳定：结合路径压缩和按秩合并，操作均摊时间接近常数

5.示例分析

假设两棵树：

  • 树A：节点数 100，高度 2。
  • 树B：节点数 5，高度 4。
  • 按节点数量合并（树B接树A）：
    • 合并后树A的高度仍为 4（因为树B的高度更高）。
    • 后续 find 操作通过路径压缩，将树B中原有长路径压平，最终实际高度可能降为 2。
  • 按高度合并（树A接树B）：
    • 合并后树B高度为 4，但需维护高度的准确性（路径压缩可能破坏这一信息）。

6.总结

按节点数量合并（小树接大树）是一种更稳健的优化策略，尤其在结合路径压缩后，能有效控制树的实际高度。虽然理论上可能出现小树高度大于大树的情况，但路径压缩的动态调整会抵消这种负面影响。而按高度合并的优化需要更复杂的高度维护，实际应用较少。