2022年考研数据结构_5 树

小咪咪 2022-12-31 05:23 261阅读 0赞

https://gitee.com/fakerlove/Data-Structure

### 文章目录 ###

*  5. 树
 *   *  5.1 概念
     *  5.2 二叉树
     *   *  5.2.1 树的定义和特征
         *   *  深度
         *  5.2.2 树的遍历
         *   *  1) 给出中后，输出前序
     *  5.3 树，森林
     *   *  5.3.1 树的存储结构
         *  5.3.2 森林与二叉树的转换
         *   *  1) 树转换为二叉树
             *  2) 森林转换为二叉树
             *  3) 二叉树转换为树
             *  4) 二叉树转换为森林
             *  5) 常见考点
         *  5.3.3 遍历
         *  5.3.4 线索二叉树
         *   *  产生背景
             *  解答
             *  线索二叉树结构实现
         *  5.3.5 二叉排序树（二叉查找树、二叉搜索树）
         *   *  1) 基本概念
             *   *  1.二叉排序树
             *  2) 二叉排序树操作
             *   *  (1)插入
                 *  (2)删除
                 *  (3)查询
                 *  (4)遍历
             *  3) 源码实现（C语言代码）
         *  5.3.6 平衡二叉树
         *   *  单选题
             *  选择题题解
             *  总结
         *  5.3.7 折半查找判定树
     *  5.4 应用
     *   *  1) 哈夫曼树(最优二叉树)
         *   *  一. 目的：
             *  二. 构造方法：
             *  三. 计算带权路径
         *  2) 常见考点

# 5. 树 #

## 5.1 概念 ##

## 5.2 二叉树 ##

### 5.2.1 树的定义和特征 ###

#### 深度 ####

![17e6430e023295121a82c2cbc75b2d41.png][]

**深度定义是从上往下的，高度定义是从下往上的。**

1.  高度就是深度
2.  看层数：  
    如果根结点第0，层数=深度=高度-1  
    如果根结点第1，层数=深度=高度

### 5.2.2 树的遍历 ###

#### 1) 给出中后，输出前序 ####

> 样例
> 
> //中序 GLDHBEIACJFK  
> //后序 LGHDIEBJKFCA

#include <iostream>
    #include <string.h>
    #include <stdlib.h>
    #define MAX 20 /*预定义字符数组的最大长度*/
    using namespace std;
    typedef struct tnode /*该结构体类型为树结点的类型*/
    {
        char data;
        struct tnode* lchild;
        struct tnode* rchild;
    } *bt;
    
    void in_post_to_bt(char* in, char* post, int len, bt& T) /*由长度为len的中序序列in和后序序列post唯一确定一棵二叉树T*/
    {
        int k;
        if (len <= 0)
        {
            T = NULL;
            return;
        }
        for (char* temp = in; temp < in + len; temp++) /*在中序序列in中找到根节点所在的位置*/
            if (*(post + len - 1) == *temp)
            {
                k = temp - in; /*k为根结点在中序序列中的下标*/
                T = (bt)malloc(sizeof(struct tnode));
                T->data = *temp;
                break;
            }
        in_post_to_bt(in, post, k, T->lchild); /*建立左子树*/
        in_post_to_bt(in + k + 1, post + k, len - k - 1, T->rchild); /*建立右子树*/
    }
    
    void in_visit(bt T) /*中序遍历树T*/
    {
        if (T)
        {
            in_visit(T->lchild);
            cout << T->data;
            in_visit(T->rchild);
        }
    }
    
    void post_visit(bt T) /*后序遍历树*/
    {
        if (T)
        {
            post_visit(T->lchild);
            post_visit(T->rchild);
            cout << T->data;
        }
    }
    
    int main()
    {
        //中序 GLDHBEIACJFK
        //后序 LGHDIEBJKFCA
        char in[MAX + 1], post[MAX + 1];
        cout << "输入中序序列：";
        cin >> in;
        cout << "输入后序序列：";
        cin >> post;
        bt T=(bt)malloc(sizeof(struct tnode));
        int len_in = strlen(in), len_post = strlen(post);
        if (len_in <= MAX && len_post <= MAX)
            in_post_to_bt(in, post, len_in, T);
        cout << endl
            << "输出中序序列：";
        in_visit(T);
        cout << endl
            << "输出后序序列：";
        post_visit(T);
        cout << endl;
        return 0;
    }

## 5.3 树，森林 ##

### 5.3.1 树的存储结构 ###

### 5.3.2 森林与二叉树的转换 ###

#### 1) 树转换为二叉树 ####

> 由于二叉树是有序的，为了避免混淆，对于无序树，我们约定树中的每个结点的孩子结点按从左到右的顺序进行编号。
> 
> 将树转换成二叉树的步骤是：  
> （1）加线。就是在所有兄弟结点之间加一条连线；  
> （2）抹线。就是对树中的每个结点，只保留他与第一个孩子结点之间的连线，删除它与其它孩子结点之间的连线；  
> （3）旋转。就是以树的根结点为轴心，将整棵树顺时针旋转一定角度，使之结构层次分明。

![img][]

#### 2) 森林转换为二叉树 ####

> 森林是由若干棵树组成，可以将森林中的每棵树的根结点看作是兄弟，由于每棵树都可以转换为二叉树，所以森林也可以转换为二叉树。
> 
> 将森林转换为二叉树的步骤是：  
> （1）先把每棵树转换为二叉树；  
> （2）第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子结点，用线连接起来。当所有的二叉树连接起来后得到的二叉树就是由森林转换得到的二叉树。

![img][img 1]

森林转换为二叉树的转换过程示意图

#### 3) 二叉树转换为树 ####

> 二叉树转换为树是树转换为二叉树的逆过程，其步骤是：  
> （1）若某结点的左孩子结点存在，将左孩子结点的右孩子结点、右孩子结点的右孩子结点……都作为该结点的孩子结点，将该结点与这些右孩子结点用线连接起来；  
> （2）删除原二叉树中所有结点与其右孩子结点的连线；  
> （3）整理（1）和（2）两步得到的树，使之结构层次分明。

![img][img 2]

#### 4) 二叉树转换为森林 ####

> 二叉树转换为森林比较简单，其步骤如下：  
> （1）先把每个结点与右孩子结点的连线删除，得到分离的二叉树；  
> （2）把分离后的每棵二叉树转换为树；  
> （3）整理第（2）步得到的树，使之规范，这样得到森林。

