树，森林，满二叉树，完全二叉树，二叉排序树，平衡二叉树，线索二叉树，森林与二叉树的转换，哈夫曼树

视频讲解，习题讲解，思维导图，PPT资源

链接: https://pan.baidu.com/s/1A8aNDgNie4ANZF0gJJGwDA 密码: wdio

1. 树

1.1. 定义

从树根生长，逐级分支

空树——结点数为0的树

非空树的特性：

有且仅有一个根节点
没有后继的结点称为“叶子结点”(或终端结点)
有后继的结点称为“分支结点”(或非终端结点)
除了根节点外，任何一个结点都有且仅有一个前驱
每个结点可以有0个或多个后继。
树是一种递归定义的数据结构

树是n(n≥0)个结点的有限集合，n = 0时，称为空树，这是一种特殊情况。在任意一棵非空树中应满足:

有且仅有一个特定的称为根的结点。
当n> 1时，其余结点可分为m(m> 0)个互不相交的有限集合T₁, T₂,…, T_m，其中每个集合本身又是一棵树，并且称为根结点的子树。

##基本术语

1.1.1. 结点之间的关系描述

什么是祖先结点?

根A到结点K的唯一路径上的任意结点，称为结点K的祖先。结点B是结点K的祖先。
什么是子孙结点?

结点K是结点B的子孙。
什么是双亲结点(父节点)?

路径上最接近结点K的结点E称为结点K的双亲结点，如结点E是结点K的父节点。根A是树中唯一没有双亲的结点。
什么是孩子结点?

结点K是结点E的祖先。
什么是兄弟结点?

有相同双亲的结点称为兄弟。如结点K和结点L有相同的双亲E，K和L是兄弟。
什么是堂兄弟结点?

位于同一层的结点为堂兄弟结点。如结点E，F，G，H，I，J
什么是两个结点之间的路径?

只能从上往下看结点之间的边情况。路径由两个结点之间所经过的结点序列构成。如结点A到结点K的路径为A->B->E->K。同一个双亲的两个孩子之间不存在路径。
什么是路径长度?

结点到结点经过几条边。如结点A到结点K经过边数为3
树的路径长度

树的路径长度是指树根到每个结点的路径长的总和。根到每个结点的路径长度的最大值应是树的高度-1。

1.1.2. 结点，树的属性描述

结点的层次(深度)——从上往下数

根结点为第1层，它的子结点为第2层，以此类推。双亲在同一层的结点互为堂兄弟。

深度为从根结点开始自顶向下逐层累加。
结点的高度——从下往上数

从叶结点开始自底向上逐层累加。
树的高度(深度)——总共多少层

树高为树中结点的最大层数。如上图树的高度为4
结点的度——有几个孩子(分支)
树的度——各结点的度的最大值

1.1.3. 有序树vs无序树

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

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

1.1.4. 树 vs 森林

森林。森林是m(m≥0)棵互不相交的树的集合。m可为0，代表空森林

eg：全中国所有人家的家谱

考点：二叉树与森林的转换——左孩子右兄弟存储法

1.2. 常考性质

1.2.1. 结点数=总度数+1

结点的度——结点有几个孩子(分支)

1.2.2. 度为m的树、m叉树的区别

树的度——各结点的度的最大值

m叉树——每个结点最多只能有m个孩子的树

度为m的树	m叉树
任意结点的度 ≤ m(最多m个孩子)	任意结点的度 ≤ m(最多m个孩子)
至少有一个结点度 = m(有m个孩子)	允许所有结点的度都 < m
一定是非空树，至少有m+1个结点	可以是空树

1.2.3. 度为m的树第i层结点数

度为m的树第 i 层至多有 m^i-1 个结点(i≥1)

m叉树第 i 层至多有 m^i-1 个结点(i≥1)

1.2.4. 高度为h的m叉树至多有结点数

高度为h的m叉树至多有$\frac{m^{h}-1}{m-1}$ 个结点

等比数列求和公式：a+aq+aq$^{2}$+…+aq$^{n-1}$=$\frac{a(1-q^{n})}{1-q}$

###高度为h的m叉树至少有结点数

高度为h的m叉树至少有 h 个结点。

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

1.2.5. 具有n个结点的m叉树的最小高度

具有n个结点的m叉树的最小高度为$\left \lceil log_{m}(n(m - 1) + 1)\right \rceil$

高度最小的情况——所有结点都有m个孩子

1.3. 树的存储结构

1.3.1. 双亲表示法(顺序存储)

每个结点中保存指向双亲的“指针”

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

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

新增数据元素，无需按逻辑上的次序存储

