Chapter 6Tree Type data; public:BinTreeNode( ) LChild= RChild=NULL; BinTreeNode(const Type LChild= lchild; RChild= rchild ; ;template class BinaryTree / 二叉树类 protected:BinTreeNode *root;void PreOrderHelp( BinTreeNode *r,void (*Visit)(const Type void InOrderHelp( BinTreeNode *r,void (*Visit)(const Type void PostOrderHelp( BinTreeNode *r, void (*Visit)(const Type 先、中、后序遍历 （辅助函数）public:BinaryTree( );/ 建立以r为根的二叉树BinaryTree(BinTreeNode *r);virtual BinaryTree();/ 析构函数BinTreeNode *GetRoot( ) const;bool Empty() const;void InOrder(void (*Visit)(const Type / 二叉树的中序遍历void PreOrder(void (*Visit)(const Type / 二叉树的前序遍历void PostOrder(void (*Visit)(const Type / 二叉树的后序遍历void void LevelOrderLevelOrder(void(void (* (*Visit)(constVisit)(const Type Type/ 二叉树的层次遍历void void InsertLeftChildInsertLeftChild(BinTreeNode(BinTreeNode*cur, const Type *cur, const Type / 插入左孩子void void InsertRightChildInsertRightChild(BinTreeNode(BinTreeNode*cur, const Type *cur, const Type / 插入右孩子; ;二叉树前序遍历递归算法二叉树前序遍历递归算法template void BinaryTree:PreOrderHelp( BinTreeNode *r,void (*Visit)(const Type / 访问根结点PreOrderHelp(r-leftChild, Visit);PreOrderHelp(r-rightChild, Visit);template void BinaryTree:PreOrder(void (*Visit)(Type template void write (const Type BinTreeNode *p =root;do while ( p != NULL ) cout void BinaryTree:InOrder( ) BinTreeNode *p=root; Stack * s;do while ( p != NULL ) Push ( s, p ); p = pLChild; if ( !Empty ( s ) ) p = pop ( s ); cout void BinaryTree:InsertRightChild(BinTreeNode *cur, const Type if (cur-rightChild != NULL)child-rightChild = cur-rightChild; cur-rightChild = child;/ e成为cur的右孩子template void BinaryTree:InsertLeftChild(BinTreeNode *cur, const Type if (cur-leftChild != NULL) / cur的左孩子非空,原有左子树成为e的左子树child-leftChild = cur-leftChild;/ cur cur-leftChild = child; / e成为cur的左孩子 int main(void) BinTreeNode *cur;int c; cur = new BinTreeNode(2); BinaryTree bt(cur);/ 建立二叉树 c = 3; bt.InsertLeftChild(cur, c);/ 插入左孩子 cur = bt.LeftChild(cur); c = 4; bt.InsertRightChild(cur, c);/ 插入右孩子 cur = bt.GetRoot();/ 取出根结点 c = 6; bt.InsertRightChild(cur, c);/ 插入右孩子 return 0; 6.6 树和森林一、树的存储表示 ABCDEFG0 A -1 1 B 0 2 C 0 3 D 0 4 E 2 5 F 2 6 G 5data father父 亲 表 示 法孩子表示法0 A 1 B 2 C 3 D 4 E 5 F 6 G data child1 2 34 56ABCDEFG改进：父亲、孩子表示法结合0 A 1 B 2 C 3 D 4 E 5 F 6 G data1 2 34 56-1 0 0 0 2 2 5ABCDEFGdata firstChildnextSibling孩子兄弟表示法A BCE DFGroot练习ABCDEFG树 的 遍 历深度优先遍历树的先根次序遍历树的后根次序遍历广度优先遍历树的层次次序遍历AB C DE F GHI J K先根遍历 A B E F C D G H I J K后根遍历 E F B C I J K H G D A层次遍历： A B C D E F G H I J KB C DE F GHI J K1森林中第一棵 树的根结点2森林中第一棵 树的子树森林3森林中其它树 构成的森林森林由三部分构成森林的先根遍历若森林F为空, 返回否则:访问F的第一棵树的根结点先根次序遍历第一棵树的子树森林先根次序遍历其它树组成的森林结果：B E F C D G H I J KBHIFCDEGJK森林的后根遍历若森林F为空，返回否则:后根次序遍历第一棵树的子树森林访问F的第一棵树的根结点后根次序遍历其它树组成的森林结果：E F B C I J K H G DBHIFCDEGJK森林的层次遍历若森林F为空，返回否则:依次遍历各棵树的根结点依次遍历各棵树根结点的所有子女依次遍历这些子女结点的子女结点结果：B C D E F G H I J K BHIFCDEGJK森林与二叉树的相互转换森林与二叉树的相互转换6.7 哈 夫 曼 树(Huffman Tree) 与 哈 夫 曼 编 码结点的路径长度从根结点到该结点的路径上分 支的数目树的路径长度树中每个结点的路径长度之和树的带权路径长度 (Weighted Path Length,WPL)树的各叶子结点所带的权值与该结点到根的路径长度的乘积的和结点的带权路径长度从该结点到到根结点之间的路径长度与结点上权的乘积。在所有含n个叶子结点、并带有各自权值的m叉树中，必存在一棵其带权路径长度取最小值的树，称为“最优树”,或“哈夫曼树” (Huffman Tree)(Huffman Tree) 哈夫曼树中，权值大的结点离根最近具有不同带权路径长度的二叉树2 27 75 54 49 9WPL(a)= 72+52+23+43+92=60WPL(b)= 74+94+53+42+21=89 7 9 7 9 2 25 54 4根据给定的 n 个权值 w1, w2, , wn，造 n 棵二叉树的集合F = T1, T2, , Tn，其中每棵二叉树中均只含一个带权值为 wi 的根结点，其左、右子树为 空树；(1)(1)构造哈夫曼树构造哈夫曼树在 F 中选取其根结点的权值为最小的两棵二叉树，分别作为左、 右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和；(2)(2)从F中删去这两棵树，同时加入刚生成的新树重复 (2)(2) 和 (3)(3) 两步，直至 F 中只含一棵树为止(3)(3)(4)(4)哈夫曼树的构造过程9 9练习：已知权值练习：已知权值 W= 5, 6, 2, 9, 7 W= 5, 6, 2, 9, 7 5 56 62 27 79 92 25 57 716166 67 713132929哈夫曼编码 哈夫曼树的应用很广，哈夫曼编码就是其在电讯 通信中的应用之一。在电讯通信业务中，通常用二进 制编码来表示字母或其他字符，并用这样的编码来表 示字符序列。 例：如果需传送的电文为 ABACCDA，它只用到 四种字符，用两位二进制编码便可分辨。假设 A, B, C, D 的编码分别为 00, 01, 10, 11，则上述电文便为 00010010101100（共 14 位），译码员按两位进行分组译码，便可恢复原来的电文。 能否使编码总长度更短呢？ 实际应用中各字符的出现频度不相同 数据的最小冗余编码问题数据的最小冗余编码问题 用短短（长）编码表示频率大大（小）的字符 使得编码序列的总长度最小，使所需总空间量最少 若假设 A, B, C, D 的编码分别为 0，00，1，01，则 电文 ABACCDA 便为 000011010（共 9 位）。可译为 BBCCDA、ABACCDA、AAAACCACA 存在多义性要求任一字符的编码都不能是另一字符编码的前缀 ！ 这种编码称为前缀编码前缀编码（其实是非前缀码）。 译码的惟一性问题 利用最优二叉树可以很好地解决上述两个问题 在编码过程要考虑两个问题 数据的最小冗余编码问题 译码的惟一性问题 以电文中的字符作为叶子结点构造二叉树。然后将二叉树中 结点引向其左孩子的分支标 0，引向其右孩子的分支标 1； 每 个字符的编码即为从根到每个叶子的路径上得到的 0, 1 序列。如 此得到的即为二进制前缀编码。 如如 此此得到的即为二进制前缀编码。得到的即为二进制前缀编码。 用二叉树设计二进制前缀编码 例： ABCD0 1 0 1 0 1 编码： A：0 B：10 C：110 D：111 ? ? 任意一个叶子 结点都不可能 在其它叶子结 点的路径中。 假设各个字符在电文中出现的次数次数（或频率）为 wi ， 其编码长度编码长度为 li，电文中只有 n 种字符，编码总长编码总长为： 叶子结点的权 从根到叶子的路径长度 设计电文总长最短的编码 设计哈夫曼树（以 n 种 字符出现的频率作权） 用哈夫曼树设计总长最短的二进制前缀编码 由哈夫曼树得到的二进制前缀编码称为哈夫曼编码 解： A CBD0 0 0 1 1 1 编码： A：0 C：10 B：110 D：111 例：如果需传送的电文为