数据结构第5章 二叉树及应用.ppt

5.4.2 创建线索二叉树2 2、二叉树的线索化 * 算法5-11 基于中序遍历的二叉树线索化 26 if (p-llink==NULL) 27 { 28 p-llink = pr; 29 p-ltag = 1; 30 } 31 } 32 pr = p; 33 p = p-rlink; 34 } while ( top!=-1 || p!=NULL ); 35 pr-rlink=root; 36 pr-rtag=1; 37 return(root); 38 } 5.4.2 创建线索二叉树3 3、线索二叉树遍历 * 以下以对中序线索化链表为例讨论基于线索的二叉树中序遍历算法。此时，算法关键点有二： ① 怎样获取中序遍历的首结点？ 从根结点沿着左指针不断向左下搜寻，直到给定二叉树左子树的处于“最左下”的结点，结点是“最左下”的含义是该结点再无左子结点，亦即该结点的左指针域为空。 ② 怎样获取在中序线索化链表中当前结点的后继结点？ 如果当前结点没有无右子树，则其后继结点即为其右指针域中后继线索所指结点；如果当前结点存在右子树，则从该右子树根结点开始沿左指针行进，直到右子树“最左下”结点，此即为当前结点的后继。 5.4.2 创建线索二叉树3 3、线索二叉树遍历2 * 算法5-12基于中序线索二叉树中序遍历算法 00 void thrInOrder(ThreadTree *root ) 01 { 02 ThreadTree *p; 03 p = root-llink; 04 if (p==NULL) 05 return ; 06 while ( p-llink!=NULL p-ltag==0 ) 07 p = p-llink; /* 一直到“最左下” */ 08 while (p!=root) 09 { 10 printf(%d ,p-info); 11 if ( p-rlink!=NULL p-rtag==0 ) /* 右子树不是线索时 */ 12 { 13 p = p-rlink; 14 while (p-llink!=NULLp-ltag==0) 15 p = p-llink; /* 顺右子树的左子树一直向下 */ 16 } 17 else 18 p = p-rlink; 19 } 20 } §5.5 Huffman编码 5.5.1 等长与非等长编码 所谓编码（code），就是用一组不同的代码表示一个数据对象集合中的每个元素的过程。 1、两种基本编码类型 编码三要素： ① 唯一性：发送方传输编码字段，接收方解码后必须具有唯一性，解码结果与发送原文保持相同； ② 简洁性：发送的编码应该尽可能做到简洁短小，减少存储代价和提高传输效率。 ③ 前缀性：两个编码字节不使用特殊标记如标点符号进行分隔，一个编码字节不能是另一个编码字节的前缀，应具有“前缀性”（Prefix Property）； * 5.5.1 等长与非等长编码2 2、最优二叉树与Huffman树 二叉树路径长度：一棵二叉树的所有从根结点到每个叶结点路径长度之和称为该二叉树的“路径长度”。 叶结点的权：赋给二叉树叶结点一个具有某种意义的实数，则称此数为该叶结点的“权”。 二叉树带权路径长度：设二叉树具有n个带权的叶结点，则从根结点到各叶结点的路径长度与相应结点权值乘积之和称为该二叉树的“带权路径长度”，记为： * WPL= wk×lk （wk是第k个叶结点权值， lk是第k个叶结点路径长度） “Huffman树”：由带有权值的一组相同叶结点所构成二叉树当中，称其中带权路径长度最小的二叉树为是“最优二叉树”。 5.5.2 Huffman树构建思想 设有n个权值w1、w2、w3、…、wn，则可按照下述步骤构造Huffman树： Step 1. 构造n棵只有一个根结点的二叉树森林 HT = {T1，T2，T3，…，Tn}，它们分别以w1、w2、w3、…、wn作为权值。 Step 2. 在HT集合中，选取权值最小和次小的两个根结点作为一棵新二叉