删除数据元素：

不移动其他数据，对应结点的数组元素数据置空，parent=-1
移动后续数据，类同于数组的删除，数据元素前移

优点：查指定结点的双亲很方便

缺点：查指定结点的孩子只能从头遍历

1.3.2. 孩子表示法(顺序+链式存储)

孩子表示法：顺序存储各个节点，每个结点中保存孩子链表头指针

struct CTNode{
  //孩子结点在数组中的位置
  int child;
  //下一个孩子
  struct CTNode *next;
}

typedef struct{
  ElemType data;
  //第一个孩子
  struct CTNode *firstChild;
}CTBox;

#define MAX_TREE_SIZE 100
typedef struct{
  CTBox nodes[MAX_TREE_SIZE];
  int n,r;
}CTree;

1.3.3. 孩子兄弟表示法(链式存储)

左孩子右兄弟

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

typedef struct CSNode{
  ElemType data;
  //左指针-第一个孩子
  //右指针-右兄弟
  struct CSNode *firstchild,*nextsibling;
}

1.3.4. 树与二叉树的转换

一个结点左指针为其第一个孩子，右指针为其右兄弟

1.3.5. 森林和二叉树的转换

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

各个树的根节点视为兄弟关系

森林中有n个非终端结点，对应转换的二叉树中右指针为空的结点数？

n个非终端结点的所有孩子结点中最后一个结点的右指针为空，每棵树相连后，最后一棵树的右指针必为空，一共n+1个空指针域。

森林F有15条边，25个结点，则F中包含多少颗树？

一棵树有n个结点n-1条边，每棵树结点数比边数少1，(25-15)10棵树25个结点比10条边数少10。

1.4. 树的遍历

1.4.1. 先根遍历

若树非空，先访问根结点，再依次对每棵子树进行先根遍历。

先序遍历结果

A B C D

A (B E F) (C G) (D H I J)

A (B(E K) F) (C G) (D H I J)

对应的二叉树转换为：

二叉树的先序遍历结果为：A B E K F C G D H I J

树的先根遍历序列与这棵树相应二叉树的先序序列相同。

1.4.2. 后根遍历

若树非空，先依次对每棵子树进行后根遍历，最后再访问根结点。

B C D A

( E F B) (G C) (H I J D) A

((K E) F B) (G C) (H I J D) A

中序遍历结果为：K E F B G C H I J D A

树的后根遍历序列与这棵树相应二叉树的中序序列相同。

1.4.3. 层序遍历

广度优先遍历

若树非空，则根节点入队
若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队
重复2直到队列为空

1.5. 森林的遍历

1.5.1. 先序遍历

若森林为非空，则按如下规则进行遍历:

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

B C D
(B E F) (C G) (D H I J)

(B (E K L) F) (C G) (D (H M) I J)

效果等同于依次对各个树进行先根遍历

效果等同于依次对二叉树的先序遍历

1.5.2. 中序遍历

若森林为非空，则按如下规则进行遍历:

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

B C D

( E F B) (G C) ( H I J D)

((K L E) F B) (G C) ((M H) I J D)

效果等同于依次对各个树进行后根遍历

效果等同于依次对二叉树的中序遍历

1.6. 树，二叉树，森林遍历对应

树	森林	二叉树
先根遍历	先序遍历	先序遍历
后根遍历	中序遍历	中序遍历

2. 二叉树

2.1. 基本概念

二叉树是n(n≥0)个结点的有限集合：

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

特点：(不同于度为2的有序树)

每个结点至多只有两棵子树
左右子树不能颠倒(二叉树是有序树)。

二叉树的五种状态：

2.2. 常考性质

2.2.1. n0=n2+1

设非空二叉树中度为0,1,2的结点个数分别为n₀,n₁,n₂，则n₀=n₂+1(叶子结点比二分支结点多一个)

假设树中结点总数为 n，则

n=n₀+n₁+n₂
n =n₁+2n₂+1

2-1得，n₀=n₂+1

2.2.2. 二叉树第i层至多结点数

二叉树第 i 层至多有 2ⁱ-1 个结点(i≥1)

m叉树第 i 层至多有 mⁱ-1 个结点(i≥1)

2.2.3. 高度为h的二叉树至多结点数

满二叉树：至多有 2^h − 1个结点

高度为h的二叉树，若树中只存在度为0或2的结点，结点个数为2h-1

2.3. 存储结构

2.3.1. 顺序存储

定义一个长度为 MaxSize 的数组 t ，按照从上至下、从左至右的顺序依次存储完全二叉树中的各个结点