根据树与二叉树的转换关系以及二叉树的遍历定义可以推知，树的先序遍历与其转换的相应的二叉树的先序遍历的结果序列相同；树的后序遍历与其转换的二叉树的中序遍历的结果序列相同；树的层序遍历与其转换的二叉树的后序遍历的结果序列相同。由森林与二叉树的转换关系以及森林与二叉树的遍历定义可知，森林的先序遍历和中序遍历与所转换得到的二叉树的先序遍历和中序遍历的结果序列相同。

#### 5) 常见考点 ####

*  *森林F 中叶子结点的个数= 二叉树T中 左孩子指针为空的结点个数*

### 5.3.3 遍历 ###

> 某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）
> 
>  *      空或只有一个结点
>  *      高度等于其结点数
>  *      任一结点无左孩子
>  *      任一结点无右孩子
> 
> 正确答案：B
> 
> B 由于先序遍历是“根――左子树――右子树”，而后序遍历是“左子树――右子树――根”，若某二叉树的先序和后序序列正好相反，则该二叉树每层左、右子树只能有1个，即则该二叉树一定是高度等于其结点数。

1）若先序序列与后序序列相同,则或为空树,或为只有根结点的二叉树.  
2）若中序序列与后序序列相同,则或为空树,或为任一结点至多只有左子树的二叉树.  
（3）若先序序列与中序序列相同,则或为空树,或为任一结点至多只有右子树的二叉树.  
（4）若中序序列与层次遍历序列相同,则或为空树,或为任一结点至多只有右子树的二叉树

### 5.3.4 线索二叉树 ###

#### 产生背景 ####

> 现有一棵结点数目为n的二叉树，采用二叉链表的形式存储。对于每个结点均有指向左右孩子的两个指针域，而结点为n的二叉树一共有n-1条有效分支路径。那么，则二叉链表中存在2n-(n-1)=n+1个空指针域。那么，这些空指针造成了空间浪费。  
> 例如：图所示一棵二叉树一共有10个结点，空指针^有11个。

![img][img 3]

**问题提出**

此外，当对二叉树进行中序遍历时可以得到二叉树的中序序列。例如：图所示二叉树的中序遍历结果为HDIBJEAFCG，可以得知A的前驱结点为E，后继结点为F。但是，这种关系的获得是建立在完成遍历后得到的，那么可不可以在建立二叉树时就记录下前驱后继的关系呢，那么在后续寻找前驱结点和后继结点时将大大提升效率。

#### 解答 ####

通过考察各种二叉链表，不管儿叉树的形态如何，空链域的个数总是多过非空链域的个数。准确的说，n各结点的二叉链表共有2n个链域，非空链域为n-1个，但其中的空链域却有n+1个。如下图所示。

![img][img 4]

因此，提出了一种方法，利用原来的空链域存放指针，指向树中其他结点。这种指针称为线索。

记ptr指向二叉链表中的一个结点，以下是建立线索的规则：

（1）如果ptr->lchild为空，则存放指向中序遍历序列中该结点的前驱结点。这个结点称为ptr的中序前驱；

（2）如果ptr->rchild为空，则存放指向中序遍历序列中该结点的后继结点。这个结点称为ptr的中序后继；

显然，在决定lchild是指向左孩子还是前驱，rchild是指向右孩子还是后继，需要一个区分标志的。因此，我们在每个结点再增设两个标志域ltag和rtag，注意ltag和rtag只是区分0或1数字的布尔型变量，其占用内存空间要小于像lchild和rchild的指针变量。结点结构如下所示。

![img][img 5]

其中：

> （1）ltag为0时指向该结点的左孩子，为1时指向该结点的前驱；
> 
> （2）rtag为0时指向该结点的右孩子，为1时指向该结点的后继；
> 
> （3）因此对于上图的二叉链表图可以修改为下图的养子。

![img][img 6]

> 线索二叉树中某结点 R 没有左孩子的充要条件是（ ）。
> 
>  *      R.lchild=NULL
>  *      R.ltag=0
>  *      R.ltag=1
>  *      R.rchild=NULL
> 
> 正确答案：C
> 
> 通过考察各种二叉链表，不管儿叉树的形态如何，空链域的个数总是多过非空链域的个数。准确的说，**n各结点的二叉链表共有2n个链域，非空链域为n-1个，但其中的空链域却有n。**
> 
> 显然，在决定lchild是指向左孩子还是前驱，rchild是指向右孩子还是后继，需要一个区分标志的。+1个。因此，我们在每个结点再增设两个标志域ltag和rtag。
> 
> 其中：
> 
>  （1）ltag为0时指向该结点的左孩子，为1时指向该结点的前驱；
> 
>  （2）rtag为0时指向该结点的右孩子，为1时指向该结点的后继；

#### 线索二叉树结构实现 ####

二叉线索树存储结构定义如下：

/* 二叉树的二叉线索存储结构定义*/
    
    typedef enum
    { 
        Link,
        Thread
    } PointerTag; //Link = 0表示指向左右孩子指针；Thread = 1表示指向前驱或后继的线索
    
    typedef struct BitNode
    
    { 
    
        char data; //结点数据
    
        struct BitNode *lchild, *rchild; //左右孩子指针
    
        PointerTag Ltag; //左右标志
    
        PointerTag rtal;
    
    } BitNode, *BiTree;

线索化的实质就是将二叉链表中的空指针改为指向前驱或后继的线索。由于前驱和后继信息只有在遍历该二叉树时才能得到，所以，线索化的过程就是在遍历的过程中修改空指针的过程。

中序遍历线索化的递归函数代码如下：

BiTree pre; //全局变量，始终指向刚刚访问过的结点
    
    //中序遍历进行中序线索化
    
    void InThreading(BiTree p)
    
    { 
    
        if (p)
    
        { 
    
            InThreading(p->lchild); //递归左子树线索化
    
            //===
    
            if (!p->lchild) //没有左孩子
    
            { 
    
                p->ltag = Thread; //前驱线索
    
                p->lchild = pre; //左孩子指针指向前驱
            }
    
            if (!pre->rchild) //没有右孩子
    
            { 
    
                pre->rtag = Thread; //后继线索
    
                pre->rchild = p; //前驱右孩子指针指向后继(当前结点p)
            }
    
            pre = p;
    
            //===
    
            InThreading(p->rchild); //递归右子树线索化
        }
    }

上述代码除了//===之间的代码以外，和二叉树中序遍历的递归代码机会完全一样。只不过将打印结点的功能改成了线索化的功能。

中间部分代码做了这样的事情：

