大家好，我是讯享网，很高兴认识大家。

目录

一、相关术语：

二、树的性质

三、树的存储结构（Tested）

1、双亲表示法（顺序）

 2、孩子链表示法（顺序+链式）

3、孩子兄弟表示法(二叉树表示法)（链式存储）

一、哈夫曼树（最优二叉树）

1、性质：

2、相关术语

3、构造：

4、哈夫曼编码：

二、二叉树（binary tree）

1、定义及性质：

2、完全二叉树

3、二叉排序树

4、平衡二叉树

5、扩充二叉树（张乃孝版）

6、二叉树的遍历及重构

7、结论及常考性质：

四、线索二叉树

1、概念及构造  

2、二叉树线索化

五、树、森林

1、二叉树、森林的转化关系

2、树、森林的遍历与二叉树遍历的对应关系

六、考点

---

一、相关术语：

1、节点：一个数据元素及指向其子树的分支

2、节点的度：节点所拥有的子树的棵树（分支个数）

3、树的度：树中节点的度的最大值

4、叶子结点(终端节点)：树中度为零的节点

5、非叶子节点

6、祖先节点、子孙节点、父节点、孩子节点、兄弟节点、堂兄弟节点

7、树的深度：树中节点的最大层次值

8、有序树与无序树：看树是否需要通过左右来表示某些逻辑关系

9、森林：多个互不相交的树组成森林

10、m叉树：每个结点最多只能有m个孩子的树（并非每个结点的孩子都是m）

11、m层数：直观上的m层

【注意】张乃孝版二叉树的定义不同！！！且根节点为0

讯享网

二、树的性质

性质6：树是一种递归定义的数据结构 

性质5补充：

 ，两边同时取对数即可得到。

三、树的存储结构（Tested）

1、双亲表示法（顺序）

每个结点中保存指向双亲的指针。根节点固定存储在0，-1表示没有双亲。

 2、孩子链表示法（顺序+链式）

        树中每个结点设置多个指针域，每个指向该结点的子结点

        1）定长结点结构：指针域的数目就是树的度。设有n个节点，度为k的树，                           则必有n*k - （n-1）（总指针数 - 分支数）

3、孩子兄弟表示法(二叉树表示法)（链式存储）

优点： 可以用二叉树相关操作来处理树，例如遍历树

一、哈夫曼树（最优二叉树）

【注】张乃孝版哈夫曼树定义与王道有出入，概念不同但构造方法类似，第一大点已经按照张乃孝版做了一些更改

1、概念：

2、相关术语

• 结点的权：有某种现实含义的数值
• 结点的带权路径长度：（树的根到该结点的路径长度）*（该结点权值的乘积）
• 树的带权路径长度（WPL）：树中所有叶子结点的带权路径长度之和

3、构造：

4、哈夫曼编码：

        概念：-编码长度最短
                   -字符集中任一字符的编码都不是其它字符的编码的前缀

        ASCII编码是固定长度编码，哈夫曼编码是可变长度编码，都属于前缀编码（无歧义编码）

二者区别：

5、算法分析（部分代码，后面有需要再补充）

 

 

二、二叉树（binary tree）

1、定义及性质：

二叉树是n（n>=0）个结点的有限集合

特点：1）每个节点至多有两棵子树

           2）左右子树不能颠倒（二叉树是有序树）

形如以下亦是二叉树

2、完全二叉树

        一种特殊的满二叉树，去掉了部分编号更大的节点，其他部分要与二叉树一一对应。简单来说就是叶子结点中间不能空着且最多只有1个度为1 的结点

        二叉树的顺序存储中，一定要把二叉树的结点编号与完全二叉树对应起来，则能够按如下方式很方便的查找左右孩子及父结点的编号。

• i的左孩子：2i
• i的右孩子：2i+1
• i的父结点：i/2

特点：1）只有最后两层可能有叶子结点

           2）最多只有1个度为1 的结点（为了保证一一对应关系，比如不能去掉13同时保留14）

3、二叉排序树

3.1、概念：

1）左子树所有关键字均小于根节点的关键字

2）右子树所有关键字均大于根节点的关键字

3）左子树与右子树又分别是二叉排序树

3.2、二叉排序树的查找、插入以及删除

        查找用二分查找即可，插入总是作为叶子结点插入，也很简单。

        较为复杂的删除操作有如下几种情况：

 

 