#define MaxSize 100
struct TreeNode{
  //结点内数据元素
  ElemType value;
  //结点是否为空
  bool isEmpty;
};
TreeNode t[MaxSize];

//初始化
for(int i=0;i<MaxSize;i++){
  t[i].isEmpty=true;
}

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

i的左孩子 ——2i
i 的右孩子 ——2i+1
i的父节点 ——i/2
i 所在的层次 —— $\left \lceil log_{2}(n + 1)\right \rceil 或 \left \lfloor log_{2}n \right \rfloor$ + 1

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

判断 i 是否有左孩子? ——2i ≤ n
判断i是否有右孩子? ——2i+1≤n
判断i是否是叶子/分支结点?——i > $\left \lfloor n/2 \right \rfloor$

如果不是完全二叉树，依然按层序将各节点顺序存储，那么无法从结点编号反映出结点间的逻辑关系

最坏情况：高度为 h 且只有 h 个结点的单支树(所有结点只有右孩子)，也至少需要 2^h-1 个存储单元

结论：二叉树的顺序存储结构，只适合存储完全二叉树

2.3.2. 链式存储

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

n个结点有2n个指针域，除根结点外n-1个结点都有被指向的指针(总分支数)，故空链域为2n-(n-1)=n+1

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->rchild = p;

找到指定结点 p 的左/右孩子——超简单

如何找到指定结点 p 的父结点? ——只能从根开始遍历寻找

typedef struct BiTNode{
  ElemType data;
  struct BiTNode *lchild,*rchild;
  //父节点指针
  struct BiTNode *parent;
}BiTNode,*BiTree;

2.4. 二叉树的遍历

遍历：按照某种次序把所有结点都访问一遍

层序遍历：基于树的层次特性确定的次序规则

先/中/后序遍历：基于树的递归特性确定的次序规则，空间复杂度为O(n)

先序遍历：根左右(NLR)

中序遍历：左根右(LNR)

后序遍历：左右根(LRN)

2.4.1. 先序遍历

先序遍历(PreOrder)的操作过程如下:

若二叉树为空，则什么也不做;
若二叉树非空:

访问根结点；

先序遍历左子树;

先序遍历右子树。

2.4.1.1. 递归算法

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);
  }
}

2.4.1.2. 非递归算法

//非递归算法
void PreOrder(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->lchild;
    }
  }
}

2.4.2. 中序遍历

中序遍历(InOrder)的操作过程如下:

若二叉树为空，则什么也不做;
若二叉树非空:

中序遍历左子树;

访问根结点；

中序遍历右子树。

2.4.2.1. 递归算法

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);
  }
}

2.4.2.2. 非递归算法

沿着根的左孩子开始，依次入栈，直到左孩子为空
栈顶元素出栈并访问该元素，若其右孩子为空，继续执行2，若其右孩子非空，则右子树转为执行1。

//非递归算法
void InOrder(BiTree T){
  InitStack(S);
  BiTree p = T;
  while(p||!IsEmpty(S)){
    if(p){
      Push(S,p);
      p=p->lchild;
    }
    else{
      Pop(S,p);
      visit(p);
      p=p->lchild;
    }
  }
}

2.4.3. 后序遍历

后序遍历(PostOrder)的操作过程如下:

若二叉树为空，则什么也不做;
若二叉树非空:

后序遍历左子树;

后序遍历右子树；

访问根结点；

2.4.3.1. 递归算法

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);
  }
}

2.4.3.2. 非递归算法

//非递归算法
void PostOrder(BiTree T){
  InitStack(S);
  BiTree p = T;
  //指向最近访问的结点
  BiTree r = NULL;
  while(p||!IsEmpty(S)){
    if(p){
      Push(S,p);
      p=p->lchild;
    }
    else{
      GetTop(S,p);
      if(p->rchild!=NULL&&p->rchild!=r){
        p=p->rchild;
      }
      else{
      	Pop(S,p);
        r = p;
        //出栈访问完就完成了p为根的子树，p置空
      	p=NULL;
      }
    }
  }
}

2.4.4. 层序遍历

算法思想:

初始化一个辅助队列
根结点入队
若队列非空，则队头结点出队，访问该结点，并将其左、右孩子插入队尾(如果有的话)
重复3直至队列为空

//二叉树结点（链式存储）
typedef struct BiTNode{
  ElemType data;
  struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

//链式队列结点
typedef struct LinkNode{
  //存指针
  BiTNode *data;
  struct 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);
    }
  }
}

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

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

前序、后序、层序序列的两两组合无法唯一确定一科二叉树

2.4.5.1. 前序 + 中序遍历序列

