第五章-树

WanXing2022年7月28日大约 18 分钟

5.1 树的基本概念

1.树的定义

1.树的定义：n 个结点的有限集

需要满足：有且仅有一个根；其余结点可分为互不相交的子树

2.树的特点
- 树的根结点没有前驱，除根结点外的所有结点有且只有一个前驱
- 树中所有结点可以有零个或多个后继

2.基本术语

根结点：非空树中无前驱结点的结点
结点的度：结点拥有的子树数
树的度：树内各结点的度的最大值
叶子（终端结点）：没有后继元素（度 = 0）
分支结点（非终端结点）：度 != 0；
内部结点：根结点以外的分支结点
孩子，双亲：结点的子树的根称为该结点的孩子，该结点称为孩子的双亲
兄弟结点：有共同的双亲
堂兄弟：双亲在同一层的结点
结点的祖先：从根到该结点所经分支上的所有结点
结点的子孙：以某结点为根的子树中的任一结点
树的深度：树中结点的最大层次
结点的深度（根--> 自顶向下）
结点的高度（叶节点--> 自底向上）
有序树：树中结点的各子树从左至右有次序（最左边为第一个孩子）
无序树：树中结点的各子树无次序
森林：是 m（m≥0）棵互不相交的树的集合，把根结点删除，树就变成了森林，一棵树可以看成是一个特殊的森林，给森林中的各子树加上一个双亲结点，森林就变成了树（树一定是森林，森林不一定是树）

3.树的性质

树中的结点数等于所有结点的度数之和 + 1
度为m的树中第i层上至多有 $m^{i-1}$ 个结点（i≥1）
高度为h的m叉树至多有 $(m^h-1)/(m-1)$ 个结点
具有n个结点的m叉树的最小高度为 $\lceil \log_m{(n(m-1)+1)} \rceil$

4.习题

在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶节点个数是（）

基本定义：度为0的结点成为叶子（leaf）或终端结点。
总节点个数为：根节点+子节点根节点个数为1，子节点个数为204+103+12+101 = 122
所以总结点个数为123个。只有叶节点度数为0，其他结点都有度数。
由题意得其他结点总数为20+10+1+10 =41个故叶节点（终端节点）=123-41=82个。

5.2 二叉树的概念

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

1.二叉树定义: 每个结点至多只有两颗子树,子树有左右之分,其次序不能颠倒

二叉树与度为 2 的有序树的区别
度为 2 的二叉树至少三个结点,二叉树考研为空
度为 2 的有序树的孩子左右次序是相对另一孩子而言的,二叉树是确定的

2.几个特殊的二叉树

1.满二叉树：高度为 h ,且含有 $2^h-1$ 个结点的二叉树. 假设高度为 3，那么满二叉树的结点数就是（1+2+4=7）7 个，每层都是满的.

     1
    / \
   2   3     <== 这就是满二叉树
  / \ / \
 4  5 6  7

2.完全二叉树：其实就是满二叉树删除最后 x 个结点，比如一颗完全二叉树的高度是 3，下图都是完全二叉树

     1           1           1
    / \         / \         / \
   2   3       2   3       2   3
  / \ /       / \         /
 4  5 6      4  5        4

若 $i\leq \lfloor n/2 \rfloor$ ,则结点为分支结点,否则为叶子结点
叶子结点只可能在层次最大的两层上出现,依次排列在最左边的位置上
若有度为 1 的结点,则只可能有 1 个,且只有左孩子而无右孩子
一旦出现某节点为叶子结点或只有左孩子,则编号大于该结点的均为叶子结点
n 为奇数,每个分支结点都有左右孩子, n为偶数 $i=n/2$ 只有左孩子

3.二叉排序树：对于任何一个结点，左子树比它小，右子树比它大

     5           5             5
    /           / \           / \
   3           3   7         3   7   ......好多好多
  /           /     \       /   /
 1           1       10    1   6

4.平衡二叉树：可以理解为更加严格的二叉排序树

     5       👈这是二叉排序树                  3
    /        但不是平衡二叉树                  / \
   3         你可以理解为左轻右重             1   5
  /          很不美观，调整后👉
 1