3.3二叉排序树算法分析

        一般采用折中的办法，也就是构建平衡二叉树和红黑树

4、平衡二叉树（AVL）

4.1、相关概念及性质

树上任一结点的左子树与右子树深度之差<=1 的特殊二叉排序树

平衡因子BF：结点的左子树的深度–右子树的深度

有更高的搜索效率

4.2、最小不平衡子树及其四种调整

        指离插入结点最近，且以平衡因子绝对值大于1的结点为根的子树，将其转化为平衡二叉树时只需要改动最小不平衡子树即可。

 

 

 

 

 

5、扩充二叉树（张乃孝版）

扩充的二叉树是对一个已有二叉树的扩充,扩充后原二叉树的结点都变为度数为2的分支结点。也就是说,如果原结点的度数为2,则不变;度数为1,则增加一个分支;度数为0(树叶),则增加两个分支。

扩充后的二叉树是满二叉树

【注】张乃孝版的满二叉树中，结点的度要么为0，要么为2就行

【例】

6、二叉树的遍历及重构

6.1

先序遍历：根左右

中序遍历：左根右

后序遍历：左右根

命名方式取决于根的位置，树的深度>1时递归遍历

练习：

1）

2）一般二叉树的重构

【注】关键在于找出根节点，然后不断划分左右子树 

给出两个周游序列，画二叉树

3）满二叉树的重构

【注】给出先根序列和后根序列只有在满二叉树的重构中能实现，实现思路跟上面差不多

6.2、层序遍历

算法思想:

①初始化一个辅助队列

②根结点入队

③若队列非空，则队头结点出队，访问该结点，并将其左、右孩子插入队尾（如果有的话)

7、结论及常考性质：

1）结论：结论:若只给出一棵二叉树的前/中/后/层序遍历序列中的一种，不能唯一确定一棵二叉树。

2）考点 ：能确定一颗二叉树的情况：

        前+中序遍历序列

        后+中序遍历序列

        层+中序遍历序列

2）考点：由树的性质2得到：

四、线索二叉树

1、概念及构造  

【注】二叉树原来的的边也要加上箭头

2、二叉树线索化

先序线索化

中序线索化

后序线索化

二叉树线索化就是对先/中/后序算法的改造，当访问一个结点时，连接该结点与前驱节点的线索信息，用一个指针&pre记录当前访问结点的前驱结点

3、方法论^^

-引入线索二叉树是为了加快查找节点前驱和后继的速度；

-方便遍历

五、树、森林

1、二叉树、森林的转化关系

实际上是采用二叉链表的方式存储森林。

森林 转 二叉树步骤：

1. 将森林中的各棵树用二叉链表进行表示，方法就是孩子兄弟表示法（左孩子，右兄弟）； 
2. 各个树的根节点视为兄弟关系，连接起来。

二叉树 转 森林示例：

2、树、森林的遍历与二叉树遍历的对应关系

树的遍历：

• 先根遍历（深度优先遍历）：若树非空，先访问根结点，再依次对每棵子树进行先根遍历。
• 后根遍历（深度优先遍历）：若树非空，先依次对每棵子树进行后根遍历，最后再访问根结点。
• 层次遍历（广度优先遍历）：用队列实现，比较简单。

①若树非空，则根结点入队

②若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队

③重复②直至队列为空。

以这样一棵树为例：

先根遍历的结果是：ABEKLF  CG  DHMIJ（对应转化成二叉树后的先序遍历序列）

后根遍历的结果是：KLEFB  GC  MHIJD  A（对应中序遍历序列）

层次遍历的结果是：A  BCD  EFGHIJ  KLM

森林的遍历（递归思想）：

tip:如果考到森林遍历的算法题，最好将其转化为二叉树简化代码

• 先序遍历森林：效果等同于依次对各个树进行先根遍历，等同于对应二叉树的先序遍历
• 中序遍历森林：效果等同于依次对各个树进行后根遍历，等同于对应二叉树的中序遍历

以这样一个森林为例：

先序遍历森林：BEKLF  CG  DHMIJ

中序遍历森林：KLEFB GC MHIJD

 其转化的二叉树为——>

六、考点

1. 树与森林的转化
2. 各种遍历序列
3. 树与二叉树的转化
4. 森林与二叉树的转化
5. 二叉树性质的相关计算
6. 构建哈夫曼树
8. updating...