前序遍历：根结点、前序遍历左子树、前序遍历右子树

中序遍历：中序遍历左子树、根结点、中序遍历右子树

eg:

/*
已知先序遍历数组 pre[]
中序遍历数组 in[]
*/
BiTNode * create(int prel,int prer,int inl,int inr){
  if(prel>prer){
    return;
  }
  BiTNode *root=(BiTNode*)malloc(sizeof(BiTNode));
  //先序遍历都是从根开始
  root->data = pre[prel];
  int i=inl;
  //求根在中序遍历中的位置
  for(;i<=inr;i++){
    if(in[i]==pre[prel]){
      break;
    }
  }
  //得左子树数量
  int left = i-inl;
  //分别处理左右子树
  root->lchild = create(prel+1,prel+left,inl,i-1);
  root->rchild = create(prel+left+1,prer,i+1,inr);
  return root;
}

2.4.5.2. 后序 + 中序遍历序列

后序遍历：前序遍历左子树、前序遍历右子树、根结点

中序遍历：中序遍历左子树、根结点、中序遍历右子树

Eg:

/*
已知后序遍历数组 post[]
中序遍历数组 in[]
*/
BiTNode * create(int postl,int postr,int inl,int inr){
  if(postl>postr){
    return;
  }
  BiTNode *root=(BiTNode*)malloc(sizeof(BiTNode));
  //后序遍历为左右根
  root->data = post[postr];
  int i=inl;
  //求根在中序遍历中的位置
  for(;i<=inr;i++){
    if(in[i]==post[postr]){
      break;
    }
  }
  //得左子树数量
  int left = i-inl;
  //分别处理左右子树
  root->lchild = create(postl,postl+left-1,inl,i-1);
  root->rchild = create(prel+left,prer-1,i+1,inr);
  return root;
}

2.4.5.3. 层序 + 中序遍历序列

Eg:

/*
已知层序遍历数组 level[]
中序遍历数组 in[]
*/
BiTNode * create(int levell,int levelr,int inl,int inr){
  if(inl>inr){
    return;
  }
  int i = inl;
  inr flag = 0;
  //每一个出现在中序中的元素为根
  for(;levell<=levelr;levell++){
    for(;i<=inr;i++){
      if(in[i]==level[levell]){
        flag=1;
        break;
      }
    }
    if(flag==1){
      break;
    }
  }
  BiTNode *root=(BiTNode*)malloc(sizeof(BiTNode));
  root->data = in[i];
  root->lchild = create(levell+1,levelr,inl,i-1);
  root->rchild = create(levell+1,levelr,i+1,inr);
  return root;
}

2.4.6. 满二叉树-得先序求后序

int pre[],post[];
void PreToPost(int prel,int prer,int postl,int postr){
  if(prel>prer){
    return;
  }
  post[postr]=pre[prel];
  int half = (prer-prel)/2;
  PreToPost(prel+1,prel+half,postl,postl+half-1);
  PreToPost(prel+half+1,prelr,postl+half,postr-1);
}

2.5. 求二叉树的深度

2.5.1. 递归版本

int treeDepth(BiTree T){
  if(T==NULL){
    return 0;
  }
  int l = treeDepth(T->lchild);
  int r = treeDepth(T->rchild);
  //树深度=Max(左子树深度,右子树深度)+1
  return l>r?(l+1):(r+1);
}

2.5.2. 非递归版本

int treeDepth(BiTree T){
  InitQueue(Q);
  //保留本层最后一个结点
  BiTNode *last =T;
  BiTNode *newNode = T;
  EnQueue(Q,T);
  int depth = 1;
  while(!IsEmpty(Q)){
    BiTNode r;
    DeQueue(Q,r);
    if(r->lchild!=NULL){
      EnQueue(Q,r->lchild);
      newNode = r->lchild;
    }
    if(r->rchild!=NULL){
      EnQueue(Q,r->rchild);
      newNode = r->rchild;
    }
    //到达同层最后一个结点，更新到下一层最后一个结点
    if(last==r){
      depth++;
      last = newNode;
    }
  }
  return depth;
}

2.6. 满二叉树

一棵高度为h，且含有2^h - 1个结点的二叉树

特点:

只有最后一层有叶子结点
不存在度为 1 的结点
按层序从 1 开始编号，结点 i 的左孩子为 2i，右孩子为2i+1；结点i的父节点为𝑖/2(如果有的话)

2.7. 完全二叉树

当且仅当其每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应时，称为完全二叉树

特点:

只有最后两层可能有叶子结点
最多只有一个度为1的结点
按层序从 1 开始编号，结点 i 的左孩子为 2i，右孩子为2i+1；结点i的父节点为𝑖/2(如果有的话)
i$\leq$$\left \lfloor n/2 \right \rfloor $为分支结点，i>$\left \lfloor n/2 \right \rfloor $为叶子结点
如果某结点只有一个孩子，那么一定是左孩子

2.7.1. 常见考点

2.7.1.1. 有n个结点的完全二叉树的高度h为?

具有n个(n > 0)结点的完全二叉树的高度h为$\left \lceil log_{2}(n + 1) \right \rceil$或$\left \lfloor log_{2}n \right \rfloor$+ 1

高为h的满二叉树共有2^h −1个结点

高为h-1的满二叉树共有2^h-1−1个结点

第 i 个结点所在层次为 $\left \lceil log_{2}(n + 1) \right \rceil$ 或 $\left \lfloor log_{2}n \right \rfloor$+1

2.7.1.2. 由结点数n推出度为0,1,2的结点个数

完全二叉树最多只有一个度为1的结点，即 n₁=0或1
n₀ = n₂ + 1 -> n₀ + n₂ 一定是奇数

若完全二叉树有2k个(偶数)个结点，则必有n₁=1，n₀ = k，n₂ = k-1

若完全二叉树有2k-1个(奇数)个结点，则必有n₁=0，n₀ = k，n₂ = k-1

2.8. 线索二叉树

传统的二叉链表仅体现一种父子关系，不能直接得到结点遍历中的前驱或后继。n个结点共n+1个空指针(度为1—1个空指针，度为2—2个空指针，总空指针数=n₁+2n₂=n₁+n₀+1+n₂=n+1)。引入线索二叉树正是为了加快查找结点前驱和后继的速度。而二叉树的线索化就是将二叉链表的空指针改为指向前驱或后继的线索。而前驱或后继的信息只有在遍历时才能得到，因此线索化实质是遍历一次二叉树。

线索二叉树是一种物理结构：二叉树是逻辑结构，线索二叉树是加上线索后的链表结构。

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

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

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

	中序线索二叉树	先序线索二叉树	后序线索二叉树
找前驱	☑️	$\times$	☑️
找后继	☑️	☑️	$\times$

2.8.1. 中序线索二叉树

2.8.1.1. 存储结构

//二叉树结点
typedef struct BiTNode{
  ElemType data;
  struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

//线索二叉树结点
typedef struct ThreadNode{
  ElemType data;
  struct ThreadNode *lchild,*rchild;
  //左，右线索标志
  //tag==0，表示指针指向孩子 
  //tag==1，表示指针是“线索”
  int ltag,rtag;
}ThreadNode,*ThreadTree;

2.8.1.2. 概述

二叉树的中序遍历序列如何找到指定结点p在中序遍历序列中的前驱？如何找到p的中序后继？

思路:

从根节点出发，重新进行一次中序遍历，指针q记录当前访问的结点，指针 pre 记录上一个被访问的结点

当q==p时，pre为前驱
当pre==p时，q为后继

//辅助全局遍历，用于查找结点p的前驱
//p指向目标结点
BiTNode *p;
//指向当前访问结点的前驱
BiTNode *pre=NULL;
//用于记录最终结果
BiTNode *final = NULL;

//访问结点q
void visit(BiTNode *q){
  //当前访问结点刚好是结点p
  if(q==p){
    //找到p的前驱
    final = pre;
  }else{
    //pre指向当前访问的结点
    pre=q;
  }
}

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

2.8.1.3. 中序线索化

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

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

void visit(ThreadNode *q){
  //左子树为空，建立前驱线索
  if(q->lchild==NULL){
    q->lchild=pre;
    q->ltag=1;
  }
  if(pre!=NULL&&pre->rchild==NULL){
    //建立前驱结点的后继线索
    pre->rchild=q;
    pre->rtag=1;
  }
  pre=q;
}

//全局变量pre，指向当前访问结点的前驱
ThreadNode *pre = NULL;

//创建中序线索二叉树
void CreateInThread(ThreadTree T){
  if(T!=NULL){
    //中序线索化
    InTread(T);
    if(pre->rchild==NULL){
      //处理最后一个结点
      pre->rtag=1;
    }
  } 
}

2.8.1.4. 找后继

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

若 p->rtag==1，则 next = p->rchild
若 p->rtag==0

左根 右

左根 (左 根右)

左根 ((左 根右) 根右)

next = 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(TreadNode *p=FirstNode(T);p!=NULL;p=NextNode(p)){
    visit(p);
  }
}

