[数据结构考研][4][树与二叉树]

1. 第四章 树与二叉树
   1. 4.1 树的基本概念
      1. 4.1.1 树的定义
      2. 4.1.2 基本术语
      3. 4.1.3 树的性质
   2. 4.2 二叉树的概念
      1. 4.2.1 二叉树的定义及其主要特性
         1. 1 二叉树的定义
         2. 2 几个特殊的二叉树
         3. 3 二叉树的性质
      2. 4.2.2 二叉树的存储结构
         1. 1 顺序存储结构
         2. 2 链式存储结构
   3. 4.3 二叉树的遍历和线索二叉树
      1. 4.3.1 二叉树的遍历
         1. 1 先序遍历(PreOrder)
         2. 2 中序遍历
         3. 3 后序遍历
         4. 4 递归算法与非递归算法的转换
         5. 5 层次遍历
         6. 6 由遍历构造二叉树
      2. 4.3.2 线索二叉树
         1. 1 线索二叉树的基本概念
         2. 2 线索二叉树的构造
         3. 3 线索二叉树的遍历
   4. 4.4 树、森林
      1. 4.4.1 树的存储结构
         1. 1 父亲表示法
         2. 2 孩子表示法
         3. 3 孩子兄弟表示法
      2. 4.4.2 树、森林和二叉树的转换
      3. 4.4.3 树和森林的遍历
         1. 1 树的遍历
         2. 2 森林的遍历
      4. 4.4.5 树的应用–并查集
   5. 4.5 树与二叉树的应用
      1. 4.5.1 二叉排序树
         1. 1 二叉排序树的定义
         2. 2 二叉排序树的查找
         3. 3 二叉排序树的插入
         4. 4 二叉排序树的构建
         5. 5 二叉排序树的删除
         6. 6 二叉排序树的查找效率分析
      2. 4.5.2 平衡二叉树
         1. 1 平衡二叉树的定义
         2. 2 平衡二叉树的插入
         3. 3 平衡二叉树的查找
      3. 4.5.3 哈夫曼树和哈夫曼编码
         1. 1 哈夫曼树的定义
         2. 2 哈夫曼树的构建
         3. 3 哈夫曼编码

第四章 树与二叉树

digraph demo{
    树形结构->二叉树[dir=none];
    树形结构->树和森林[dir=none];
    二叉树->概念[dir=none];
    二叉树->操作[dir=none];
    二叉树->应用[dir=none];
    
}

4.1 树的基本概念

4.1.1 树的定义

任何一颗非空树要满足

1. 有且只有一个特定的称为根的节点
2. 当$n$大于$1$时，其余节点可分为$m(m>0)$个互不相交的有限集合$T_1, T_2, ...,T_m$，其中每个集合本身又是一颗树，并且称为根节点的子树

树是一种递归结构也是一种层次结构

4.1.2 基本术语

• 祖先节点和子孙节点
• 双亲节点和孩子节点
• 兄弟节点
• 节点的度: 某节点的子节点的个数称为该节点的度
• 树的度: 树中节点的最大度数
• 分支节点: 度大于$0$的节点
• 叶子节点: 度为$0$的节点
• 节点的层次、深度、高度，数的高度
• 有序树和无序树
• 路径和路径长度
• 森林: 森林是$m(m\ge0)$棵互不相交的树的集合

4.1.3 树的性质

1. 树中的节点数等于所有节点的度数$+1$
2. 度为$m$的树中第$i$层上至多有$m^{i-1}$个节点
3. 高度为$h$的$m$叉树至多有$\frac{m^h-1}{m-1}$个节点
4. 具有$n$个节点的$m$叉树的最小高度为$log_m(n(m-1)+1)$

4.2 二叉树的概念

4.2.1 二叉树的定义及其主要特性

1 二叉树的定义

二叉树每个节点至多只有两棵子树，并且二叉树的子树有左右之分，其次序不能任意颠倒

二叉树与度为$2$的有序树的区别

1. 度为$2$的树至少有$3$个节点，而二叉树可以为空
2. 度为$2$的有序树的孩子节点的左右次序是相对另一个孩子节点而言的，若某个节点只有一个孩子节点，则这个孩子节点就无需区分其左右顺序，而二叉树无论其孩子数是否为$2$，均需要确定其左右次序，即二叉树的节点次序不是相对于另一节点而言，而是确定的

2 几个特殊的二叉树

1. 满二叉树: 除了叶子节点，所有节点度都是2

2. 完全二叉树: 略

3. 二叉排序树

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

4. 平衡二叉树

   • 树上任一节点的左子树和右子树的深度之差不超过$1$

3 二叉树的性质

