系列链接
第一章 概述	第二章 线性表	第三章 栈与队列	第四章 串
第五章 树与二叉树	第六章 图	第七章 查找	第八章 排序

🔥树的基本概念

• 树是一种递归定义的结构，树的结构示意图如下：
  
• 没有结点的树叫空树（∅）
• 非空树的特性：

1. 有且仅有一个根结点
2. 没有后继的结点成为叶子结点（终端结点）
3. 有后继的结点成为分支结点（非终端结点）
4. 除了根结点外，任何结点有且仅有一个前驱
5. 每个节点可以有0个或多个后继

• 子树的示意图如下：
  
• 树从左到右顺序可以更改，不影响逻辑的，成为无序树，反之则为有序树

✍结点关系

1. 祖先结点：逆着路径向上的所有结点都是祖先结点
2. 子孙结点：与祖先结点相反
3. 父节点：顾名思义
4. 孩子结点：父节点相反
5. 兄弟结点：同一个父节点的所有孩子结点之间互为兄弟结点
6. 堂兄弟结点：同一层的结点之间互为堂兄弟结点
7. 路径：只能从上往下走
8. 路径长度：经过的边的个数

✍属性

1. 结点的层次：从上往下数
2. 结点的高度：从下往上数
3. 数的高度（深度）：总层数
4. 结点的度：有几个孩子结点（分支），非叶子结点度大于0
5. 树的度：各结点度中的最大值

✍其他概念

• 森林：多个无交集的树组成的集合。森林和树有相互转化的问题

🔥树的性质

• 结点数 = 总度数 + 1 （这个1就是根结点）
• 度为m的树与m叉树：

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

　也就是三叉树有可能是一个二叉树甚至线性表，度为m的树一定是三叉树

• 度为m的树或者m叉树第i层至多有m^i-1个结点
• 高度为h的m叉树最多有 (m^h-1)/(m-1) 个结点，最少有h个结点
• 高度为h、度为m的树至少有h+m-1个结点
• 有n个结点的m叉树最小高度为 log_m(n(m-1)+1)

🔥二叉树

✍基本概念

• 二叉树是n（n≥0）个结点的有限集合：要么是空二叉树，要么由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左右子树也都是二叉树（可以是空的）。
• 二叉树特点：

1. 每个结点至多有两个子树
2. 左右子树不能颠倒（有序树）

✍特殊的二叉树

• 满二叉树：

1. 除了叶子结点都有两个孩子结点，只有最后一层有叶子结点
2. 不存在度为1的结点
3. 按层序从1开始编号，结点i左孩子为 2i ，右孩子为 2i+1 ；结点i的父节点为 i/2（如果有）

• 完全二叉树：去掉任意个满二叉树编号最大的结点（必须是最大的连续的几个），最多只有一个度为1的结点。显然，满二叉树属于完全二叉树。

• 二叉排序树：一棵二叉树要么是空二叉树，要么具有如下性质的二叉树：

1. 左子树上所有结点的关键字均小于根结点
2. 右子树上所有结点的关键字均大于根结点
3. 左右子树各是一棵二叉排序树

• 平衡二叉树：任意结点的左子树和右子树深度之差不超过1。平衡二叉树高度通常不会很高，尽可能的宽，使得搜索变得更快，更高效

✍二叉树的顺序存储

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

• 定义一个数组，从上到下，从左往右的顺序依次存储完全二叉树的各个结点
• 非完全二叉树顺序存储可以将元素与完全二叉树一一对应，在空缺的地方不存数据，这会造成大量空闲的空间，所以二叉树一般不用顺序存储

✍二叉树的链式存储

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

• 这种实现方式成为二叉链表
• 没有孩子结点的指针就是空指针，n个结点的二叉链表有n+1个空链域（空指针）
• 父指针通常在需要经常反向查找的情况下使用
• 编程过程中要熟悉如下结点之间的序列关系：

✍二叉树的遍历

先中后序遍历