2.8.1.5. 找前驱

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

若 p->ltag==1，则 pre = p->lchild
若 p->ltag==0

左 根右
(左根 右) 根右

(左根 (左根 右) ) 根右

pre = 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 RevInOrder(ThreadNode *T){
  for(TreadNode *p=LastNode(T);p!=NULL;p=preNode(p)){
    visit(p);
  }
}

2.8.2. 先序线索二叉树

2.8.2.1. 存储结构

2.8.2.2. 先序线索化

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

void PreThread(ThreadTree T){
  if(T!=NULL){
    visit(T);
    /*
    不加T->ltag==0，
    将与visit中的q->lchild=pre;
    再次访问又将是q->lchild,
    会导致线索成圈
    */
    if(T->ltag==0){
    	PreThread(T->lchild);
    }
    PreThread(T->rchild);
  }
}

void visit(ThreadNode *q){
  //左子树为空，建立前驱线索
  if(q->lchild==NULL){
    q->lchild=pre;
    q->ltag=1;
  }
  if(pre!=NULL&&pre->rchild==NULL){
    //建立前驱结点的后继线索
    pre->rchild=q;
    pre->rtag=1;
  }
  pre=q;
}

//全局变量pre，指向当前访问结点的前驱
ThreadNode *pre = NULL;

//创建中序线索二叉树
void CreatePreThread(ThreadTree T){
  if(T!=NULL){
    //中序线索化
    InTread(T);
    if(pre->rchild==NULL){
      //处理最后一个结点
      pre->rtag=1;
    }
  } 
}

2.8.2.3. 找后继

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

若 p->rtag==1，则 next = p->rchild
若 p->rtag==0：

若p有左孩子，则先序后继为左孩子

根 左 右
根 (根 左右) 右

若p没有左孩子，则先序后继为右孩子

根 右

根 (根 左右)

ThreadNode *NextNode(ThreadNode *p){
  //有左孩子
  if(p->ltag==0){
    return p->lchild;
  }
  else{
    //有后继指针or有右孩子
    return p->rchild;
  }
}

2.8.2.4. 找前驱

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

若 p->ltag==1，则 next = p->lchild
若 p->ltag==0

根 左右

先序遍历中，左右子树中的结点只可能是根的后继，不可能是前驱

除非用土办法从头开始先序遍历

改用三叉链表可以找到父节点

如果能找到 p 的父节点，且p是左孩子

根 左右

根 (根 左右) 右

p的父节点即为其前驱
如果能找到 p 的父节点，且 p是右孩子，其左兄弟为空

根 右
根 (根 左右)

p的父节点即为其前驱
如果能找到 p 的父节点，且p是右孩子，其左兄弟非空

根 左 右

p的前驱为左兄弟子树中最后一个被先序遍历的结点

2.8.3. 后序线索二叉树

2.8.3.1. 存储结构

2.8.3.2. 后序线索化

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

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

void visit(ThreadNode *q){
  //左子树为空，建立前驱线索
  if(q->lchild==NULL){
    q->lchild=pre;
    q->ltag=1;
  }
  if(pre!=NULL&&pre->rchild==NULL){
    //建立前驱结点的后继线索
    pre->rchild=q;
    pre->rtag=1;
  }
  pre=q;
}

//全局变量pre，指向当前访问结点的前驱
ThreadNode *pre = NULL;

//创建中序线索二叉树
void CreatePostThread(ThreadTree T){
  if(T!=NULL){
    //中序线索化
    InTread(T);
    if(pre->rchild==NULL){
      //处理最后一个结点
      pre->rtag=1;
    }
  } 
}

2.8.3.3. 找前驱

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

若 p->ltag==1，则 pre = p->lchild
若 p->ltag==0

若p有右孩子，则后序前驱为右孩子

左 右 根

左 (左右 根) 根

若p没有右孩子，则后序前驱为左孩子

左 根

(左右 根) 根

ThreadNode *PreNode(ThreadNode *p){
  if(p->rtag == 0){
    return p->rchild;
  }
  else{
    return p->lchild;
  }
}

2.8.3.4. 找后继

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

若 p->rtag==1，则 next = p->rchild
若 p->rtag==0

左右根

后序遍历中，左右子树中的结点只可能是根的前驱，不可能是后继

改用三叉链表可以找到父节点

如果能找到 p 的父节点，且p是右孩子

左右 根

左 (左右 根) 根

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

左 根
(左右 根) 根

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

p的后继为右兄弟子树中第一个被后序遍历的结点

2.8.3.5. 后序线索树仍需栈的支持

结点6的rchild指向的是其右孩子结点7，而其后继实际为双亲结点4