1. 非空二叉树上的叶子节点数等于度为$2$的节点数加$1$，即$n_0=n_2+1$
2. 非空二叉树上第$k$层上至多又$2^{k-1}$个节点
3. 高度为$h$的二叉树至多为$2^h-1$
4. 具有$n$个($n>0$)节点的完全二叉树的高度为$log_2(n+1)$或$log_2n+1$

4.2.2 二叉树的存储结构

1 顺序存储结构

二叉树的顺序存储结构是指用一组地址连续的存储单元依次自上而下、自左而右存储完全二叉树上的节点元素

依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中节点的序号可以唯一地反应节点之间的逻辑关系，这样既可以节省存储空间，又能利用数组元素的下标值确定节点在二叉树中的位置，以及节点之间的关系

对于一般二叉树，为了让数组下标能反映二叉树中节点之间的逻辑关系，只能添加一些并不存在的空节点

2 链式存储结构

由于顺序存储的空间利用率较低，因此二叉树一般采用链式存储结构

二叉链表至少包含$3$个域: 数据域data、左指针域lchild和右指针域rchild

二叉树的链式存储结构描述如下

typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

4.3 二叉树的遍历和线索二叉树

4.3.1 二叉树的遍历

二叉树的遍历是指按照某条搜索路径访问树中的每个节点，使得每个节点均被访问一次

1 先序遍历(PreOrder)

步骤如下:

1. 先访问根节点
2. 先序遍历左子树
3. 先序遍历右子树

void PreOrder(BiTree t){
    if(t != NULL){
        visit(t);
        PreOrder(t->lchild);
        PreOrder(t->rchild);
    }
}

2 中序遍历

步骤如下:

1. 中序遍历左子树
2. 访问根节点
3. 中序遍历右子树

3 后序遍历

步骤如下:

1. 后序遍历左子树
2. 后序遍历右子树
3. 访问根节点

4 递归算法与非递归算法的转换

以先序遍历和中序遍历为例

中序遍历

1. 先将根节点的左子孙全加入栈中
2. 弹出并访问，并将该节点的右孩子和右孩子的所有左子孙加入栈中
3. 重复执行2，直到栈为空

先序遍历

1. 对于根节点和它的所有左子孙，先访问并加入栈中
2. 弹出，访问该节点的右孩子和右孩子的所有左子孙并将它们加入栈中
3. 重复执行2，直到栈为空

后序遍历

• 每个节点需要一个标志来判断是不是第一次被访问
• 先略

5 层次遍历

要进行层次遍历，需要借助一个队列

1. 先将二叉树的根节点入队，
2. 然后出队，访问该节点，若它有左子树，则将左子树根节点入队；若它有右子树，则将右子树根节点入队。
3. 如此反复，直到队列为空

void levelOrder(BiTree T){
    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);
        }
    }
}

6 由遍历构造二叉树

由二叉树的先序遍历和中序遍历可以唯一地确定一棵二叉树，以下几种也可以

1. 中序和后序
2. 层序和中序

但是先序和后序不可以

4.3.2 线索二叉树

1 线索二叉树的基本概念

遍历二叉树的实质: 是对一个非线性结构进行线性化操作，使这个访问序列中的每个节点都有一个直接前驱和一个直接后继

引入线索二叉树是为了加快查找节点前驱和后继的速度

二叉树线索化的方法

1. 若无左子树，令lchild指向其前驱节点；若无右子树，令rchild指向其后继节点
2. 还需要增加两个标志域来表明当前指针域所指对象是指向左/右子节点还是直接前驱/后继

线索二叉树的储存结构描述为

typedef struct ThreadNode{
    ElemType data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag;
}ThreadNode;

2 线索二叉树的构造

对二叉树的线索化，实质上是遍历一次二叉树，只是在遍历的过程中，检查当前节点左、右指针是否为空，若为空，将它们改为指向前驱节点和后继节点的线索

中序遍历的递归算法为

void InThread(ThreadTree *p, ThreadTree *pre){
    if(p!=NULL){
        InThread(p->lchild, pre);
        if(p->lchild == NULL){
            p->lchild = pre;
            p->ltag = 1;
        }
        if( pre != NULL && pre->rchilc == NULL){
            pre->rchild = p;
            pre->rtag = 1;
        }
        pre=p;
        InThread(p->rchild, pre);
    }
}
void CreateInThread(ThreadTree T){
    ThreadTree pre = NULL;
    if(T != NULL){
        InThread(T, pre);
        pre->rchild = NULL;
        pre->rtag = 1;
    }
}

3 线索二叉树的遍历

中序线索化二叉树主要是为了访问运算服务的，这种遍历不再需要借助栈，因为它的节点隐含了线索二叉树的前驱和后继信息