因为此时p结点的后继还没有访问到，因此只能对它的前驱结点pre的右指针rchild做判断，if(!pre->rchild)表示如果为空，则p就是pre的后继，于是pre->rchild = p，并且设置pre->rtag = Thread，完成后继结点的线索化。如图：

![img][img 7]

if(!p->lchild)表示如果某结点的左指针域为空，因为其前驱结点刚刚访问过，赋值了pre，所以可以将pre赋值给p->lchild，并修改p->ltag = Thread（也就是定义为1）以完成前驱结点的线索化。

![img][img 8]

完成前驱和后继的判断后，不要忘记当前结点p赋值给pre，以便于下一次使用。

有了线索二叉树后，对它进行遍历时，其实就等于操作一个双向链表结构。

![img][img 9]

和双向链表结点一样，在二叉树链表上添加一个头结点，如下图所示，并令其lchild域的指针指向二叉树的根结点（图中第一步），其rchild域的指针指向中序遍历访问时的最后一个结点（图中第二步）。反之，令二叉树的中序序列中第一个结点中，lchild域指针和最后一个结点的rchild域指针均指向头结点（图中第三和第四步）。这样的好处是：我们既可以从第一个结点起顺后继进行遍历，也可以从最后一个结点起顺前驱进行遍历。

![img][img 10]

遍历代码如下所示。

//t指向头结点，头结点左链lchild指向根结点，头结点右链rchild指向中序遍历的最后一个结点。
    
    //中序遍历二叉线索树表示二叉树t
    
    int InOrderThraverse_Thr(BiTree t)
    
    { 
    
        BiTree p;
    
        p = t->lchild; //p指向根结点
    
        while (p != t) //空树或遍历结束时p == t
    
        { 
    
            while (p->ltag == Link) //当ltag = 0时循环到中序序列的第一个结点
    
            { 
    
                p = p->lchild;
            }
    
            printf("%c ", p->data); //显示结点数据，可以更改为其他对结点的操作
    
            while (p->rtag == Thread && p->rchild != t)
    
            { 
    
                p = p->rchild;
    
                printf("%c ", p->data);
            }
    
            p = p->rchild; //p进入其右子树
        }
    
        return OK;
    }

说明：

（1）代码中，p = t->lchild；意思就是上图中的第一步，让p指向根结点开始遍历；  
（2）while(p != t)其实意思就是循环直到图中的第四步出现，此时意味着p指向了头结点，于是与t相等（t是指向头结点的指针），结束循环，否则一直循环下去进行遍历操作；  
（3）while(p-ltag == Link)这个循环，就是由A->B->D->H，此时H结点的ltag不是link（就是不等于0），所以结束此循环；  
（4）然后就是打印H；  
（5）while(p->rtag == Thread && p->rchild != t)，由于结点H的rtag = Thread（就是等于1），且不是指向头结点。因此打印H的后继D，之后因为D的rtag是Link，因此退出循环；  
（6）p=p->rchild；意味着p指向了结点D的右孩子I；  
（7）…，就这样不断的循环遍历，直到打印出HDIBJEAFCG，结束遍历操作。

从这段代码可以看出，它等于是一个链表的扫描，所以时间复杂度为O(n)。  
由于充分利用了空指针域的空间（等于节省了空间），又保证了创建时的一次遍历就可以终生受用后继的信息（意味着节省了时间）。所以在实际问题中，如果所用的二叉树需要经过遍历或查找结点时需要某种遍历序列中的前驱和后继，那么采用线索二叉链表的存储结构就是非常不错的选择。

#include <stdio.h>
    #include <stdlib.h>
    #define ERROR 0
    #define OK 1
    
    typedef enum
    { 
        Link,
        Thread
    } PointerTag; //link = 0表示指向左右孩子指针
    
    //Thread = 1表示指向前驱或后继的线索
    
    typedef struct BitNode
    { 
        char data;              //结点数据
        struct BitNode *lchild; //左右孩子指针
        struct BitNode *rchild;
        PointerTag ltag; //左右标志
    
        PointerTag rtag;
    
    } BitNode, *BiTree;
    
    BiTree pre; //全局变量，始终指向刚刚访问过的结点
    
    //前序创建二叉树
    
    void CreateTree(BiTree *t)
    
    { 
    
        char ch;
        scanf("%c", &ch);
        if (ch == '#')
        { 
            *t = NULL;
        }
    
        else
        { 
    
            (*t) = (BiTree)malloc(sizeof(BitNode));
            if ((*t) == NULL)
            { 
                return;
            }
            (*t)->data = ch;
            CreateTree(&((*t)->lchild));
            CreateTree(&((*t)->rchild));
        }
    }
    
    //t指向头结点，头结点左链lchild指向根结点，头结点右链rchild指向中序遍历的最后一个结点。
    
    //中序遍历二叉线索树表示的二叉树t
    
    int InOrderThraverse_Thr(BiTree t)
    { 
    
        BiTree p;
        p = t->lchild; //p指向根结点
        while (p != t)
        { 
    
            while (p->ltag == Link) //当ltag = 0时循环到中序序列的第一个结点
    
            { 
    
                p = p->lchild;
            }
    
            printf("%c ", p->data); //显示结点数据，可以更改为其他对结点的操作
            while (p->rtag == Thread && p->rchild != t)
            { 
                p = p->rchild;
                printf("%c ", p->data);
            }
    
            p = p->rchild; //p进入其右子树
        }
        return OK;
    }
    
    //中序遍历进行中序线索化
    
    void InThreading(BiTree p)
    { 
    
        if (p)
        { 
    
            InThreading(p->lchild); //递归左子树线索化
            if (!p->lchild)         //没有左孩子
            { 
    
                p->ltag = Thread; //前驱线索
    
                p->lchild = pre; //左孩子指针指向前驱,这里是第3步
            }
    
            if (!pre->rchild) //没有右孩子
    
            { 
    
                pre->rtag = Thread; //后继线索
    
                pre->rchild = p; //前驱右孩子指针指向后继(当前结点p)
            }
    
            pre = p;
    
            InThreading(p->rchild); //递归右子树线索化
        }
    }
    
    //建立头结点，中序线索二叉树
    
    int InOrderThread_Head(BiTree *h, BiTree t)
    
    { 
    
        (*h) = (BiTree)malloc(sizeof(BitNode));
    
        if ((*h) == NULL)
    
        { 
    
            return ERROR;
        }
    
        (*h)->rchild = *h;
    
        (*h)->rtag = Link;
    
        if (!t) //如果为NULL
    
        { 
    
            (*h)->lchild = *h;
    
            (*h)->ltag = Link;
        }
    
        else
    
        { 
    
            pre = *h;
    
            (*h)->lchild = t; //第一步
    
            (*h)->ltag = Link;
    
            InThreading(t); //找到最后一个结点
    
            pre->rchild = *h; //第四步
    
            pre->rtag = Thread;
    
            (*h)->rchild = pre; //第二步
        }
    }
    
    int main(int argc, char **argv)
    
    { 
    
        BiTree t;
    
        BiTree temp;
    
        printf("请输入前序二叉树的内容:\n");
    
        CreateTree(&t); //建立二叉树
    
        InOrderThread_Head(&temp, t); //加入头结点，并线索化
    
        printf("输出中序二叉树的内容:\n");
    
        InOrderThraverse_Thr(temp);
    
        printf("\n");
    
        return 0;
    }

