二叉树的遍历（递归）

先序遍历（根左右）

中序遍历（左根右）

后序遍历（左右根）

==试卷中圆圈1的变化是主要考点：它的位置，所实现的功能==

层次遍历

过程：

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

代码：

由遍历序列构造二叉树

先序，后序，层次都可以知道谁是根，然后再结合中序谁在左谁在右，就可以搞出来二叉树的样子，
所以==必须要有中序才能搞出来二叉树的样子==

先序+后序： ==顺序相反是父子，顺序相同是兄弟==

二叉树遍历（非递归）

其实就是用自己定义的栈，来代替系统栈以提高效率

先序遍历非递归算法

中序遍历的非递归算法

后序遍历非递归算法

先求逆后序遍历序列，逆后序遍历序列是先序遍历序列对左右子树遍历顺序交换所得到的结果。

逆后序遍历再出一次栈就是后序遍历了

线索二叉树

1. 为什么引入线索二叉树？
   树的前中后遍历序列是线性的，如果想要访问遍历序列中某个结点的前序或者后继，只能从头开始访问，非常不方便。
   链式存储的二叉树中有n+1个空指针
2. 数据结构：
   
   

二叉树的应用

二叉排序树/二叉查找树（BST）

1. 定义：
   中序遍历可得到递增的有序序列
2. 查找效率：
   查找成功：
   
   查找失败：
   
3. 二叉排序vs二分查找
   二叉排序树的查找是不唯一的（同一批数据按照不同的顺序插入，得到的排序树是不一样的），二分查找的判定树是唯一的。
   二叉排序的插入删除只需修改指针，时间复杂度是log2n，但是二分查找的插入和删除要移动节点，时间复杂度是logn

4. 插入

   • 新插入的结点一定是叶子结点
     

5. 删除

   1. p是叶子结点：直接删除
   2. p只有左子树或只有右子树：p的孩子结点代替p
   3. p有左子树也有右子树：用中序遍历的直接后继代替p,随后删除这个后继

平衡二叉树（AVL）

1. 定义：在二叉排序树的基础上，进一步要求任意结点左右子树高度之差不超过1。
2. 调整不平衡：
   LL（右转）：在左孩子的左子树中插入（==这都是相较于那个不平衡的点来说的==）
   
   RR（左转）：右孩子的右子树中插入
   
   LR（先左后右）：左孩子的右子树中插入
   
   RL（先右后左）：右孩子的左子树中插入
   
   无论RR,还是LR，每次转都是先转那个最小不平衡的子树，你不要从根上转，那样一下就错了

哈夫曼树

1. 概念：
   结点的带权路径长度：从树的根到该节点经过的路径长度*该节点的权值
   树的带权路径长度（WPL）：所有叶子结点的带权路径长度之和
   哈夫曼树（最优二叉树）：含n结点的所有二叉树中，带权路径长度（WPL）最短的那个称为哈夫曼树
2. 构造哈夫曼树的步骤、
   找权小的兄弟，组团体，从小到大，新组成的团体也要加入下一轮的组团体

3. 哈夫曼树可能和归并一起考察
   对于k叉归并，若初始归并段数量无法构成严格k叉树，则需要补充几个长度为0的虚段，再进行k叉哈夫曼树的构造。
   问还要补充多少个虚段？
   若（初始段数-1）%（k-1）==0，则不需要添加；否则，补充（k-1）-u 个虚段

   1. 由哈夫曼树得到哈夫曼编码
      向左走是0，向右走为1
      此时wpl为二进制编码的长度
      利用哈夫曼树可以设计出长度最短的二进制编码
      编码不会出现一个编码是另一个编码的前缀