算法如下

1. 求中序线索二叉树中中序序列下的第一个节点

   ThreadNode *FirstNode(ThreadNode *p){
       while(p->ltag==0){
           p=p->lchild;
           return p;
       }
   }

2. 求中序线索二叉树中节点p在中序序列下的后继节点

       ThreadNode *NextNode(ThreadNode *p){
           if(p->rtag==0){
               return FirstNode(p->rchild);
           }else{
               return p->rchild;
           }
       }
       ````    
   3. 利用上面两个算法可以实现线索二叉树的中序遍历
       ````c
       void InOrder(ThreadNode *T){
           for(ThreadNode *p=FirstNode(T); p!=NULL; p=NextNode(p)){
               visit(p);
           }
       }

4.4 树、森林

4.4.1 树的存储结构

1 父亲表示法

这种存储方式采用一组连续空间来存储每个节点，同时在每个节点中增设一个伪指针，指示其父亲节点在数组中的位置

2 孩子表示法

孩子表示法是将每个节点的孩子节点都用单链表链接起来形成一个线性结构，此时$n$个节点就有$n$个孩子链表

3 孩子兄弟表示法

又称为二叉树表示法，以二叉链表作为树的存储结构，孩子兄弟表示法使每个节点包括三部分内容

• 节点值
• 指向节点第一个孩子节点的指针
• 指向节点下一个兄弟节点的指针

孩子兄弟表示法的存储结构描述

typedef struct CSNode{
    ElemType data;
    struct CSNode *firstchild, *nextsibling;
}CSNode

4.4.2 树、森林和二叉树的转换

树与二叉树的关系

• 给定一棵树，可以找到唯一的一棵二叉树与之对应。
• 从物理结构上看，树的孩子兄弟表示法与二叉树的二叉链表表示法相同
• 因此，可以用同一存储结构的不同解释将一棵树转换为二叉树

树转换为二叉树的规则

• 每个节点左指针指向它的第一个孩子节点
• 右指针指向它在树中的相邻兄弟节点

森林转换为二叉树的规则

• 先将森林中的每棵树转换为二叉树
• 将第一棵树的根作为转换后二叉树的根，将第一棵树的左子树作为转换后二叉树根的左子树
• 将第二棵树作为转化后二叉树的右子树
• 将第三棵树作为转化后二叉树根的右子树的右子树

二叉树转换回森林的规则

• 略，与前面的过程相反

4.4.3 树和森林的遍历

1 树的遍历

1. 先根遍历: 若树非空，则先访问根节点，再按从左到右的顺序遍历根节点的每棵子树。其顺序与这棵树相应二叉树的先序遍历顺序相同
2. 后根遍历: 若树非空，则按从左到右的顺序遍历根节点的每棵子树，之后再访问根节点，其访问顺序与这棵树对应二叉树的中序遍历顺序相同

2 森林的遍历

1. 先序遍历森林

   • 访问森林中第一课树的根节点
   • 先序遍历第一课树中根节点的子树森林
   • 先序遍历除去第一棵树之后剩余的树构成的森林

2. 中序遍历森林

   • 中序遍历森林中第一棵树的根节点的子树森林
   • 访问第一棵树的根节点
   • 中序遍历除去第一棵树之后剩余的树构成的森林

4.4.5 树的应用–并查集

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

1. Union(S, Root1, Root2): 把集合S中的子集合Root2并入子集合Root1。要求Root1和Root2互不相交，否则无法合并
2. Find(S, x): 查找集合S中单元素x所在的子集合，并返回该子集合的名字
3. Initial(S): 将集合S中的每个元素都初始化为只有一个单元素的子集合

通常用树的父亲表示法作为并查集的存储结构

• 每个子集合以一棵树表示
• 所有表示子集合的树，构成全集合的森林，存放在父亲表示数组内
• 为了得到两个子集合的并，只需要将其中一个子集合根节点的父亲指针指向另一个集合的根节点

# define SIZE 100
int UFSets[SIZE];

void Initial(int S[]){
    for(int i = 0; i < size; i ++){
        S[i] = -1;
    }
}

int Find(int S[], int x){
    while(S[x] >= 0){
        x = S[x];
    }
    return x;
}

void Union(int S[], int Root1, int Root2){
    S[Root2]=Root1;

}

4.5 树与二叉树的应用

4.5.1 二叉排序树

1 二叉排序树的定义

二叉排序树(BST)，又称二叉查找树

1. 若左子树非空，则左子树上所有节点关键字值均小于根节点关键字值
2. 若右子树非空。则右子树上所有节点关键字值均大于根节点关键字值
3. 左、右子树本身也分别是一棵二叉排序树