### 5.3.5 二叉排序树（二叉查找树、二叉搜索树） ###

#### 1) 基本概念 ####

##### 1.二叉排序树 #####

二叉排序树（Binary sort tree，BST），又称为二叉查找树，或者是一棵空树；或者是具有下列性质的二叉树：

(1)若它的左子树不为空，则左子树上所有节点的值均小于它的根节点的值；

(2)若它的右子树不为空，则右子树上所有节点的值均大于它的根节点的值；

(3)它的左、右子树也分别为二叉排序树。

#### 2) 二叉排序树操作 ####

二叉排序树是一种动态树表。它的特点是树的结构不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的节点时再进行插入。新插入的节点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个节点的左孩子或右孩子节点，

二叉排序树的操作有插入、删除、查询和遍历等。

注意：二叉排序树中没有值相同的节点

##### (1)插入 #####

a.插入过程比较简单，首先判断当前要插入的值是否已经存在二叉排序树中，如果已经存在，则直接返回；如果不存在，则转b;

b.当前要插入的值不存在，则应找到适当的位置，将其插入。注意插入的新节点一定是叶子节点；

![img][img 11]

##### (2)删除 #####

a.和插入一样，要删除一个给定值的节点，首先要判断这样节点是否存在，如果已经不存在，则直接返回；如果已经存在，则获取给定值节点的位置，根据不同情况进行删除、调整，转b；

b.如果待删节点只有左子树（只有右子树），则直接将待删节点的左子树（右子树）放在待删节点的位置，并释放待删节点的内存,否则转c;

![img][img 12]

c.如果待删节点既有左子树又有右子树，此时的删除可能有点复杂，但是也比较好理解。就是在待删节点的左子树中找到值最大的那个节点，将其放到待删节点的位置。

![img][img 13]

![img][img 14]

##### (3)查询 #####

查询过程比较简单，首先将关键字和根节点的关键字比较，如果相等则返回节点的位置(指针)；否则，如果小于根节点的关键字，则去左子树中继续查找；如果大于根节点的关键字，则去右子树中查找；如果找到叶子节点也没找到，则返回NULL。

查询过程的最好情况就是上面的图中那样，节点在左右子树中分布比较均匀，此时查找的时间复杂度为O(logn)；最坏的情况就是在建立二叉排序树时，输入的关键字序列正好是有序的，此时形成的二叉排序树是一棵单支二叉树，此时查找退化成了单链表的查找，时间的复杂度为O(n).如下图：

![img][img 15]

##### (4)遍历 #####

由上面二排序树的定义可知，左子树的所有值均小于根节点，右子树的所有值均大于根节点，而这个特点正好和二叉树的中序遍历中–左子树->根节点->右子树不谋而合，所以对二叉排序树进行中序遍历得到的正好是一个有序的

#### 3) 源码实现（C语言代码） ####