3.二叉树的性质

1.非空二叉树上的叶子结点数等于 --> 度为 2 的结点数加 1，即 $n_0=n_2+1$

$n_0+n_1+n_2=n$ 联立 $n-1=n_1+2*n_2$

2.非空二叉树上第 k 层上至多有 $2^{k-1}$ 个结点，总共至多有 $2^k-1$ 个结点
3.高度为 h 的二叉树至多有 $2^h-1$ 个结点
4.对完全二叉树按从上到下、从左到右的顺序依次编号 1，2，...，n，则有以下关系
- ① 当 $i >1$ 时，结点 $i$ 的双亲的编号为 $\lfloor i/2 \rfloor$ ，即当 i 为偶数时，其双亲编号为 $i/2$ ，它是双亲的左孩子；当 $i$ 为奇数时，其双亲的编号为 $(i-1) / 2$ ，它是双亲的右孩子
- ② 当 $2i ≤ n$ 时，结点 $i$ 的左孩子编号为 $2i$ ，否则无左孩子
- ③ 当 $2i + 1 ≤ n$ 时，结点 $i$ 的右孩子编号为 $2i$ ，否则无右孩子
- ④ 结点 i 所在的层次（深度）为 $\lfloor \log_2i \rfloor+1$
5.具有 n 个（n > 0）结点的完全二叉树的高度为 $\lceil\log_2(n+1)\rceil或\lfloor\log_2 n\rfloor+1$

二叉树的存储结构

1.顺序存储结构
- a.完全二叉树和满二叉树采用顺序存储比较合适
- b.对于一般的二叉树，需要添加并不存在的空结点
- c.结点类型定义

#define MAXSIZE 100
typedef TElemType SqBiTree[MAXSIZE];
SqBiTree bt;

2.链式存储结构
- 1.二叉链表
  - 二叉链表的结点类型定义

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

在含有 n 个结点的二叉链表中，含有 n+1 个空链域

\begin{cases} 1n_0+1n_1+1n_2=n&结点数之和\\ 0n_0+1n_1+2n_2=n-1&度和结点关系\\ 2n_0+1n_1+0n_2=?&求空链域\\ \end{cases}

再来看看三叉链表，它的结点类型定义如下

typedef struct TriNode{
  TElemType data;
  struct TriNode *lchild,*rchild,*parent;
}TriNode, *TriTree;

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

1.二叉树的遍历

1.先序遍历 PreOrder

1.遍历结点的顺序如下，先是 根结点、再是左子树，最后右子树

    1                1
   / \     =>       / \
  2   3            2   5
                  / \ / \
                 3  4 6  7

2.先序遍历的算法实现（递归）

void PreOrder(BiTree T) {
  if (T != NULL){         // 如果二叉树非空，则继续
    visit(T);             // 访问根结点内容
    PreOrder(T->lchild);  // 访问左子树内容
    PreOrder(T->rchild);  // 访问右子树内容
  }
}

2.中序遍历 InOrder

1.遍历结点的顺序如下，先是左子树、再是根节点，最后右子树

    2                4
   / \     =>       / \
  1   3            2   6
                  / \ / \
                 1  3 5  7

2.中序遍历的算法实现（递归）

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

3.后续遍历 PostOrder

1.遍历结点的顺序如下，先是左子树、再是右子树，最后根节点

    3                7
   / \     =>       / \
  1   2            3   6
                  / \ / \
                 1  2 4  5

2.后序遍历的算法实现（递归）

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

4.递归算法和非递归算法的转换

1.中序遍历的非递归算法

void InOrder2(BiTree T, SqStack S) {
  InitStack(S);   //初始化栈 S 
  BiTree p = T;   //p 是遍历指针
  while (p || !IsEmpty(S)) {    //栈不空或p不空
    if (p) {    //一路向左
        Push(S, p);   //当前结点入栈
        p = p->lchild;    //左孩子不空
    }
    else {    //出栈,转向右子树
        Pop(S, p);    //栈顶元素出栈
        visit(p);   //访问
        p = p->rchild;    //向右
    }
  }
}

