二叉树、树、森林的相互转换

树转二叉树

步骤:

1. 加线：所有兄弟节点之间加线
2. 擦线：树中的每个节点，只保留其最左边的子节点的连线
3. 旋转：使其结构分明
   

二叉树转树

步骤：

1. 连线：若节点存在左子节点，将其左子节点的右子节点、右子节点的右子节点……（左的所有右）都作为该节点的子节点，并用线连接起来
2. 擦线：擦掉原二叉树中所有节点与其右子节点的连线
3. 旋转：使其结构分明
   

森林转二叉树

步骤：

1. 先把每个数分别转换成二叉树
2. 连线：以第一棵二叉树为起始，依次将之后的每个二叉树的根节点作为前一棵树的右子节点，连接起来（根接右）
   

二叉树转森林

步骤：

1. 擦线：从根节点开始查看，若存在右子节点，则将其连线删除。再查看删除后的二叉树，若存在右子节点，则将其连线删除……依次往下（从上到下只删右）
2. 将分离后的每个二叉树转换成树
   

以上出现的几个图，均是转载！ID：祥哥的说
仅作为个人笔记使用
转自：link

二叉树的三种遍历方法

1. 先序遍历：根左右
2. 中序遍历：左根右（Java中的TreeSet以此遍历来排序）
3. 后序遍历：左右根

二叉树的几种基本形态

满二叉树

定义：一棵二叉树的结点要么是叶子结点，要么它有两个子结点
如果一个二叉树的层数为K，且结点总数是(2^k) -1，则它就是满二叉树

完全二叉树

定义：若一个二叉树的深度为k，处第k层外，其他所有层的节点都满了，切第k层的所有节点都连续集中在最左边，称这样的二叉树为完全二叉树

最优二叉树（哈夫曼树）

定义：树的带权路径长度达到最小，称这样的二叉树为最优二叉树

哈夫曼数的构建：
例题：用2，6，4，5，3构建一棵哈夫曼数

思路：

1. 用最小的两个数及其二者之和构建一颗二叉树
   （2，6，4，5，3）—>2+3=5
   
2. ①将2、3从这一列数中去掉，将2，3的和（5）加入这组数
   ②从这列数中挑出最小的两个数构建一颗二叉树
   （5，6，4，5）—>4+5=9
   
3. 重复以上操作
   （9，6，5）—>5+6=11
   （11，9）—>9+11=20
   
   这样一颗哈夫曼树就构建好了

怎么计算哈夫曼树的带权路径长度（WPL）？
（权值大的在上层，权值小的在下层）
权值=叶子节点的值 * 叶子节点的高度（根节点为0）
上图的带权路径长度为：（2+3）*3+（4+5+6）*2=45