#include <stdio.h>
    #include <stdlib.h>
    //二叉排序树
     
    typedef struct BSTNode
    { 
    	int data;
    	BSTNode *lchild;  //左孩子
    	BSTNode *rchild;  //右孩子
    }BSTNode, *BSTree;
     
    bool Search(BSTree bst, int key, BSTree f, BSTree *p);
     
    void InOderTraverse(BSTree bst)   //中序递归遍历二叉树
    { 
    	if (NULL != bst)
    	{ 
    		InOderTraverse(bst->lchild);
    		printf("%d ", bst->data);
    		InOderTraverse(bst->rchild);
    	}
    }
     
    static BSTNode* BuyNode(int data)   //生成一个节点并进行初始化
    { 
    	BSTNode *pTmp = (BSTNode*)malloc(sizeof(BSTNode));
    	if (NULL == pTmp)
    	{ 
    		exit(0);
    	}
    	pTmp->data = data;
    	pTmp->lchild = NULL;
    	pTmp->rchild = NULL;
    	return pTmp;
    }
     
    bool Insert(BSTree *bst, int key)
    { 
    	if (NULL == *bst)  //空树
    	{ 
    		*bst = BuyNode(key);   //插入根节点
    		return true;
    	}
    	BSTNode *p;
    	//先在二叉排序树中查找要插入的值是否已经存在
    	if (!Search(*bst, key, NULL, &p))  //如果查找失败，则插入；此时p指向遍历的最后一个节点
    	{ 
    		BSTNode *pNew = BuyNode(key);
    		if (key < p->data)  //将s作为p的左孩子
    		{ 
    			p->lchild = pNew;
    		}
    		else if (key > p->data)  //将s作为p的右孩子
    		{ 
    			p->rchild = pNew;
    		}
    		return true;  //插入成功
    	}
    	else
    	{ 
    		printf("\nThe node(%d) already exists.\n", key);
    	}
    	return false;
    }
     
    /* 删除分三种情况： (1)被删除的节点无孩子，说明该节点是叶子节点，直接删 (2)被删除的节点只有左孩子或者右孩子，直接删，并将其左孩子或者右孩子放在被删节点的位置 (3)被删除的节点既有右孩子又有右孩子 */
     
    BSTNode* FindParent(BSTree bst, BSTNode *child)
    { 
    	if (NULL == bst)
    	{ 
    		return NULL;
    	}
     
    	if (bst->lchild == child || bst->rchild == child)
    	{ 
    		return bst;
    	}
    	else if(NULL != bst->lchild)
    	{ 
    		FindParent(bst->lchild, child);
    	}
    	else if (NULL != bst->rchild)
    	{ 
    		FindParent(bst->rchild, child);
    	}
    }
     
    void Delete(BSTree *bst, int key)
    { 
    	if (NULL == *bst)
    	{ 
    		exit(1);  //空树直接报错
    	}
    	BSTNode *p;
    	BSTNode *f = NULL;
    	BSTNode *q, *s;
    	if (Search(*bst, key, NULL, &p)) //确实存在值为key的节点,则p指向该节点
    	{ 
     
    		if (NULL == p->lchild && NULL != p->rchild)  //无左孩子,有右孩子
    		{ 
    			q = p->rchild;
    			p->data = q->data;    //因为两个节点之间本质的不同在于数据域的不同，而与放在哪个地址没有关系
    			p->rchild = q->rchild;
    			p->lchild = q->lchild;
    			free(q);
    		}
    		else if (NULL == p->rchild && NULL != p->lchild)  //无右孩子,有左孩子
    		{ 
    			q = p->lchild;
    			p->data = q->data;
    			p->rchild = q->rchild;
    			p->lchild = q->lchild;
    			free(q);
    		}
    		else if (NULL != p->rchild && NULL != p->lchild) //既有左孩子，又有右孩子
    		{ 
    			q = p;
    			s = p->lchild;   //找左孩子的最右孩子
    			while (s->rchild)
    			{ 
    				q = s;
    				s = s->rchild;
    			}
    			p->data = s->data;
     
    			if (q != p)
    			{ 
    				q->rchild = p->lchild;
    			}
    			else
    			{ 
    				q->lchild = s->lchild;
    			}
    			free(s);
    		}
    		else
    		{ 
    			if (*bst == p)   //只有一个根节点
    			{ 
    				free(*bst);
    				*bst = NULL;
    				return;
    			}
     
    			BSTNode* parent = FindParent(*bst, p);
    			if (parent->lchild == p)
    			{ 
    				parent->lchild = NULL;
    			}
    			else
    			{ 
    				parent->rchild = NULL;
    			}
    			free(p);
    		}
    	}
    }
     
    bool Search(BSTree bst, int key, BSTree f, BSTree *p)  //查找成功时，p指向值为key的节点。如果查找失败，则p指向遍历的最后一个节点
    { 
    	if (!bst)
    	{ 
    		*p = f;
    		return false;
    	}
    	if (bst->data == key)  //查找成功，直接返回
    	{ 
    		*p = bst;
    		return true;
    	}
    	else if (bst->data < key)
    	{ 
    		return Search(bst->rchild, key, bst, p);
    	}
    	return Search(bst->lchild, key, bst, p);
    }
     
    int main(void)
    { 
    	BSTNode *root = NULL;
    	Insert(&root, 45);
    	Insert(&root, 24);
    	Insert(&root, 53);
    	Insert(&root, 12);
    	Insert(&root, 90);
    	InOderTraverse(root);
    	printf("\n%d ", Insert(&root, 45));   //输出0表示插入失败，输出1表示插入成功
    	printf("%d\n", Insert(&root, 4));
    	InOderTraverse(root);
    	printf("\n");
    	Delete(&root, 4);      //删除节点45
    	Delete(&root, 45);      //删除节点45
    	Delete(&root, 24);      //删除节点45
    	Delete(&root, 53);      //删除节点45
    	Delete(&root, 12);      //删除节点45
    	Delete(&root, 90);      //删除节点45
    	InOderTraverse(root);
    	return 0;
    }

运行结果：

### 5.3.6 平衡二叉树 ###

平衡二叉搜索树，又被称为AVL树，且具有以下性质：**它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。**

由于普通的二叉查找树会容易失去”平衡“，极端情况下，二叉查找树会退化成线性的链表，导致插入和查找的复杂度下降到 O(n) ，所以，这也是平衡二叉树设计的初衷。那么平衡二叉树如何保持”平衡“呢？根据定义，有两个重点，一是左右两子树的高度差的绝对值不能超过1，二是左右两子树也是一颗平衡二叉树。

如下图所示，左图是一棵平衡二叉树，根节点10，左右两子树的高度差是1，而右图，虽然根节点左右两子树高度差是0，但是右子树15的左右子树高度差为2，不符合定义，所以右图不是一棵平衡二叉树。

![是否为平衡二叉树例图][fb6ca2c80c48536ca437535a9d38e4df.png]

由此可以看出平衡二叉树是一棵高度平衡的二叉查找树。所以，要构建跟维系一棵平衡二叉树就比普通的二叉树要复杂的多。在构建一棵平衡二叉树的过程中，当有新的节点要插入时，检查是否因插入后而破坏了树的平衡，如果是，则需要做旋转去改变树的结构。

关于旋转，这东西不拿动态图将还真很难讲明白。所以我就借一下 [最容易懂得红黑树][Link 1] 这篇文章中左旋右旋的图来讲。

**左旋**：

![左旋][4e03038f939e574dcb1e6822cbb41aee.png]

**右旋**：

![右旋][b7e4ac756006a6224c682dd66978be7d.png]

不同于顺时针跟逆时针变换这种方式去记忆，上面两个动态图特别方便记忆跟理解：

**左旋就是将节点的右支往左拉，右子节点变成父节点，并把晋升之后多余的左子节点出让给降级节点的右子节点；**

**而右旋就是反过来，将节点的左支往右拉，左子节点变成了父节点，并把晋升之后多余的右子节点出让给降级节点的左子节点。**

**即左旋就是往左变换，右旋就是往右变换。不管是左旋还是右旋，旋转的目的都是将节点多的一支出让节点给另一个节点少的一支**。

举个例子，像上图是否平衡二叉树的图里面，左图在没插入前”19“节点前，该树还是平衡二叉树，但是在插入”19“后，导致了”15“的左右子树失去了”平衡“，所以此时可以将”15“节点进行左旋，让”15“自身把节点出让给”17“作为”17“的左树，使得”17“节点左右子树平衡，而”15“节点没有子树，左右也平衡了。如下图，

![非平衡二叉树左旋变换成平衡二叉树例图][909a8404fe650fe2466350996b3dd3f5.png]

由于在构建平衡二叉树的时候，当有**新节点插入**时，都会判断插入后时候平衡，这说明了插入新节点前，都是平衡的，也即高度差绝对值不会超过1。当新节点插入后，有可能会有导致树不平衡，这时候就需要进行调整，而可能出现的情况就有4种，分别称作**左左，左右，右左，右右**。

**左左**：

![平衡二叉树失衡情况之左左][10cb8088581d4520d3b39ad6fb7a076d.png]

左左即为在原来平衡的二叉树上，在**节点的左子树的左子树下**，有新节点插入，导致节点的左右子树的高度差为2，如上即为”10“节点的左子树”7“，的左子树”4“，插入了节点”5“或”3“导致失衡。

左左调整其实比较简单，只需要对节点进行右旋即可，如下图，对节点”10“进行右旋，