2.先序遍历非递归

void PreOrder2(BiTree T){
  InitStack(S);
  BiTree p = T;
  while(p||!IsEmpty(S)){
    if(p){
      visit(p);
      Push(S,p);
      p = p->lchild;    //向左走
    }
    else{   //转向右子树
      Pop(S,p);
      p = p->rchild;
    }
  }
}

3.后续遍历非递归（比较难）

5.层次遍历

字面意思，一行一行遍历

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.二级推论

（先序 + 中序） => 唯一的二叉树
（后序 + 中序） => 唯一的二叉树
（层序 + 中序） => 唯一的二叉树

7.线索二叉树

线索二叉树 Threaded Binary Tree
- 1.线索二叉树的基本概念:利用空指针存放指向其前驱或后继的指针
- 若无左子树,lchild指向前驱,若无右子树,rchild指向后继
- 增加tag标识是指向孩子还是前后继 0-->孩子,1-->前后继
- 2.中序线索二叉树的构造

//中序遍历对二叉树线索化
void InThread(ThreadTree &p,ThreadTree &pre){
  if(p!=NULL)
  {
    InThread(p->lchild,pre);    //递归线索化左子树
    if(p->lchild==NULL)
    {
      p->lchild = pre;    //左子树为空,建立前驱线索
      p->ltag = l;
    }
    if(pre!=NULL && pre->rchild==NULL)
    {
      pre->rchild = p;    //建立前驱结点的后继线索
      pre->rtag = 1;
    }
    pre = p;    //标记当前节点成为刚刚访问的结点
    InThread(p->rchild,pre);    //递归线索化右子树
  }
}

//中序遍历建立二叉树
void CreateInThread(ThreadTree)
{
  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;
}

//求中序线索二叉树中结点p再中序序列下的后继
ThreadNode *NextNode(ThreadNode *p)
{
  if(p->ltag ==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);
}

4.先序线索二叉树和后序线索二叉树 TODO

5.4 树、森林 Tree Forest

1.树的存储结构

1.双亲表示法:每个结点中增设一个伪指针,指示其双亲结点在数组中的位置

#define MAX_TREE_SIZE  100
typedef struct{
  ElemType data;    //数据元素
  int parent;   //双亲位置域
}PTNode;

typedef struct{
  PTNode nodes[MAX_TREE_SIZE];    //双亲表示
  int n;    //结点数
}PTree

每个结点具有唯一双亲,可以很快找到双亲但求结点孩子需要遍历

2.孩子表示法:将每个结点的孩子都用单链表链接成一个线性结构,此时n个结点就有n个孩子链表

顺序+链式,找子女直接,寻找双亲需要遍历

3.孩子兄弟表示法:以二叉链表作为存储结构

typedef struct CSNode{
  ElemType data;    //数据域
  struct CSNode *firstchild,*nextsibling;   //第一个孩子和右兄弟指针
}CSNode,*CSTree;

链式,方便转换为二叉树,易于查找孩子,查找双亲较麻烦

2.树、森林与二叉树的转换

1.树转换成二叉树的画法(左指针是孩子，右指针兄弟):在兄弟结点之间加一条线,对每个结点只保留和第一个孩子的连线,以树根为轴心顺时针旋转45°
2.森林转换为二叉树的画法:将树林中的每棵树转换成相应的二叉树,每棵树的根之间加一条连线,以第一棵树的根为轴心顺时针旋转45°
3.二叉树转换为森林，二叉树的根及左子树为第一棵树的二叉树形式，将根的右链断开。右子树继续转换

3.树和森林的遍历

1.先根遍历:先访问根节点,再遍历根结点的每棵子树(等于二叉树的先序)
2.后根遍历:先访问每棵子树,再访问根节点(等于二叉树的中序遍历)

4.森林的性质

1.一条边一个结点
终端结点->左孩子指针为空的结点的个数
非终端结点+1->右指针域为空的结点的个数

树与二叉树的应用

1.哈夫曼树和哈夫曼编码