2 二叉排序树的查找

二叉排序树的查找从根节点开始，沿某个分支逐层向下进行比较。若当前节点为空，则查找失败。若当前节点非空且与给定值相等，则查找成功。若给定关键字小于当前节点关键字，则在这个节点的左子树查找，否则在右子树查找。

3 二叉排序树的插入

若为空，则直接插入节点；否则，若给定值小于当前节点值，则插入到左子树；否则，插入到右子树

4 二叉排序树的构建

略

5 二叉排序树的删除

1. 若被删除节点$z$是叶子节点，则直接删除
2. 若节点$z$只有左子树或右子树，则让$z$的子树成为$z$父节点的子树，替代$z$的位置
3. 若节点$z$有左、右两棵子树，则令$z$的直接后继(或直接前驱)替代$z$，然后将问题转换为$z$的直接后继(或直接前驱)的删除问题，直到转换为情况1或情况2

6 二叉排序树的查找效率分析

二叉排序树查找算法的效率，主要取决于树的高度。对于高度为$h$的二叉排序树，其插入和删除操作的运行时间都为$O(h)$

• 若二叉排序树是一个只有左(或右)孩子的单支树，则其平均查找长度与单链表相同，为$O(n)$
• 若二叉排序树的左、右子树的高度之差的绝对值不超过$1$，则这样的二叉排序树为平衡二叉树，它的平均查找长度为$O(log_2n)$

4.5.2 平衡二叉树

1 平衡二叉树的定义

平衡二叉树: 任意节点的左、右子树高度差的绝对值不超过1，将这样的二叉树称为平衡二叉树

平衡因子: 定义节点左子树与右子树的高度差为该节点的平衡因子

2 平衡二叉树的插入

二叉排序树保证平衡的基本思想如下

• 每当在二叉排序树中插入一个节点时，首先检查其插入路径上的节点是否因为此次操作而导致了不平衡
• 若导致了不平衡，则先找到插入路径上离插入节点最近的平衡因子的绝对值大于$1$的节点A
• 再对以A为根的子树，在保持二叉排序树特性的前提下，调整各节点的位置关系，使之重新达到平衡

调整方法如下

1. LL平衡旋转
   • 将A的左孩子B向右上旋转代替A成为根节点
   • 将A节点向右下旋转成为B的右子树的根节点
   • B的原右子树作为A的左子树
2. RR平衡旋转
   • 略
3. LR平衡旋转
   • 先将A节点的左孩子B的右子树的根节点C向左上旋转提升到B节点的位置
   • 然后再把该C节点向右上旋转提升到A节点的位置
4. RL平衡旋转
   • 略

3 平衡二叉树的查找

含有n个节点的平衡二叉树的最大深度为$O(log_2n)$，因此平衡二叉树的平均查找长度为$O(log_2n)$

4.5.3 哈夫曼树和哈夫曼编码

1 哈夫曼树的定义

节点的权: 为树中节点赋予的一个表示某种特殊意义的数值

节点的带权路径长度: 从树根节点到该节点的路径长度与该节点上权值的乘积

树的带权路径长度: 树中所有叶节点的带权路径长度之和称为该树的带权路径长度

哈夫曼树(最优二叉树): 在含有n个带权叶子节点的二叉树中，带权路径长度最小的二叉树

2 哈夫曼树的构建

通过哈夫曼算法可以构建最优二叉树，如下

1. 将这$n$个节点分别作为$n$棵仅含有一个节点的二叉树，构成森林$F$
2. 构造一个新节点，从$F$中选取两棵根节点权值最小的树作为新节点的左、右子树，并且将新节点的权值置为左、右子树上根节点的权值之和
3. 从$F$中删除刚才选出的两棵树，同时将新得到的树加入到$F$中
4. 重复2和3，直到F中只剩下一棵树为止

从上述构建过程可以看出哈夫曼树的特点

1. 每个初始节点最终都成为叶节点，且权值越小的节点到根节点的路径长度越大
2. 构建过程中共新建了$n-1$个节点，因此哈夫曼树中节点总数为$2n-1$
3. 每次构建都选择两棵树作为新节点的孩子，因此哈夫曼树不存在度为1的节点

3 哈夫曼编码

固定长度编码和可变长度编码: 对于待处理的一个字符串序列，若对每个字符用相同长度的二进制位表示，则称这种编码方式为固定长度编码；若允许对不同字符用不等长的二进制表示，则这种方式称为可变长度编码

可变长度编码的好处: 对频率高的字符赋以短编码，而对频率低的字符赋以长编码，从而可以使字符平均编码长度减短，达到压缩数据的效果