注意：如果对左右旋变换还不是很懂或不是很熟练的，可以对照着前面的那两个动图去想象，自己动手变换几次，就明白了。

![平衡二叉树左左情况进行右旋][ce979f1814466ba65ed3bfd31cfc88ab.png]

**左右**：

![平衡二叉树失衡情况之左右][805c31c9af11c470ddeac7bff81091ec.png]

左右即为在原来平衡的二叉树上，在**节点的左子树的右子树**下，有新节点插入，导致节点的左右子树的高度差为2，如上即为”11“节点的左子树”7“，的右子树”9“，插入了节点”10“或”8“导致失衡。

左右的调整就不能像左左一样，进行一次旋转就完成调整。我们不妨先试着让左右像左左一样对”11“节点进行右旋，结果图如下，右图的二叉树依然不平衡，而右图就是接下来要讲的右左，即左右跟右左互为镜像，左左跟右右也互为镜像。

![平衡二叉树左右情况右旋错误示范][3ddecea3faff511e5b332ada26be293c.png]

**右右跟左左一样，只需要旋转一次就能把树调整平衡，而左右跟右左也一样，都要进行旋转两次才能把树调整平衡**，所以，首先上图的这种调整是错误的，正确的调整方式是，将左右进行第一次旋转，将左右先调整成左左，然后再对左左进行调整，从而使得二叉树平衡。

即先对上图的节点”7“进行左旋，使得二叉树变成了左左，之后再对”11“节点进行右旋，此时二叉树就调整完成，如下图，

![平衡二叉树左右情况进行左旋再右旋][fb80715bb3f1f6fac9c73aac815cc2db.png]

**右左**：

![平衡二叉树失衡情况之右左][cdc54cf60fa92d2019b09598df468368.png]

右左即为在原来平衡的二叉树上，在节点的右子树的左子树下，有新节点插入，导致节点的左右子树的高度差为2，如上即为”11“节点的右子树”15“，的左子树”13“，插入了节点”12“或”14“导致失衡。

前面也说了，右左跟左右其实互为镜像，所以调整过程就反过来，先对节点”15“进行右旋，使得二叉树变成右右，之后再对”11“节点进行左旋，此时二叉树就调整完成，如下图，

![平衡二叉树右左情况进行右旋再左旋][34b95ccfd54b6241f12b1c473035e43f.png]

**右右**：

![平衡二叉树失衡情况之右右][46a69558655fe039d63bc845c3fa5f42.png]

右右即为在原来平衡的二叉树上，在节点的右子树的右子树下，有新节点插入，导致节点的左右子树的高度差为2，如上即为”11“节点的右子树”13“，的左子树”15“，插入了节点”14“或”19“导致失衡。

右右只需对节点进行一次左旋即可调整平衡，如下图，对”11“节点进行左旋。

![平衡二叉树右右情况进行左旋][774ec709c8e987bdd174c75a57544b27.png]

平衡二叉树构建的过程，就是节点插入的过程，插入失衡情况就上面4种，算简单了，下面讲下**平衡二叉树节点的删除**，删除的情况会复杂一点，复杂的原因主要在于删除了节点之后要维系二叉树的平衡，但是删除二叉树节点总结起来就两个判断：**①删除的是什么类型的节点？②删除了节点之后是否导致失衡？**

节点的类型有三种：1.叶子节点；2.只有左子树或只有右子树；3.既有左子树又有右子树。

针对这三种节点类型，再引入判断②，所以**处理思路**分别是：

（1）当删除的节点是叶子节点，则将节点删除，然后从父节点开始，判断是否失衡，如果没有失衡，则再判断父节点的父节点是否失衡，直到根节点，此时到根节点还发现没有失衡，则说此时树是平衡的；如果中间过程发现失衡，则判断属于哪种类型的失衡（左左，左右，右左，右右），然后进行调整。

（2）删除的节点只有左子树或只有右子树，这种情况其实就比删除叶子节点的步骤多一步，就是将节点删除，然后把仅有一支的左子树或右子树替代原有结点的位置，后面的步骤就一样了，从父节点开始，判断是否失衡，如果没有失衡，则再判断父节点的父节点是否失衡，直到根节点，如果中间过程发现失衡，则根据失衡的类型进行调整。

（3）删除的节点既有左子树又有右子树，这种情况又比上面这种多一步，就是中序遍历，找到待删除节点的前驱或者后驱都行，然后与待删除节点互换位置，然后把待删除的节点删掉，后面的步骤也是一样，判断是否失衡，然后根据失衡类型进行调整。

最后总结一下，平衡二叉树是一棵高度平衡的二叉树，所以**查询的时间复杂度是 O(logN)** 。**插入**的话上面也说，失衡的情况有4种，左左，左右，右左，右右，即一旦插入新节点导致失衡需要调整，**最多也只要旋转2次**，所以，**插入复杂度是 O(1)** ，但是平衡二叉树也不是完美的，也有**缺点**，从上面删除处理思路中也可以看到，就是**删除节点时有可能因为失衡，导致需要从删除节点的父节点开始，不断的回溯到根节点，如果这棵平衡二叉树很高的话，那中间就要判断很多个节点**。所以后来也出现了综合性能比其更好的树—-**红黑树**，后面再讲。

#### 单选题 ####

