【数据结构】——树、森林、哈夫曼树

目录

树的存储结构

双亲表示法

孩子链表示法

孩子兄弟表示法

树、森林与二叉树的转换

树、森林转为二叉树

二叉树转为树、森林

树和森林的遍历

哈夫曼树

树的存储结构

双亲表示法

概述：在树结构中，每个结点的双亲是唯一的。假设以一组连续空间来存储树的结点，同时为每个结点附设一个指向双亲的指针parent，就可唯一地表示一棵树。

图示：

孩子链表示法

概述：树中每个结点可能有多棵子树 (即多个孩子)，因此可以把每个结点的孩子结点看成一个线性表，并以单链表结构存储其孩子结点，n个结点就有n个孩子链表。

图示：基于上述树的转换

孩子兄弟表示法

概述：孩子兄弟表示法又称二叉链表表示法，即以二叉链表作为树的存储结构，链表中两个链指针域分别指向该结点的第一个孩子结点和下一个兄弟结点，命名为 firstchild域和 nextsibling域。

图示：基于上述树的转换

树、森林与二叉树的转换

树、森林转为二叉树

树转二叉树：首先在所有兄弟结点之间加一道连线，然后再对每个结点保留长子的连线，去掉该结点与其他孩子的连线。

图示：

森林转二叉树：先将森林中的每棵树转为二叉树，然后再将各二叉树的根结点看作是兄弟连在一起，形成一棵二叉树。

图示：

二叉树转为树、森林

转换方式：若二叉树中结点X是双亲Y的左孩子，则把X的右孩子、右孩子的右孩子，...，都与Y用连线连起来，最后去掉所有双亲到右孩子的连线，即可得到对应的树或森林。

图示：

树和森林的遍历

概述：在树中，任何一个结点都可能有两棵以上的子树，不易于讨论中根次序的遍历。为此，一般都只给出两种次序遍历树的方法，即前序遍历和后序遍历。

树的遍历：

• 前序遍历：先访问树的根结点，然后依次前序遍历根的每棵子树
• 后序遍历：先依次后序遍历根的每棵子树，然后访问根结点

前序遍历：ABECFGD 后序遍历：EBFGCDA

结论：前序遍历一棵树等价于前序遍历该树对应的二叉树，后序遍历一棵树等价于中序遍历该树对应的二叉树。

森林的遍历：

前序遍历

1. 访问森林中的第一棵树的根结点
2. 前序遍历第一棵树中的根结点的子树森林
3. 前序遍历除去第一棵树之后剩余的树构成的森林

后序遍历

1. 后序遍历森林中第一棵树的根结点的子树森林
2. 访问第一棵树的根结点
3. 后序遍历除去第一棵树之后剩余的树构成的森林

前序遍历：ABDECFGHIJKL 后序遍历：DEBCAGIHJFLK

哈夫曼树

两个结点构成的路径的分支 (边)数目称为路径长度，树根到树中每个结点的路径长度之和称之为树的路径长度。完全二叉树就是这种路径长度最短的二叉树。

将树中的结点赋上一个具有某种意义的实数，称为结点的权。从树根结点到某结点之间的路径长度与该结点上的权的乘积称为该结点的带权路径长度，树中所有叶子结点的带权路径长度之和称为树的带权路径长度，记为：

n表示叶子结点的个数、w(i)和 l(i)分别表示叶子结点k(i)的权值和根到k(i)之间的路径长度。

哈夫曼树(最优二叉树)：在权值为w1,w2,...,w(n)的n个叶结点构成的所有二叉树中，带权路径长度WPL最小的二叉树。

如图所示，图c所示树的WPL最小，所以它就是一棵哈夫曼树。

注意：若叶结点上的权值均相同，完全二叉树一定是最优二叉树，否则不一定是最优二叉树。

---