6 二叉树

[6] 二叉树

二叉树的定义与特性

注意：二叉树不是树的特殊情况，它们是两个概念（详情看上面）

定义： 二叉树是n(n>=0)个结点的有限集，它或者是空集(n=0)，或者由一个根结点及两颗互不相交的分别称作这个根的左子树和右子树的二叉树组成。

特点：

每个结点最多有 2 个孩子（二叉树中不存在度大于 2 的结点）
二叉树可以是空集合，根可以有空的左子树和空的右子树
二叉树有左右之分，次序不能颠倒

二叉树的性质(计算上的)：

在二叉树的第i层上至多有2^(i-1)个结点(i>1)
深度为 k 的二叉树至多有2^k-1个结点(k>=1)
对任何一颗二叉树 T，如果其叶子数为 n~0~，度为 2 的结点数为 n~2~，则 n~0~=n~2~+1.
证：假设树中结点总数为 n,则 ①n=n~0~+n~1~+n~2~ ②n=n~1~+2n~2~+1（因为树的结点数=总度数+1）所以 n~0~=n~2~+1
具有 n 个结点的完全二叉树的深度为(log~2~N)+1

顺序储存

uTools_1665313037451

#define MaxSize 100

struct TreeNode{
   ElemType value; //结点中的数据元素
   bool isEmpty;   //结点是否为空
}
main(){
   TreeNode t[MaxSize];
   for (int i=0; i<MaxSize; i++){
      t[i].isEmpty = true;
   }
}

二叉树的顺序结构适合存储完全二叉树，存一般二叉树会有很多浪费

链式存储

//二叉树的结点

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; //作为根节点的左孩子

找到指定结点 p 的左/右孩子；
找到指定结点 p 的父节点；只能从根结点开始遍历，也可以使用三叉链表

typedef struct BiTnode{
   ElemType data;          //数据域
   struct BiTNode *lchild, *rchild; //左、右孩子指针
   struct BiTNode *parent;          //父节点指针
}BiTNode, *BiTree;

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

[6-1] 完全二叉树

深度为 k 的具有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 k 的满二叉树中编号为 1~n 的结点一一对应时，称之为完全二叉树。

储存

顺序表存完全二叉树

uTools_1665311785932

[6-1-1] 满二叉树

一颗深度为k且有2^k-1个结点的二叉树称为满二叉树。每一层上的结点数都达到最大。叶子全部在最低层。

uTools_1665304677893

[6-2] 二叉排序树（BST）

也称二叉查找树，属于二叉树类，可以为空树

左子树结点值<跟结点值<右子树结点值
左子树和右子树又各是一棵二叉排序树

{0} 构造

//按照str[]中的关键字序列建立二叉排序树
void Crear_BST(BSTree &T, int str[], int n){
   T = NULL;                     //初始时T为空树
   int i=0;
   while(i<n){
      BST_Insert(T,str[i]);     //依次将每个关键字插入到二叉排序树中
      i++;
   }
}

{1} 插入

// 在二叉排序树中插入关键字为k的新结点（递归）
// 最坏空间复杂度：O(h)
int BST_Insert(BSTree &T, int k){
   if(T==NULL){           // 原树为空，新插入的结点为根结点
      T = (BSTree)malloc(sizeof(BSTNode));
      T->key = k;
      T->lchild = T->rchild = NULL;
      return 1;                       // 插入成功
   }
   else if(K == T->key)               // 树中存在相同关键字的结点，插入失败
      return 0;
   else if(k < T->key)
      return BST_Insert(T->lchild,k);
   else
      return BST_Insert(T->rchild,k);
}

{2} 删除

如果是叶子节点 => 直接删

非叶子节点

只有 1 个孩子 => 孩子代替该节点位置

有 2 个孩子

其中一个孩子代替父亲的位置，另一边整理上去

50(26(21 30) 66(60 70(68)))
删除66=>
## 左孩子代替，则右子树放到左边最大的节点的右孩子上(该位置一定为空)
50(26(21 30) 60(70(68)))
## 右孩子代替，则做子树放到左边最大的节点的左孩子上(该位置一定为空)
或50(26(21 30) 70(60 68))

{3} 查找

typedef struct BSTNode{
   int key;
   struct BSTNode *lchild, *rchild;
}BSTNode, *BSTree;