<table> 
 <thead> 
  <tr> 
   <th>题号</th> 
   <th>题目</th> 
   <th>答案</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>1</td> 
   <td>AVL树是一种平衡的二叉搜索树，树中任一结点具有下列哪一特性：</td> 
   <td>左、右子树高度差的绝对值不超过1</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td><img src="https://img-blog.csdnimg.cn/img_convert/3078484b0863a05c8dbdd75044426a27.png" alt="在这里插入图片描述"></td> 
   <td>C</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>在下列所示的平衡二叉树中，插入关键字48后得到一棵新平衡二叉树。在新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是： <img src="https://img-blog.csdnimg.cn/img_convert/db0963a9026b3ec43f4f78d166863627.png" alt="在这里插入图片描述"></td> 
   <td>24、53</td> 
  </tr> 
  <tr> 
   <td>4</td> 
   <td>12个结点的AVL树的最大深度是？</td> 
   <td>5</td> 
  </tr> 
  <tr> 
   <td>5</td> 
   <td>若AVL树的深度是6（空树的深度定义为-1），则该树的最少结点数是：</td> 
   <td>33</td> 
  </tr> 
  <tr> 
   <td>6</td> 
   <td>将 8, 9, 7, 2, 3, 5, 6, 4 顺序插入一棵初始为空的AVL树。下列句子中哪句是错的？<img src="https://img-blog.csdnimg.cn/img_convert/da2d377f22065b0f6da29c1b2dbf1185.png" alt="在这里插入图片描述"></td> 
   <td>C</td> 
  </tr> 
  <tr> 
   <td>7</td> 
   <td>将一系列数字顺序一个个插入一棵初始为空的AVL树。下面哪个系列的第一次旋转是“右-左”双旋？<img src="https://img-blog.csdnimg.cn/img_convert/00e14d7b1731fb1ca1d856126b7fa24e.png" alt="在这里插入图片描述"></td> 
   <td>D</td> 
  </tr> 
  <tr> 
   <td>8</td> 
   <td>将 1, 2, 3, 6, 5, 4 顺序一个个插入一棵初始为空的AVL树，会经历下列哪些旋转？</td> 
   <td>一个“右-右”旋和两个“右-左”旋</td> 
  </tr> 
  <tr> 
   <td>9</td> 
   <td><img src="https://img-blog.csdnimg.cn/img_convert/963ca5ee44af71b400de54e11ecd8f3a.png" alt="在这里插入图片描述"></td> 
   <td>A</td> 
  </tr> 
  <tr> 
   <td>10</td> 
   <td>首先将 28, 23, 54, 61, 98, 37 插入一棵初始为空的平衡二叉树（AVL树），然后马上插入下列选项中的一个键值。哪个键值将引起 RL 旋转？</td> 
   <td>70</td> 
  </tr> 
 </tbody> 
</table>

#### 选择题题解 ####

2、如图所示  
![在这里插入图片描述][d57c2ec22505c82f457a61a45e460f67.png]  
3、转的过程：

*  插入48之后属于右左双旋转的情况，按照图示的方法先做右单旋转，再做左单旋转
 *  右单旋转：以37为轴，53顺时针旋转（向下），原本是37左孩子的48成为53的左孩子
 *  24的右孩子由53变为37
 *  左单旋转：仍然以37为轴，24逆时针旋转（向下），成为37的左孩子![在这里插入图片描述][4bee7c3fcf5c492df9ee16f283a08120.png]  
    24的左子树高度为1，右字数高度为3，属于RL型，RL型的变化就这么做的，具体RL型解释如下  
    ![在这里插入图片描述][0d7018eb9e337b0ed57c60b3911c55f2.png]  
    具体的RL型的旋转规则，大佬说记住就可以了，哎拼命记吧。  
    ![在这里插入图片描述][37235d9029cc7400b633df034fd76d86.png]

#### 总结 ####

高度为h 的最小平衡二叉树的节点数 N n = N n − 1 + N n − 2 + 1 , N 0 = 0 , N 1 = 1 N\_n=N\_\{n-1\}+N\_\{n-2\}+1,N\_0=0,N\_1=1 Nn=Nn−1\+Nn−2\+1,N0=0,N1=1

### 5.3.7 折半查找判定树 ###

长度为n的折半查找判定树的构造方法为：

⑴ 当n=0时，折半查找判定树为空；bai

⑵ 当n＞0时，折半查找判定树的根结点是有序表中序号为mid=(n+1)/2的记录，根结点的左子树是与有序表r\[1\] ~ r\[mid-1\]相对应的折半查找判定树，根结点的右子树是与r\[mid+1\] ~ r\[n\]相对应的折半查找判定树。

题目中 长度为10的折半查找判定树的具体生成过程为：

⑴ 在长度为10的有序表中进行折半查找，不论查找哪个记录，都必须先和中间记录进行比较，而中间记录的序号为(1+10)/2=5（注意是整除即向下取整），即判定树的根结点是5，如图(a)所示；

![a9135ba566c80519929db211c07bb77e.png][]

⑵ 考虑判定树的左子树，即将查找区间调整到左半区，此时的查找区间是\[1，4\]，也就是说，左分支上为根结点的值减1，代表查找区间的高端high，此时，根结点的左孩子是(1+4)/2=2，如图(b)所示；

![da9a9e69eba131dfc174ae8093d7c3f0.png][]

![3fd971535035bc4ec4a8a69ed7edb7ae.png][]

⑷ 重复⑵⑶步，依次确定每个结点的左右孩子，如图(d)所示。

![22863936c849d0ccbe33a472a312418a.png][]

## 5.4 应用 ##

### 1) 哈夫曼树(最优二叉树) ###

#### 一. 目的： ####

*找出*存放一串字符所需的最少的二进制编码

*带权路径最短*

#### 二. 构造方法： ####

**首先统计出每种字符出现的*频率*！（也可以是概率）权值**

--------------------

**例如：*频率表* A：60, B:45, C:13 D:69 E:14 F:5 G:3**

第一步：找出字符中最小的两个，小的在左边，大的在右边，组成二叉树。在\*\**频率表**中删除**此次找到的两个数，并加入此次最小两个数的频率和。*

*F和G*最小，因此如图，从字符串频率计数中删除*F*与*G，并返回G*与*F*的和 *8*给*频率表*\*\*

![img][img 16]

**重复第一步：**

--------------------

***频率表* A：60, B:45, C:13 D:69 E:14 FG:8**

最小的是 ***FG：8\*\*\*与\*C：13，因此如图，并返回FGC的和：21给频率表。***

![img][img 17]

重复第一步：

--------------------

***频率表* A：60 B: 45 D: 69 E: 14 FGC: 21**

**如图**

![img][img 18]

**-----------------------------------------------------------------------------------------------------**

重复第一步

**-----------------------------------------------------------------------------------------------------**

***频率表* A：60 B: 45 D: 69 FGCE: 35**

![img][img 19]

**-----------------------------------------------------------------------------------------------------**

重复第一步

**-----------------------------------------------------------------------------------------------------**

***频率表* A：60 D: 69 FGCEB: 80**

![img][img 20]

**-----------------------------------------------------------------------------------------------------**

重复第一步

**-----------------------------------------------------------------------------------------------------**

***频率表* AD：129 FGCEB: 80**

![img][img 21]

**添加 0 和 1，规则左0 右1**

![img][img 22]

***频率表* A：60, B:45, C:13 D:69 E:14 F:5 G:3**

**每个 字符 的 二进制编码 为（从根节点 数到对应的叶子节点，路径上的值拼接起来就是叶子节点字母的应该的编码）**

#### 三. 计算带权路径 ####

哈夫曼树是一种带权路径长度最短的二叉树，也称为最优二叉树。下面用一幅图来说明。