• 先序遍历：根->左->右 的顺序遍历(NLR)
• 中序遍历：左->根->右 的顺序遍历(LNR)
• 后序遍历：左->右->根 的顺序遍历(LRN)
  
• 二叉树的先中后序遍历也能获得之前章节的前中后缀表达式：
  
• 代码实现，以先序为例

void PreOrder(BiTree T){
  if(T!=NULL){
    visit(T);       //访问根结点，visit表示需要对结点进行的操作
    PreOrder(T->lchild);    //递归遍历左子树
    PreOrder(T->rchild);    //递归遍历右子树
  }
}

• 对于中、后序遍历只需更改if下的三条语句顺序即可
• 先序遍历为例，实现过程如下，一条路一直往左边走，只要左边有路就走到底，左边走完回头走右边，右边走完再往回走，如此往复。也就是在每个路口（结点）都得作出判断，优先走左边，然后走右边，最后回头。
  
• 因此，每个结点最终都会经过三次，先序遍历时结点在第一次会被访问。

层序遍历

• 按一层一层的顺序遍历（从上到下，从左往右）
• 算法思想：

1. 初始化一个辅助队列
2. 根结点入队
3. 若队列非空，则队头结点出队，访问该结点，并将该结点的左右孩子结点依次入队（如果有的话）
4. 重复3直到队列为空

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);     //右孩子入队
  }
}

✍线索二叉树

• 以中序遍历为例，将中序遍历序列中每一个结点的前驱作为左孩子，后继作为右孩子，形成中序线索二叉树，这种时候的左右孩子就是左右线索。如果没有线索（在遍历序列头尾）就是空指针。之前提到的二叉树n+1个空链域就刚好用来作为线索。
• 线索化的目的就是利于找前驱后继
  

typedef struct ThreadNode{
  ElemType data;
  struct ThreadNode *lchild,*rchild;
  int ltag,rtag;        //左右线索标志
}ThreadNode,*ThreadTree;

• 如上，当对应ltag为0，说明该结点的左孩子指针指向的确实是左孩子结点，为1代表指针是线索。rtag同理。
• 线索化实现，中序为例，其他的略有不同，不做具体记录

• 线索化之后，中序二叉树找前驱后继的方法如下
  
  
• 先序线索二叉树找不到前驱，后序线索二叉树找不到后继，除非用原始方法，从根开始一个一个找

🔥树的存储结构

✍双亲表示法（顺序存储）

• 如上，每个结点的父结点“指针”（实际是整型）存放的是父结点的物理位置索引

✍孩子表示法（顺序+链式存储）

• 如上，每个结点指针指向第一个孩子

✍孩子兄弟表示法（链式存储）

• 结点的指针分别指向第一个孩子和右兄弟，把它们分别视作左右孩子，实质上就完成了树与二叉树的转化

✍森林和二叉树转换

• 和孩子兄弟表示法一样，把森林的各个根结点视作兄弟结点连起来，就变成一个二叉树存储起来。反过来，把森林的二叉树最右边一路依次拆开即可变成森林

🔥树的遍历

✍先根遍历

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

✍后根遍历

• 和先根相反，先进入子树，最后访问根结点

✍层次遍历

• 方法和二叉树的层序遍历一样，用队列实现，不再赘述
• 层次遍历也成为对树的广度优先遍历，先根遍历和后根遍历是深度优先遍历

🔥森林的遍历

• 先序遍历：相当于把每个树看作子树依次进行先根遍历
• 中序遍历；相当于把森林转换的二叉树进行中序遍历

🔥二叉排序树

• 又名二叉查找树（BST）特点如下：

1. 左子树上所有结点的关键字均小于根结点
2. 右子树上所有结点的关键字均大于根结点
3. 左右子树各是一棵二叉排序树

• 中序遍历一个二叉排序树就可以得到递增序列，这利于查找

✍查找

//二叉排序树中查找值为key的结点
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;         //查到就返回结果，查不到会返回NULL
}

• 也可以通过递归实现：