2.9. 二叉排序树

二叉排序树，又称二叉查找树 (BST，Binary Search Tree)，可用于元素的排序、搜索

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

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

左子树结点值 < 根结点值 < 右子树结点值 -> 进行中序遍历，可以得到一个递增的有序序列

2.9.1. 查找

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

空间复杂度 - O(1)

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;
}

递归实现——空间复杂度为O(h)

BSTNode *BST_Search(BSTree T,int key){
  if(T==NULL){
    return NULL;
  }
  if(key==T->key){
    return T;
  }
  else if(key<T->key){
    //小于根结点，在左子树查找
     BST_Search(T->lchild,key);
  }
  else{
     //大于根结点，在右子树查找
     BST_Search(T->rchild,key);
  }
  return T;
}

2.9.2. 二叉排序树的插入

若原二叉排序树为空，则直接插入结点;否则，若关键字k小于根结点值，则插入到左子树，若关键字k大于根结点值，则插入到右子树

新插入的结点一定是叶子

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

//递归版本
bool BST_Insert(BSTree &T,int k){
  if(T==NULL){
    T=(BSTNode*)malloc(sizeof(BSTNode));
    T->key=k;
    T->lchild=NULL;
    T->rchild=NULL;
    return true;
  }
  else if(k==T->key){
    return false;
  }
  else if(k<T->key){
    return BST_Insert(T->lchild,k);
  }
  else{
    return BST_Insert(T->rchild,k);
  }
}

2.9.3. 二叉排序树的构造

void createBST(BSTree &T,int str[],int n){
  BSTree T=NULL;
  int i=0;
  while(i<n){
    BST_Insert(T,str[i]);
    i++;
  }
}

不同的关键字序列可能得到同款二叉排序树

按照序列str={50, 26, 21, 30, 66, 60, 70, 68}建立BST

按照序列str={26, 21, 30, 50, 60, 66, 68, 70}建立BST

2.9.4. 二叉排序树的删除

若被删除结点是叶结点，则直接删除，不会破坏二叉排序树的性质。
若结点只有一棵左子树或右子树，则让其子树成为其父结点的子树，替代结点的位置。
若结点有左、右两棵子树，则令其直接后继(或直接前驱)替代，然后从二叉排序树中删去这个直接后继(或直接前驱)，这样就转换成了第一或第二种情况

中序遍历中：
- 取结点的后继：取其右子树中最左下结点(该节点一定没有左子树)
- 取结点的前驱：取其左子树中最右下结点(该节点一定没有右子树)

2.9.5. 查找效率分析

查找长度——在查找运算中，需要对比关键字的次数称为查找长度。

查找失败的平均查找长度 ASL(Average Search Length)

ASL_失败 = $\frac{(37 + 42)}{9}$ = 3.22

ASL_成功 = $\frac{11+22+34+41}{8}$ = 2.625

2.10. 平衡二叉树

2.10.1. 定义

平衡二叉树(Balanced Binary Tree)，G. M. Adelson-Velsky和 E. M. Landis - AVL树

树上任一结点的左子树和右子树的深度之差不超过1。能有更高的搜索效率

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

平衡二叉树结点的平衡因子的值只可能是−1、0或1。

2.10.2. 存储结构

typedef struct AVLNode{
  int key;
  int balance;
  struct AVLNode *lchild,*rchild;
}AVLNode,*AVLTree;

2.10.3. 平衡二叉树的插入

在二叉排序树中插入新结点后，从插入点往回找到第一个不平衡结点，调整以该结点为根的子树。即每次调整的对象都是“最小不平衡子树”。

2.10.3.1. 调整最小不平衡子树LL

LL平衡旋转(右单旋转)。由于在结点A的左孩子(L)的左子树(L)上插入了新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要一次向右的旋转操作。将A的左孩子B向右上旋转代替A成为根结点，将A结点向右下旋转成为B的右子树的根结点，而B的原右子树则作为A结点的左子树。

代码实现：

typedef struct AVLNode{
  int key;
  int balance;
  struct AVLNode *lchild,*rchild;
}AVLNode,*AVLTree;

//实现根右旋
void R(AVLNode* &root){
	AVLNode *B = root->lchild;
	root->lchild = B->rchild;
	B->rchild = root;
	root = B;
  return root;
}

Eg:

2.10.3.2. 调整最小不平衡子树RR

RR平衡旋转(左单旋转)。由于在结点A的右孩子(R)的右子树(R)上插入了新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，需要一次向左的旋转操作。将A的右孩子B向左上旋转代替A成为根结点，将A结点向左下旋转成为B的左子树的根结点，而B的原左子树则作为A结点的右子树。