1.哈夫曼树的定义:带权路径长度最小的二叉树
- 1.带权路径长度
  - $WPL = \sum^n_{i=1}w_il_i$
  - $w_i$ 叶节点所带权值
  - $l_i$ 叶节点到根结点的路径长度
- 2.哈夫曼树的构造
  - 构造一个新结点,从 F 中选取两棵根节点权值最小的树作为新结点的左,右子树,新结点的权值为左右子树根结点的权值之和
  - 选择新树加入 F
  - 直至 F 中只剩下一棵树
初始结点-->叶结点;新建了 n-1个结点;不存在度为 1 的结点
- 3.哈夫曼编码
  - 固定长度编码
  - 可变长度编码
  - 前缀编码
  没有一个编码是其他编码的前缀

因为度为m的哈夫曼树中，节点的度只有0或m。假设非叶节点（即度为m的节点）个数为a,由题意知叶结点个数（即度为0节点个数）是n。在该哈夫曼树中度为m的节点有m个分支，度为0的节点有0个分支。因为树的总结点数=总分支数+1，所以有 n+a=am+n0 +1 ，化简后有a=(n-1)/(m-1)

2.树的应用——并查集

1.并查集:简单的集合表示，通常使用树的双亲表示作为存储结构
- Union(S, Root1, Root2)
- Find(S, x)
- Initial(S)
2.并查集的结构定义

#define SIZE 100
int UFSets[SIZE];

1.并查集的初始化操作

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

2.并查集的查找操作

int Find(int S[], int x){
  while(S[x]>=0)    //循环寻找x的根
    x = S[x];
  return x;   //根的s[]小于0
}

3.并查集的合并操作

void Union(int S[], int Root1, int Root2){
  S[Root2] = Root1;   //将根Root2连接到另一根Root1下面
}

5.5 树与二叉树的应用

二叉排序树（BST）

二叉排序树的定义
二叉排序树的查找
二叉排序树的插入
二叉排序树的构造
二叉排序树的删除
二叉排序树的查找效率分析

平衡二叉树 Balanced Binary Tree

平衡二叉树的定义
- 结点左子树与右子树的高度差为该结点的平衡因子
平衡二叉树的插入
- LL 平衡旋转（右单旋转）
- RR 平衡旋转（左单旋转）
- LR 平衡旋转（先左后右双旋转）
- RL 平衡旋转（先右后左双旋转）
平衡二叉树的查找

第五章-树

# 5.1 树的基本概念

# 1.树的定义

# 2.基本术语

# 3.树的性质

# 4.习题

# 5.2 二叉树的概念

# 1.二叉树的定义及其主要特性

# 2.几个特殊的二叉树

# 3.二叉树的性质

# 二叉树的存储结构

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

# 1.二叉树的遍历

# 1.先序遍历 PreOrder

# 2.中序遍历 InOrder

# 3.后续遍历 PostOrder

# 4.递归算法和非递归算法的转换

# 5.层次遍历

# 6.二级推论

# 7.线索二叉树

# 5.4 树、森林 Tree Forest

# 1.树的存储结构

# 2.树、森林与二叉树的转换

# 3.树和森林的遍历

# 4.森林的性质

# 树与二叉树的应用

# 1.哈夫曼树和哈夫曼编码

# 2.树的应用——并查集

# 5.5 树与二叉树的应用

# 二叉排序树（BST）

# 平衡二叉树 Balanced Binary Tree

5.1 树的基本概念

1.树的定义

2.基本术语

3.树的性质

4.习题

5.2 二叉树的概念

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

2.几个特殊的二叉树

3.二叉树的性质

二叉树的存储结构

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

1.二叉树的遍历

1.先序遍历 PreOrder

2.中序遍历 InOrder

3.后续遍历 PostOrder

4.递归算法和非递归算法的转换

5.层次遍历

6.二级推论

7.线索二叉树

5.4 树、森林 Tree Forest

1.树的存储结构

2.树、森林与二叉树的转换

3.树和森林的遍历

4.森林的性质

树与二叉树的应用

1.哈夫曼树和哈夫曼编码

2.树的应用——并查集

5.5 树与二叉树的应用

二叉排序树（BST）

平衡二叉树 Balanced Binary Tree