树和二叉树

线性结构和树型结构对比

二叉树

基本概念

二叉树的递归定义：二叉树或为空树，或是由一个根节点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。

结点的度：结点所拥有的子树的个数，二叉树的度最大为2。

叶子：度为0的结点，如D、E。

孩子：结点子树的根，如B和C就是A的孩子。

双亲：孩子结点的上层结点，如A是B的双亲。

子孙：以某结点为根的子树中的任意一个结点，D是A的子孙。

祖先：从根到该结点所经分支上的所有结点，A、C、F就是H的祖先。

结点的层次：从根结点起，根是第一层，孩子是第二层，依次类推。

兄弟：同一个双亲的孩子，如D、E就是兄弟。

堂兄弟：双亲在同一层的结点，D和F互为堂兄弟。

二叉树的深度：二叉树结点的最大层次数。

特点

1. 每个结点最多只有两棵子树，即不存在结点度大于2的结点
2. 子树有左右之分，不能颠倒

五种基本形态

1. 空树
2. 只含根结点
3. 右子树为空树
4. 左子树为空树
5. 左右子树均不为空树

两种特殊的二叉树

二叉树的性质

• 性质1：在二叉树的第i层上至多有2的i-1次方个结点；

• 性质2：深度为k的二叉树上至多含有2的k次方-1个结点；

• 性质3：叶结点与双分支结点的关系

  对于任何一棵二叉树T，设叶子结点数为n，度为2的结点数为m，则有n=m+1。

• 性质4：具有n个结点的完全二叉树的深度为logn+1

• 性质5：

存储结构

顺序存储结构

用一组地址连续的存储单元，以层序顺序存放二叉树的数据元素，结点的相对位置蕴含着结点之间的关系

完全二叉树的顺序存储：

一般二叉树的顺序存储：

把一般的二叉树先补成完全二叉树，然后按照完全二叉树的顺序存储方式进行存储，而新补上去的结点只占位置，不存放结点数据。

链式存储结构

二叉链表

三叉链表（类似于双向链表，可以反向寻址）

二叉树的遍历

常见的遍历方式：递归遍历、层次遍历、非递归遍历

先序遍历算法

若二叉树非空，则

1. 访问根结点
2. 先序遍历左子树
3. 先序遍历右子树

中序遍历算法

若二叉树非空，则

1. 中序遍历左子树
2. 访问根结点
3. 中序遍历右子树

后序遍历算法

若二叉树非空，则

1. 后序遍历左子树
2. 后序遍历右子树
3. 访问根结点

二叉树的层次遍历

二叉树的应用

先序和中序序列建立二叉树

叶子结点的统计

二叉树的深度

变形的二叉树

• 二叉排序树（BST）
• 平衡二叉树（AVL）
• 哈夫曼树及哈夫曼编码
• 堆排序

二叉排序树（BST）

左子树的元素>双亲>右子树的元素，所以中序遍历序列是一个有序序列

查找

插入

插入操作只有在查找不成功的时候才进行

删除

删除可分为三种情况：

1. 被删除的结点是叶子
2. 被删除的结点只有左子树或者只有右子树
3. 被删除的结点既有左子树又有右子树

查找性能

平衡二叉树（AVL，三个人的名字缩写）

定义

首先是一棵二叉排序树，或者是一棵空树，或者它的左右子树都是平衡二叉树并且左右子树的深度差不超过1。

构造平衡二叉树

在插入过程中，采用平衡旋转技术

失衡调整旋转平衡处理

1. 单向右旋（LL）
2. 单向左旋（RR）
3. 先左后右旋转（LR）
4. 先右后左旋转（RL）

哈夫曼树及哈夫曼编码

最优树-哈夫曼树

• 结点的路径长度：从根结点到该结点的路径上分支的数目
• 树的路径长度：树中每个结点的路径长度之和
• 树的带权路径长度：

构造最优树-哈夫曼算法

例如把13的左右子树交换之后就是一棵新的二叉树

哈夫曼编码

上图中左子树的路径设定为0，右子树路径为1，则哈夫曼树的叶子结点编码就是该结点的路径

算法实现

堆排序

堆的定义

堆排序

思想

1. 以初始关键字序列，建立堆；
2. 输出堆顶最小元素；
3. 调整余下的元素，使其称为一个新堆；
4. 重复2和3，直到n个元素输出，得到一个有序序列；

关键是要解决1和3，即如何由一个无序序列构建成一个堆？如何调整余下的元素成为一个新堆？

筛选的逻辑

1. 堆顶元素和堆底元素交换，然后把13输出；

2. 让97和左右孩子比较，跟较小的一个孩子做交换，以此类推，直到97比左右孩子小或者97变成叶子结点，停止；

调整算法实现

初始化堆

1. 获取最后一个非终端结点（位置为二分之n，向下取整，这里值为97）；
2. 反复调用筛选过程；

树和森林

树的定义

树：具有相同特性的数据元素的集合，当数据元素个数为0的时候，称为空树，否则在树中，存在一个唯一的称为根的数据元素，当数据元素超过1的时候，其余的结点可分为m个互不相交的有限集合，每个集合对应一棵树，这些集合称为树的根的子树。

树的特点：

1. 树的根结点没有双亲，其他每个结点都有且只有一个双亲；
2. 树中所有结点有0个或者多个孩子结点；

森林的定义

若干个互不相交的子树的集合

表示方法

树和森林的存储结构

树的双亲表示法

树的孩子表示法

树的双亲孩子表示法

树的孩子兄弟表示法

森林的存储结构

1. 森林的双亲表示法
2. 森林的孩子表示法
3. 森林的孩子兄弟表示法

树及森林和二叉树的相互转换

树转换成二叉树

• 加线：兄弟结点先用线连接；
• 去线（抹线）：保留双亲和最左边孩子的连线，去掉双亲和其他孩子的连线；
• 最后进行一个旋转。

二叉树转换成树

• 加线：将结点和它的左孩子结点的右孩子，即它的右子孙全部加线相连；
• 去线：去掉所有结点和右孩子结点的连线；
• 旋转处理。

森林转成二叉树

• 首先将每棵树转成二叉树；
• 每棵树的根结点相连；
• 以第一棵树的根结点作为二叉树的根，顺时针旋转。

二叉树转成森林

• 去线：将二叉树中根结点与其右孩子的连线全部去掉，使之成为孤立的二叉树；
• 对每个孤立的二叉树进行转换，变成树；

树的遍历

• 先根（序）遍历
• 后根（序）遍历
• 层次遍历

森林的遍历

• 先序遍历
• 中序遍历，其实就是后序遍历每棵树

平衡二叉树-补充（AVL）

平衡二叉树定义（ADEL'SON-VEL'SKII & LANDIS）

平衡二叉树或者是一棵空树，或者是具有下列性质的二叉排序树：

• 它的左右子树都是平衡二叉树；
• 左右子树的深度之差不超过1；