![img][img 23]

它们的带权路径长度分别为：

图a： WPL=5\*2+7\*2+2\*2+13\*2=54

图b： WPL=5\*3+2\*3+7\*2+13\*1=48

可见，图b的带权路径长度较小，我们可以证明图b就是哈夫曼树(也称为最优二叉树)。

### 2) 常见考点 ###

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>已知完全二叉树总结点数 N，求叶子结点数 n？</td> 
   <td><em><strong>如果是偶数个节点，叶子节点等于总节点除以2， 即 N % 2==0， n = N/2<br>如果是奇数个叶子节点等于(总节点+1)除以2, 即 N % 2 == 1, n = (N+1)/2</strong></em></td> 
  </tr> 
  <tr> 
   <td>已知完全二叉树叶子结点数n, 求总结点数N？</td> 
   <td><em><strong>2n</strong></em></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><em><strong>哈夫曼树是二叉树，所有符合的都是叶子节点，设叶子节点个数为m,则，生成的哈夫曼树结点个数为2m-1</strong></em></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

[17e6430e023295121a82c2cbc75b2d41.png]: /images/20221120/613c8aa5c56544f6ba6cea20fcc5f480.png
[img]: /images/20221120/3b89f13b349e491b92391ccf39cec904.png
[img 1]: /images/20221120/f1d5f74f851249baa7711b81be6bd12b.png
[img 2]: /images/20221120/8a81e7963c7441af9ab68f78c4dc0c90.png
[img 3]: /images/20221120/82665966b7574047ad02c132a09b4108.png
[img 4]: /images/20221120/284748998c4746fd9d25bfaf157b14cd.png
[img 5]: /images/20221120/c4ac636a5ee34758a560b35d5422e5cd.png
[img 6]: /images/20221120/90aa3963ae96431b9931d85e65db9c52.png
[img 7]: /images/20221120/7b6491e0646c495394202cf0a5903059.png
[img 8]: /images/20221120/b47e096c1abe44a48ad894d346d4b336.png
[img 9]: /images/20221120/fefbde6e6a6c469db2d8f6fd4a9862df.png
[img 10]: /images/20221120/b6aabc8c1dcf45af81b2110976cec0e0.png
[img 11]: /images/20221120/c639a1603b864115bcfc346b1a147cfe.png
[img 12]: /images/20221120/bb0663f6d21b4d6c942b2ea64a583c9c.png
[img 13]: /images/20221120/9414ab4194764a4cad23e3fffe69de96.png
[img 14]: /images/20221120/af3271340ff14a449de124918295a8f2.png
[img 15]: /images/20221120/1aca85f561914535801ce6c20d0b73d8.png
[fb6ca2c80c48536ca437535a9d38e4df.png]: /images/20221120/ce6f5df3f5b34d4994fa920a4ea933aa.png
[Link 1]: https://blog.csdn.net/sun_tttt/article/details/65445754
[4e03038f939e574dcb1e6822cbb41aee.png]: /images/20221120/c6149f924eb74974b24a5536e3a85e97.png
[b7e4ac756006a6224c682dd66978be7d.png]: /images/20221120/2c314bddaff240309aef51445eb361d6.png
[909a8404fe650fe2466350996b3dd3f5.png]: /images/20221120/a4f56433eada4bbb83acecb5a367b952.png
[10cb8088581d4520d3b39ad6fb7a076d.png]: /images/20221120/9038f3c6dc3245abbf4ff0f5a14007c4.png
[ce979f1814466ba65ed3bfd31cfc88ab.png]: /images/20221120/f8142d64fc8c44079ee33ce688b4e27b.png
[805c31c9af11c470ddeac7bff81091ec.png]: /images/20221120/c80e9edaac2543cda726a0f001d235ac.png
[3ddecea3faff511e5b332ada26be293c.png]: /images/20221120/c2cc41d0318c4cf3890cdd1007d2ba89.png
[fb80715bb3f1f6fac9c73aac815cc2db.png]: /images/20221120/5b722e95b53a45388eac7a8d5d730fbb.png
[cdc54cf60fa92d2019b09598df468368.png]: /images/20221120/afffc135d94447e995f95abb0fe2b0ee.png
[34b95ccfd54b6241f12b1c473035e43f.png]: /images/20221120/1d7b67f60d4e4b05b88052e278cc816e.png
[46a69558655fe039d63bc845c3fa5f42.png]: /images/20221120/0db73614e7a9458f937eec96510a49cf.png
[774ec709c8e987bdd174c75a57544b27.png]: /images/20221120/4ef4fbf4224640e3bdb7df77c1fd64f1.png
[d57c2ec22505c82f457a61a45e460f67.png]: /images/20221120/a4edc135b3084135875fffaaa9f75df4.png
[4bee7c3fcf5c492df9ee16f283a08120.png]: /images/20221120/17726f1b13f34953825a75c1b2e1932b.png
[0d7018eb9e337b0ed57c60b3911c55f2.png]: /images/20221120/55961b2745994432a1db721f93ff56c4.png
[37235d9029cc7400b633df034fd76d86.png]: /images/20221120/77389a6e0d8e409781eeceb9faaceff2.png
[a9135ba566c80519929db211c07bb77e.png]: /images/20221120/3b90e414f09d49769672016062e918c8.png
[da9a9e69eba131dfc174ae8093d7c3f0.png]: /images/20221120/b107c403fbe141d7bcad3d79a90c90a7.png
[3fd971535035bc4ec4a8a69ed7edb7ae.png]: /images/20221120/60756d99b2a44534aa3c142e0786f0b6.png
[22863936c849d0ccbe33a472a312418a.png]: /images/20221120/01efed5b4ec242919e87fc3740d62946.png
[img 16]: /images/20221120/d95eb7c2f6e74727a164311b1029181c.png
[img 17]: /images/20221120/d60a45929ea344bf82ad35f336e5c422.png
[img 18]: /images/20221120/7d438dd0d0d04cb495c65f0765062f6e.png
[img 19]: /images/20221120/0a6384d3ec6e4d83b17db8b737b30d51.png
[img 20]: /images/20221120/b9e4d638810348269fa3d2eb00c4da0b.png
[img 21]: https://img-blog.csdnimg.cn/img_convert/fb58fe565eebb99ed4a9eb2167d5f934.png
[img 22]: https://img-blog.csdnimg.cn/img_convert/e1df2204dbde2b7e38da64a0ea05e9ca.png
[img 23]: https://img-blog.csdnimg.cn/img_convert/10544539b9c3eab1a8647a0dea9acc1b.png