构造赫夫曼树.PPT

赫夫曼编码的实现 Huffman树中没有度为1的结点，此类树称为严格的或正则的二叉树。 一棵有n个叶子结点的赫夫曼树共有2n-1个结点，why？ 可存储在大小为2n-1的一维数组中。 数据结构设计 生成赫夫曼树之后，编码需要从叶子结点走到根，译码需要从根走到叶子结点。因此每个结点中既要存放孩子的信息，又要存放双亲的信息。 赫夫曼编码算法 赫夫曼编码算法 练习 假设用于通信的电文是由字符集{a, b, c, d, e, f, g, h}中的字符构成， 这8个字符在电文中出现的概率分别为{0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10} 。编写一段程序，设计用于通信的赫夫曼编码。 中序遍历的非递归算法实现 线索二叉树 遍历二叉树是按一定的规则将树中的结点排列成一个线性序列，即对非线性结构的线性化操作。使每个结点仅有一个直接前驱和一个直接后继。 如何保存这种前驱和后继信息呢？ 每个结点增加两个指针域fwd和bkwd. 在含有n个结点的二叉链表中有n+1个空链域。 可以利用这些空闲的指针域来存放结点的直接前驱和直接后继信息。对结点的指针域做如下规定： 若结点有左孩子，则Lchild指向其左孩子，否则，指向其直接前驱； 若结点有右孩子，则Rchild指向其右孩子，否则，指向其直接后继； 线索二叉树 为避免混淆,每个结点需要增加两个标志域 用这种结点结构构成的二叉树的存储结构叫做线索链表；指向结点前驱和后继的指针叫做线索；加上线索的二叉树称之为线索二叉树。 Lchild Ltag data Rchild Rtag 0：Lchild域指示结点的左孩子 1：Lchild域指示结点的前驱 Ltag= 0：Rchild域指示结点的右孩子 1：Rchild域指示结点的后继 Rtag= A F H I E G B D C (a) 二叉树 (b) 先序线索树的逻辑形式 结点序列：ABDCEGFHI A F H I E G B D C NIL (c) 中序线索树的逻辑形式 结点序列：DBAGECHFI A F H I E G B D C NIL NIL (d) 后序线索树的逻辑形式 结点序列：DBGEHIFCA A F H I E G B D C NIL 写出先序、中序和后序线索树的结点序列 线索二叉树的遍历 在线索树上进行遍历，先找到序列中的第一个结点，然后就可以依次找结点的直接后继结点直到后继为空为止。如何在线索树中找结点的直接后继? 中序线索树的结点序列： DBAGECHFI A F H I E G B D C NIL NIL 如果结点的右链是线索，则右链直接指示了结点的直接后继。 如果结点的右链是指针。根据中序遍历的规律，非叶子结点的直接后继是遍历其右子树时访问的第一个结点，即右子树中最左下的(叶子)结点。 如结点C的直接后继：沿右指针找到右子树的根结点F，然后沿左链往下直到Ltag=1的结点即为C的直接后继结点H。 线索二叉树的遍历 如何在线索树中找结点的直接前驱? 若结点的Ltag=1，则左链是线索，指示其直接前驱； 否则，遍历左子树时访问的最后一个结点(即沿左子树中最右往下的结点) 为其直接前驱结点。 二叉树的二叉线索存储表示 可以为二叉树的线索链表添加一个头结点，令其lchild域的指针指向二叉树的根结点，rchild域的指针指向访问的最后一个结点。并令访问的第一个节点的lchild域和最后一个结点的rchild域指向头结点。这样就建立一个双向线索链表。 线索二叉树的中序遍历算法 树和森林 前面介绍了二叉树的存储结构，本节继续介绍树的存储结构。 常见的树存储结构有三种 双亲表示法 孩子表示法 孩子兄弟表示法 双亲表示法 用一组连续的存储空间来存储树的结点，同时在每个结点中附加一个指示器(整数) 指示其双亲结点在链表中的位置。 缺点：求孩子结点的操作需要进行遍历。 孩子表示法（1） 树中每个结点有多个指针域，每个指针指向其一棵子树的根结点。有两种结点结构。 定长结点结构 指针域的数目就是树的度。 链表结构简单，但指针域的浪费明显。 不定长结点结构 树中每个结点的指针域数量是该结点的度，结点不同构，节约存储空间，但操作不便。 孩子表示法（2） 另一个办法是把每个结点的孩子排列起来，看成一个线性表，以单链表作存储结构，则n个结点有n个孩子链表(叶子的孩子链表为空)，而n个头指针又组成一个线性表，可采用顺序存储结构。 孩子表示法 孩子兄弟表示法 又称二叉树表示法或二叉链表表示法。链表中结点的两个指针域分别指向结点的第一个孩子结点和下一个兄弟结点。 树与二叉树 由于