// 在二叉排序树中查找值为key的结点（非递归）
// 最坏空间复杂度：O(h)
BSTNode *BST_Search(BSTree T, int key){
   while(T!=NULL && key!=T->key){        // 若树空或等于跟结点值，则结束循环
      if(key<T->key)       // 值小于根结点值，在左子树上查找
         T = T->lchild;
      else                  // 值大于根结点值，在右子树上查找
         T = T->rchild;
   }
   return T;
}

// 在二叉排序树中查找值为key的结点（递归）
// 最坏空间复杂度：O(h)
BSTNode *BSTSearch(BSTree T, int key){
   if(T == NULL)
      return NULL;
   if(Kry == T->key)
      return T;
   else if(key < T->key)
      return BSTSearch(T->lchild, key);
   else
      return BSTSearch(T->rchild, key);
}

[6] {3} 查找

查找长度：在查找运算中，需要对比关键字的次数称为查找长度，反映了查找操作时间复杂度
查找成功的平均查找长度 ASL=所有节点的查找长度求平均
例：
```
    X
   /|\
  X B X
 /|  /|\
X X D X X
```
D 的查找长度为 3，B 的查找长度为 2
ASL=(1*1+3*2+5*3)/9=22/9

平均查找长度越低，查找效率越高

查找失败的平均查找长度=所有叶子的子节点的查找长度求平均
图中标为K的子节点不存在，但查找时会查询那个位置是不是空的，也就是最终会到那个位置
```
    X
   /|
  X B
 /| |\
K K K K
```
查找失败 ASL=（4*3）/4=3

[6-2-1] 平衡二叉树（AVL）

平衡二叉树，也称平衡树，是特殊的二叉排序树

平衡二叉树是为了避免二叉排序树高度增长过快导致二叉排序树性能降低而设计的树

特性：保证树上任一结点的左子树和右子树的深度之差不超过 1。

平衡二叉排序树的平均查找长度更低，效率更高

节点的平衡因子=左子树高 - 右子树高

节点平衡因子大于 1 或小于-1 就不平衡了

深度为 h 的平衡树中含有的最少节点数 N~h~=N~h-1~+N~h-2~+1

{0} 构造

//平衡二叉树结点
typedef struct AVLNode{
   int key;         //数据域
   int balance;     //平衡因子
   struct AVLNode *lchild; *rchild;
}AVLNode, *AVLTree;

{调节最小不平衡子树}

向平衡二叉树添加/删除数据时会导致平衡二叉树状态打破，即某一边的查找深度超了

比如：

A(B(D(H)E)C)

A(2)
B(1)   C
D(0) E
H

## 括号内为节点平衡因子，A(2)>1，平衡状态打破了

当出现不平衡时，只需要调整最小不平衡子树，最小不平衡子树调节后，其父节点都会恢复正常

有四种情况需要一一讨论

LL：在 A 的左孩子的左子树中插入导致不平衡
- 调整：A 的左孩子结点右上旋
RR：在 A 的右孩子的右子树中插入导致不平衡
- 调整：A 的右孩子结点左上旋
LR：在 A 的左孩子的右子树中插入导致不平衡
- 调整：A 的左孩子的右孩子先左上旋再右上旋
RL：在 A 的右孩子的左子树中插入导致不平衡
- 调整：A 的右孩子的左孩子先右上旋后左上旋

LL

uTools_1669712955177

LR

uTools_1669713188348

效率分析

对于一棵有 N 个节点的二叉树，若树高 H，则最坏情况下，查找一个关键字最多需要对比 H 次，即查找操作时间复杂度小于 O(H)

高度 H∈(log~2~N,N)

而对于平衡二叉树，由于深度为 h 的平衡树中含有的最少节点数 N~h~=N~h-1~+N~h-2~+1，通过一同扫操作可得（具体论证较复杂），平均查找长度约为 O(log~2~N)。

[6-4] 哈夫曼树

uTools_1669717301719

【带权路径长度】

节点的权：有某种现实含义的数值（如：表示结点的重要性等）
节点的带权路径长度：从树的根到该节点的路径长度（经过的边数）* 该节点的权值

1(1(1(5 1) 2(10 3)) 4)
1
|    \
1        4
| \
1   2
|\  | \
5 1 10 3->3*3=9

树的带权路径：所有叶子节点的带权路径长度之和

哈夫曼树定义

在含有 N 个带权叶结点的二叉树中，其中带权路径长度(WPL)最小的二义树称为哈夫曼树，也称最优二义树

构造哈夫曼树

uTools_1669714415289