BSTNode *BSTSearch(BSTree T,int key){
  if(T==NULL)
    return NULL;    //查不到
  if(key==T->key)
    return T;       //成功
  else if(key< T->key)
    return BSTSearch(T->lchild, key);   //左子树
  else
    return BSTSearch(T->rchild, key);   //右子树
}

• 查找长度，即需要查找对比的步数，反应时间复杂度
• 查找成功的平均查找长度ASL：任意结点查找的机会相同，那么平均需要进行的对比次数。相同数据高度越大的树ASL越大，若排序树是平衡二叉树那么ASL就会最小。
• 查找失败的平均查找长度ASL：每个空指针查找的机会相同，以此进行求平均，也是越高的树ASL越大。

✍插入

• 方法类似查找，当值小于根结点就插入左子树，反之插入右子树，如果查到一样的值就不能插入。
• 也可以使用递归和循环两种方法实现，不再记录

✍构造

✍删除

1. 删除叶子结点，不破坏排序树性质
2. 若该结点只有左或者右子树之一，则让该子树直接代替该结点的位置即可（简单地上移一格）
3. 若结点有左右两个子树，可以用其直接后继或直接前驱结点替代其位置，再删去这个直接后继或者前驱原来的位置即可

🔥平衡二叉树

• 简称AVL，任意结点的左子树和右子树深度之差不超过1。
• 平衡因子：一个结点左子树高度减去右子树高度的差
• 使得二叉树平衡的方法思路：将最小不平衡子树进行改造，所有不平衡都会解决
• 导致不平衡的原因及对策：

1. LL：在A的左孩子的左子树中插入导致不平衡
   LL平衡旋转（右单旋转）。由于在结点A的左孩子(L)的左子树(L)上插入了新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要一次向右的旋转操作。将A的左孩子B向右上旋转代替A成为根结点，将A结点向右下旋转成为B的右子树的根结点，而B的原右子树则作为A结点的左子树。
2. RR：在A的右孩子的右子树中插入导致不平衡
   RR平衡旋转（左单旋转）。由于在结点A的右孩子（R）的右子树(R)上插入了新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，需要一次向左的旋转操作。将A的右孩子B向左上旋转代替A成为根结点，将A结点向左下旋转成为B的左子树的根结点，而B的原左子树则作为A结点的右子树。
3. LR：在A的左孩子的右子树中插入导致不平衡
   LR平衡旋转（先左后右双旋转）。由于在A的左孩子(L)的石子树（R）上抽人新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先左旋转后右旋转。先将A结点
   的左孩子B的右子树的根结点c向左上旋转提升到B结点的位置，然后再把该c结点向右上旋转提升到A结点的位置。
4. RL：在A的右孩子的左子树中插入导致不平衡
   RL平衡旋转（先右后左双旋转）。由于在A的右孩子（R）的左子树(L)上插入新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先右旋转后左旋转。先将A结点的右孩子B的左子树的根结点c向右上旋转提升到B结点的位置，然后再把该C结点向左上旋转提升到A结点的位置。

🔥哈夫曼树

• 结点的权：给结点赋予一个特殊意义的值，类似重要性等现实意义，父结点权值为两个孩子结点（如果有的话）权值之和
• 结点的带权路径长度：根到该结点的路径长度 与 结点权值 的 乘积
• 树的带权路径长度（WPL）：所有叶子结点的带权路径长度和
• 含有n个带权叶子结点的二叉树中，带权路径长度最小的二叉树成为哈夫曼树，也称最优二叉树，可能不止一个
• 哈夫曼树构造方法如下：
  
• 本质上是让权值大的结点尽可能靠上层，那样其带权路径长度会尽可能小

哈夫曼树的应用
固定长度编码：每个字符用等长度二进制表示（类似ASCII码）
可变长度编码：每个字符允许用不同长度二进制表示
前缀编码：可变长度编码要求没有一个编码是另一个编码的前缀
哈夫曼编码：用哈夫曼树获得的编码，字符集中的每个字符作为叶子结点，每个字符的出现频度作为权值，以此构建哈夫曼树。方案也不唯一，但编码量一样，常用于压缩数据