typedef struct AVLNode{
  int key;
  int balance;
  struct AVLNode *lchild,*rchild;
}AVLNode,*AVLTree;

//实现根左旋
void L(AVLNode* &root){
	AVLNode *B = root->rchild;
	root->rchild = B->lchild;
	B->lchild = root;
	root = B;
  return root;
}

2.10.3.3. 调整最小不平衡子树(LR)

LR平衡旋转(先左后右双旋转)。由于在A的左孩子(L)的右子树(R)上插入新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先左旋转后右旋转。先将A结点的左孩子B的右子树的根结点C向左上旋转提升到B结点的位置，然后再把该C结点向右上旋转提升到A结点的位置

typedef struct AVLNode{
  int key;
  int balance;
  struct AVLNode *lchild,*rchild;
}AVLNode,*AVLTree;

//1.先右子树左旋——L(root->lchild);
void L(AVLNode* &root){
	AVLNode *B = root->rchild;
	root->rchild = B->lchild;
	B->lchild = root;
	root = B;
  return root;
}

//2. 再根右旋——R(root);
void R(AVLNode* &root){
	AVLNode *B = root->lchild;
	root->lchild = B->rchild;
	B->rchild = root;
	root = B;
  return root;
}

2.10.3.4. 调整最小不平衡子树(RL)

RL平衡旋转(先右后左双旋转)。由于在A的右孩子(R)的左子树(L)上插入新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先右旋转后左旋转。先将A结点的右孩子B的左子树的根结点C向右上旋转提升到B结点的位置，然后再把该C结点向左上旋转提升到A结点的位置。

typedef struct AVLNode{
  int key;
  int balance;
  struct AVLNode *lchild,*rchild;
}AVLNode,*AVLTree;

//1.先左子树右旋——R(root->rchild);
void R(AVLNode* &root){
	AVLNode *B = root->lchild;
	root->lchild = B->rchild;
	B->rchild = root;
	root = B;
  return root;
}

//2. 再根左旋——L(root);
void L(AVLNode* &root){
	AVLNode *B = root->rchild;
	root->rchild = B->lchild;
	B->lchild = root;
	root = B;
  return root;
}

2.10.4. 查找效率分析

《An algorithm for the organizaSon of informaSon》——G.M. Adelson- Velsky 和 E.M. Landis ,1962

若树高为h，则最坏情况下，查找一个关键字最多需要对比 h 次，即查找操作的时间复杂度不可能超过 O(h)

平衡二叉树——树上任一结点的左子树和右子树的高度之差不超过1。假设以n_h表示深度为h的平衡树中含有的最少结点数。

则有n₀ =0，n₁ =1，n₂=2，并且有 ${\color{Red} n_{h}=n_{h−1}+n_{h−2}+1}$

可以证明含有n个结点的平衡二叉树的最大深度为O(log₂n) ，平衡二叉树的平均查找长度为O(log₂n)

2.11. 哈夫曼树

2.11.1. 带权路径长度

结点的权：有某种现实含义的数值(如:表示结点的重要性等)

结点的带权路径长度：从树的根到该结点的路径长度(经过的边数)与该结点上权值的乘积

树的带权路径长度：树中所有叶结点的带权路径长度之和 (WPL, Weighted Path Length)

WPL = $\sum_{i=1}^{n}w_{i}l_{i}$

WPL = (5+1+10+3)x3=57

2.11.2. 哈夫曼树的定义

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

2.11.3. 哈夫曼树的构造

给定n个权值分别为w₁, w₂,…, w_n的结点，构造哈夫曼树的算法描述如下:

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

Eg:

WPL_min=1x7+2x3+3x2+4x1+4x2=31

2.11.4. 哈夫曼树特点

每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大
哈夫曼树的结点总数为2n − 1
哈夫曼树中不存在度为1的结点。
哈夫曼树并不唯一，但WPL必然相同且为最优(结点放置顺序左右任意)

2.11.5. 哈夫曼编码

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

电报——点、划两个信号(二进制0/1)

假设，100题中有80题选C，10题选A，8题选B，2题选D

2.11.5.1. 固定长度编码

每个字符用相等长度的二进制位表示

构造树——并不是哈夫曼树：

每个字符用长度为2的二进制表示：

A——00

B——01

C——10

D——11

故所有答案的二进制长度(WPL)=80x2+10x2+8x2+2x2=200 bit

2.11.5.2. 可变长度编码

允许对不同字符用不等长的二进制位表示

若没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码

构造哈夫曼树