哈夫曼编码

用左和右代替 1 和 0，编码来传递信息，可以更具信息的内容设计子字典以减少信息量（减少冗余）

举例

传输一段包含 ABCD 的信息

其中 A 占 10，B 占 8，C 占 80，D 占 2

普通编码

固定长度编码：每个字符用相等长度的二进制位表示

直接编码（）

A:00		B:01
C:10		D:11

转化为二叉树

    X
  X   X
A  B C  D
00 01 10 11
## 向作为0，向右为1

需要传 2*100=200 位数字（200bit）

哈夫曼编码

根据信息内容生产安哈夫曼编码

字符集中的每个字符作为一个叶子结点，各个字符出现的频度作为结点的权值，构造哈夫曼树

X(C X(A X(D B)))
X
C X
  A X
    D B

生成的编码为：

C:0		A:10
B:111	D:110

需要传输的数据=WPL=80*1+10*2+(2+8)*3

不能用 X 替换信息，会出现错误

## 非前缀编码
C:0		A:1
B:111	D:110

CAAABD => 0 1 1 1 111 110 => 0111111110 => 0 111 111 110 => CBBD

哈夫曼编码特点

可变长度编码：允许对不同字符用不等长的二进制位表示
前缀编码：对字符集进行编码时，要求字符集中任一字符的编码都不是其它字符的编码的前缀

[6] {4} 二叉树遍历

先序/前序遍历

遍历顺序：根左右
若二叉树为空，不用操作
若二叉树非空
- 访问根节点
- 先序遍历左子树
- 先序遍历右子树

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);      //递归遍历右子树
   }
}

中序遍历

左根右
若二叉树为空，不用操作
若二叉树非空：
- 先序遍历左子树
- 访问根节点
- 先序遍历右子树

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);       //递归遍历右子树
   }
}

后续遍历

左右根
若二叉树为空，不用操作
若二叉树非空：
- 先序遍历左子树
- 先序遍历右子树
- 访问根节点

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);                 //访问根结点
   }
}

二叉树的层次遍历

（广度优先遍历）

算法思想：

初始化一个辅助队列
根节点入队
若队列非空，则队头结点出队，访问该结点，依次将其左、右孩子插入队尾（如果有的话）
重复以上操作直至队列为空

//二叉树的结点(链式存储)
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);   //右孩子入队
   }
}

由遍历序列构造二叉树

得到一下三个序列之一都能还原初完整的二叉树

先序序列 + 中序序列
后序序列 + 中序序列
层序序列 + 中序序列
key: 找到树的根节点，并根据中序序列划分左右子树，再找到左右子树根节点、

[6-4]线索二叉树

线索二叉树的概念与作用

在二叉树的结点上加上线索的二叉树称为线索二叉树

线索二叉树的存储结构

中序线索二叉树——线索指向中序前驱、中序后继
（原本空着的 2 个节点分别指向中序前驱和后继，这样遍历，寻找前后继会快很多）

//线索二叉树结点
typedef struct ThreadNode{
   ElemType data;
   struct ThreadNode *lchild, *rchild;
   int ltag, rtag;                // 左、右线索标志
}ThreadNode, *ThreadTree;

tag == 0: 指针指向孩子
tag == 1: 指针是“线索”

先序线索二叉树——线索指向先序前驱、先序后继
后序线索二叉树——线索指向后序前驱、后序后继

{ } 二叉树的线索化

对二叉树以某种遍历方式（如先序、中序、后序或层次等）进行遍历，使其变为线索二叉树的过程称为对二叉树进行线索化

中序线索化

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;         //处理遍历的最后一个结点
   }
}

先序线索化注意【转圈】问题，当 ltag==0 时，才能对左子树先序线索化

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;         //处理遍历的最后一个结点
   }
}

后序线索化

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;         //处理遍历的最后一个结点
   }
}

{ } 线索二叉树中找前驱、后继

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

若 p->rtag == 1, 则 next = p->rchild;

若 p->rtag == 0, 则 p 必有右孩子, 则 next = p的右子树中最左下结点;

//1. 找到以P为根的子树中，第一个被中序遍历的结点
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; //rtag==1，直接返回后继线索
}

//3. 对中序线索二叉树进行中序遍历
void Inorder(ThreadNode *T){            //T为根节点指针
   for(ThreadNode *p = Firstnode(T); p!=NULL; p = Nextnode(p))
      visit(p);
}

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

