I 树、森林与二叉树的转换

关键：树的孩子

兄弟表示法

和二叉树的

二叉链表

表示法在物理结构上是相同。

1. 树转换为二叉树

方法：

1. 树中所有相邻兄弟结点之间加一条连线。
2. 对于树中每个结点，仅保留它与第一个孩子结点之间的连线，删去与其他孩子之间的练习。
3. 调整层次。

2. 森林转换为二叉树

方法：

1. 将森林中每颗树转换为二叉树。
2. 从第二棵二叉树开始，依次把后一颗二叉树的根结点作为前一棵二叉树根节点的有孩子，当所有的二叉树连起来后，就是森林得到的二叉树。

3. 二叉树转换为树或森林

略

II 哈弗曼树

1. 概念

给定一组具有确定权值的叶子结点，构成的二叉树中带权路径长度最小的二叉树称为哈弗曼树。

2. 构造算法

略

III 平衡二叉树

1. 概念

平衡二叉树主要用于二叉排序树查找。

平衡二叉树

1. 空的二叉排序树
2. 根节点的左子树和右子树的深度最多相差1；根节点的左子树和右子树也都是平衡树。

平衡因子


结点的平衡因子是该结点的左子树的深度与右子树的深度之差。

最小不平衡树