若 p->rtag == 1, 则 next = p->rchild; 若 p->rtag == 0, 则 p 必有右孩子（左孩子不知道）
case1: 若 p 有左孩子 ——— 根左右 / 根 (根左右) 右
case2: 若 p 没有左孩子 ——— 根右 / 根 (*根 *左右)

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

若 p->ltag == 1, 则 next = p->lchild;
若 p->ltag == 0, 则 p 必有左孩子，但是先序遍历中，左右子树的结点只可能是根的后继，不可能是前驱，所以不能从左右孩子里寻找 p 的先序前驱，（除非从头开始遍历/三叉链表
case1: 如果能够找到 p 的父节点，且 p 是左孩子 —— p 的父节点就是 p 的前驱；
case2: 如果能够找到 p 的父节点，且 p 是右孩子，且其左兄弟为空 —— p 的父节点就是 p 的前驱；
case3: 如果能够找到 p 的父节点，且 p 是右孩子，且其左兄弟非空 —— p 的前驱为左兄弟子树中最后一个被先序遍历到的结点（根节点出发，先往右，右没有往左，找到最下一层的结点）；
case4: p 没有父节点，即 p 为根节点，则 p 没有先序前驱

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

若 p->ltag == 1, 则 next = p->lchild;

若 p->ltag == 0, 则 p 必有左孩子（不知道有没有右孩子）

case1: 若 p 有右孩子 ——— 左右根 / 左 (左右根) 根

case2: 若 p 没有右孩子 ——— 左根（左子树按后序遍历，最后一个结点，p 的左孩子）

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

若 p->rtag == 1, 则 next = p->rchild;

若 p->rtag == 0, 则 p 必有右孩子, 左孩子不知道, 但是在后序遍历中，左右子树中的结点只有可能是根的前驱，而不可能是根的后继，所以找不到后继，（除非从头开始遍历/三叉链表

case1: 如果能找到 p 的父节点，且 p 是右孩子 —— p 的父节点即为其后继

case2: 如果能找到 p 的父节点，且 p 是左孩子，其右兄弟为空 —— p 的父节点即为其后继

case3: 如果能找到 p 的父节点，且 p 是左孩子，其右兄弟非空 —— p 的后继为其右兄弟子树中第一个被后序遍历的结点；

case4: p 没有父节点，即 p 为根节点，则 p 没有后序后继；

在这里插入图片描述

6 二叉树 ​

[6] 二叉树 ​

二叉树的定义与特性 ​

顺序储存 ​

链式存储 ​

[6-1] 完全二叉树 ​

储存 ​

[6-1-1] 满二叉树 ​

[6-2] 二叉排序树（BST） ​

{0} 构造 ​

{1} 插入 ​

{2} 删除 ​

{3} 查找 ​

[6] {3} 查找 ​

[6-2-1] 平衡二叉树（AVL） ​

{0} 构造 ​

{调节最小不平衡子树} ​

LL ​

LR ​

效率分析 ​

[6-4] 哈夫曼树 ​

【带权路径长度】 ​

哈夫曼树定义 ​

构造哈夫曼树 ​

哈夫曼编码 ​

[6] {4} 二叉树遍历 ​

先序/前序遍历 ​

中序遍历 ​

后续遍历 ​

二叉树的层次遍历 ​

由遍历序列构造二叉树 ​

[6-4]线索二叉树 ​

线索二叉树的概念与作用 ​

线索二叉树的存储结构 ​

{ } 二叉树的线索化 ​

{ } 线索二叉树中找前驱、后继 ​

6 二叉树

[6] 二叉树

二叉树的定义与特性

顺序储存

链式存储

[6-1] 完全二叉树

储存

[6-1-1] 满二叉树

[6-2] 二叉排序树（BST）

{0} 构造

{1} 插入

{2} 删除

{3} 查找

[6] {3} 查找

[6-2-1] 平衡二叉树（AVL）

{0} 构造

{调节最小不平衡子树}

LL

LR

效率分析

[6-4] 哈夫曼树

【带权路径长度】

哈夫曼树定义

构造哈夫曼树

哈夫曼编码

[6] {4} 二叉树遍历

先序/前序遍历

中序遍历

后续遍历

二叉树的层次遍历

由遍历序列构造二叉树

[6-4]线索二叉树

线索二叉树的概念与作用

线索二叉树的存储结构

{ } 二叉树的线索化

{ } 线索二叉树中找前驱、后继