遍历非递归算法

1、遍历非递归算法1第1页，共116页，2022年，5月20日，19点55分，星期三2递归函数的主要优点是可以把算法写的比使用非递归函数时更清晰更简洁，而且某些问题，特别是与人工智能有关的问题，更适宜用递归方法。递归的另一个优点是，递归函数不会受到怀疑，较非递归函数而言，某些人更相信递归函数。第2页，共116页，2022年，5月20日，19点55分，星期三3以先序遍历为例：void PreOrder (BiTree T) if (T) coutdata ;PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchild); ABCDEFHG第3页，共116页

2、，2022年，5月20日，19点55分，星期三4ABCDEFHGBDGNULLDNULLGCEFHFHNULLGNULLNULLNULLNULLHENULLNULL第4页，共116页，2022年，5月20日，19点55分，星期三5遍历二叉树的非递归算法需用到栈，顺序栈的定义如下：#define size 100 typedef struct Type data size ; int top ； SqStack ；第5页，共116页，2022年，5月20日，19点55分，星期三61.先序非递归遍历：(1) 初始化一个堆栈(2) 把根结点入栈(3) 当堆栈非空时，循环: A. 出栈取一个结点指针，

3、访问该结点; B. 若该 结点右子树非空，右子树指针入栈(4) 左端到尽头后,若该 栈非空，右子树出栈 第6页，共116页，2022年，5月20日，19点55分，星期三7先序遍历的非递归算法Status InorderTraverse(BiTree T )/ 采用二叉链表存储结构. 先序遍历二叉树T的非递归算法 。 InitStack(S); p=T; while(p|!StackEmpty(S) while(p)/访问当前结点，右子进栈，遍历左子树 coutdata ; if(p-rchild!=null) Push(S，p-rchild); p=p-lchild; if(StackEmpt

4、y(S)=0)/根指针退栈，遍历右子树 Pop(S，p); 第7页，共116页，2022年，5月20日，19点55分，星期三8步骤指针P栈Stack内容访问结点值初态A1BCA2DGB3D4G5CFG6E C7F E8F9FACBFEDGwhile(p)/访问当前结点，右子进栈，遍历左子树 cout data ; if(p-rchild!=null) Push(S，p-rchild); p=p-lchild; if(StackEmpty(S)=0)/根指针退栈，遍历右子树 Pop(S，p);第8页，共116页，2022年，5月20日，19点55分，星期三92.中序非递归遍历：在遍历左子树之前，

5、先把根结点入栈，当左子树遍历结束后，从栈中弹出，访问，再遍历右子树第9页，共116页，2022年，5月20日，19点55分，星期三10void InOrder(BiTree T)/ 采用二叉链表存储结构。先序遍历二叉树T的非递归算法。 InitStack(S);Push(S，T); /根指针进栈 while(p | !StackEmpty(S) while( p!=NULL ) Push(S，p); /向左走到尽头 p=p-lchild ; if(!StackEmpty(S) Pop(S，p); coutdata ; /访问结点 p=p-rchild); /向右一步 中序遍历的非递归算法1第1

6、0页，共116页，2022年，5月20日，19点55分，星期三11步骤指针P栈Stack内容访问结点值初态A1ABA2BDBA3DDBA4DBA5DGBAD6GGBA7GBA8GBAG9BA10BAB11A12ACA13CEC14EECACBFEDG while( p!=NULL ) Push(S，p); /向左走到尽头 p=p-lchild ; if(!StackEmpty(S) Pop(S，p); coutdata ; /访问结点 p=p-rchild); /向右一步 第11页，共116页，2022年，5月20日，19点55分，星期三1215EC16ECE17C18CFC19FF20F21

7、FF22ACBFEDG第12页，共116页，2022年，5月20日，19点55分，星期三13中序遍历的非递归算法2(算法) 自学Status InorderTraverse(BiTree T，Status(*visit(TElemType e)/ 采用二叉链表存储结构，Visit是对数据元素操作的应用函数。先序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit。 InitStack(S); p=T; while (p|!StackEmpty(S) if ( p ) /根指针进栈，遍历左子树 Push(S，p); p=p-lchild; else /访问结点，根指针退栈，遍历右子树 Po

8、p(S，p); visit(p-data); p=p-rchild; 第13页，共116页，2022年，5月20日，19点55分，星期三14步骤指针P栈Stack内容访问结点值初态A1BA2DBA3DBA4GBAD5GBA6BAG7AB8CA9EC10EC11CE12FC13F14FACBFEDGif(p) /根指针进栈，遍历左子树 Push(S，p); p=p-lchild; else /访问结点，根指针退栈，遍历右子树 Pop(S，p); visit(p-data); p=p-rchild; 第14页，共116页，2022年，5月20日，19点55分，星期三153.后序非递归遍历(自学)与

9、前序遍历和中序遍历二叉树的算法不同，在后续遍历二叉树的过程中，对一个结点访问之前，要两次经历这个结点。第一次是由该结点找到其左孩子结点，遍历其左子树，遍历完左子树后，返回到这个结点。第二次是由该结点找到其右孩子结点，遍历其右子树，遍历完右子树后，再次返回到结点，这时才能访问该结点。因此，用非递归方法后续遍历二叉树时，也需要设置一个栈结构，用来保存指向所经历结点的指针。第15页，共116页，2022年，5月20日，19点55分，星期三16从上面的分析可知，在后续遍历二叉树时，一个指针要进出栈两次，第一次出栈的目的是由该指针找到其左孩子结点，对该结点并不做任何处理，因此出栈后需再次进栈，只有在他第

10、二次出栈后，才能访问该结点。为了区别同一个结点两次出栈，设置一个标志flag，令： 1 第一次出栈，结点不能访问flag= 2 第二次出栈，结点可以访问第16页，共116页，2022年，5月20日，19点55分，星期三17PostOrder( BiTree t )SqStack sMAX;BiTree p;int sign;if( t=NULL ) retrun ;top=-1;p=t;while( !(p=NULL & top = -1)if ( p!=NULL ) s+top.link=p; stop.flag=1; p=p-lchild;第17页，共116页，2022年，5月20日，19

11、点55分，星期三18else p=stop.link; sign=stop-.flag; if (sign=1) s+top.link=p; stop.flag=2; p=p-rchild; else printf(“%c”,p-data ); p=NULL; 第18页，共116页，2022年，5月20日，19点55分，星期三19第19页，共116页，2022年，5月20日，19点55分，星期三204.按层次遍历二叉树实现方法为从上层到下层，每层中从左侧到右侧依次访问每个结点。下面我们将给出一棵二叉树及其按层次顺序访问其中每个结点的遍历序列。 ACBFEDG按层次遍历该二叉树的序列为：A B

12、C D E F G H第20页，共116页，2022年，5月20日，19点55分，星期三21二叉树用顺序存储结构表示时，按层遍历的算法实现：ACBFEDGABCDEFG012345671234567ACBFDGABCD#FG012345671234675第21页，共116页，2022年，5月20日，19点55分，星期三22void LevelOreder(SqBiTree BT)for(i=1;i=n;i+) if(BT.elemi!=#) cout BT.elemi);ABCDEFGHIJK第22页，共116页，2022年，5月20日，19点55分，星期三23二叉树用链式存储结构表示时，按层

13、遍历的算法实现访问过程描述如下：(1)访问根结点，并将该结点记录下来；(2)若记录的所有结点都已处理完毕，则结束遍历操作；否则重复下列操作。(3)取出记录中第一个还没有访问孩子的结点，若它有左孩子，则访问左孩子，并将记录下来；若它有右孩子，则访问右孩子，并记录下来。在这个算法中，应使用一个队列结构完成这项操作。所谓记录访问结点就是入队操作；而取出记录的结点就是出队操作。第23页，共116页，2022年，5月20日，19点55分，星期三24这样一来， 算法就可以描述成下列形式： (1)访问根结点，并将根结点入队；(2)当队列不空时，重复下列操作：a.从队列退出一个结点；b.若其有左孩子，则访问左

14、孩子，并将其左孩子入队；c.若其有右孩子，则访问右孩子，并将其右孩子入队；第24页，共116页，2022年，5月20日，19点55分，星期三25ABCDEFGHIJK初始化A第一次while循环BC第二次while循环CDE第三次while循环DEFG第四次while循环EFG第四次while循环FGHI 第25页，共116页，2022年，5月20日，19点55分，星期三26void LevelOrder(BiTree T) if ( T ) exit(0) ; InitQueue(Q); p=T; /初始化 coutdata ; EnQueue(Q，p);/访问根结点，并将根结点入队 whi

15、le(!QueueEmpty(Q)/当队非空时重复执行下列操作 DeQueue(Q，p); /出队 if(p-Lchild) /处理左孩子 coutLchild ; EnQueue(Q，p-Lchild); if(p-Rchild) /处理右孩子 coutRchild ; EnQueue(Q，p-Rchild); 第26页，共116页，2022年，5月20日，19点55分，星期三27总结：遍历的第一个和最后一个结点第一个结点：先序：根结点；中序：后序：最后一个结点：先序：中序：后序：根结点。沿着左链走，找到一个没有左孩子的结点；从根结点出发，沿着右链走，找到一个没有右孩子的结点；从根结点出发，

16、沿着右链走，找到一个没有右孩子的结点；沿着左链走，找到一个没有左孩子的结点；第27页，共116页，2022年，5月20日，19点55分，星期三28求中序的第一个结点从根结点出发，沿着左链走，找到一个没有左孩子的结点；的算法：求中序的第一个结点的算法： P=T; while(P-lchild) P=P-lchild; cout data ;第28页，共116页，2022年，5月20日，19点55分，星期三29求中序的最后一个结点的算法：从根结点出发，沿着右链走，找到一个没有右孩子的结点；求中序的最后一个结点的算法：P=T；while(P-rchild) P=P-rchild;coutdata ;

17、第29页，共116页，2022年，5月20日，19点55分，星期三30一个程序员的生活第30页，共116页，2022年，5月20日，19点55分，星期三31第31页，共116页，2022年，5月20日，19点55分，星期三32利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针(这种附加的指针称为“线索(Thread)”)。这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。不同的遍历有不同的线索树。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。6.4 线索二叉树第32页，

18、共116页，2022年，5月20日，19点55分，星期三33ABCDEFGHINULLNULL中序线索二叉树第33页，共116页，2022年，5月20日，19点55分，星期三34结点的结构：左标志ltag=右标志rtag=0：lchild是指向结点的左孩子的指针0：rchild是指向结点的右孩子的指针1：lchild是指向结点的前驱的左线索1：rchild是指向结点的后继的右线索lchildltagdatartagrchild第34页，共116页，2022年，5月20日，19点55分，星期三35若结点有左孩子，则lchild指示其左孩子，否则lchild中存储该结点的前驱结点的指针；若结点有右

19、孩子，则rchild指示其右孩子，否则rchild中存储指向该结点的后继结点的指针实质：对一个非线性结构进行线性化操作，使每个结点(除第一和最后一个外)在这些线性序列中有且仅有一个直接前驱和直接后继。第35页，共116页，2022年，5月20日，19点55分，星期三36DBEAFHGIC0A00B00C11E11F01D10G01I11H1NULLNULL中序线索链表ROOT第36页，共116页，2022年，5月20日，19点55分，星期三37注意：图中的实线表示指针，虚线表示线索。结点D的左线索为空，表示D是中序序列的开始结点，无前趋；结点C的右线索为空，表示C是中序序列的终端结点，无后继。

20、线索二叉树中，一个结点是叶结点的充要条件为：左、右标志均是1第37页，共116页，2022年，5月20日，19点55分，星期三38ABCDEFGHINULLNULL中序线索二叉树提问：中序线索二叉树是物理结构还是逻辑结构？第38页，共116页，2022年，5月20日，19点55分，星期三39不带表头结点的先序穿线(线索)链表0A01B00E11D11F1NULL第39页，共116页，2022年，5月20日，19点55分，星期三40不带表头结点的后序穿线(线索)链表0A01B00E11D11F1NULL非空二叉链表第40页，共116页，2022年，5月20日，19点55分，星期三41带表头结点的

21、中序穿线(线索)链表0A01B00E11D11F101ROOT01ROOT(a)空二叉链表(b)非空二叉链表第41页，共116页，2022年，5月20日，19点55分，星期三42从遍历的第一个结点来看：先序序列中第一个结点必为根结点，中、后序序列中第一个结点的左孩子定为空从遍历的最后一个结点来看：先、中序序列中最后一个结点的右孩子必为空，后序序列中最后一个结点一定为根结点线索二叉树的作用：对于遍历操作，线索树优于非线索树；遍历线索树不用设栈步骤：1)找遍历的第一个结点2)不断地找遍历到的结点的后继结点，直到树中各结点都遍历到为止，结束。遍历线索二叉树第42页，共116页，2022年，5月20日

22、，19点55分，星期三43遍历中序线索二叉树(带头结点)P134算法6.5Status InorderTraverse_Thr(BiThrTree T，Status(*Visit)(TElemType e)/T指向头结点，头结点的左链lchild指向根结点，可参见线索化算法，中序遍历二叉线索树T的非递归算法 p=T-lchild;/p指向根结点while(p!=T)/空树或遍历结束时，p=T while (p-LTag=Link) p=p-lchild; if(!visit(p-data) return ERROR； /访问其左子树为空的结点 while (p-rchild!=T &p-RTa

23、g=Thread) p=p-rchild; Visit(p-data)/访问后继结点 p=p-rchild; return OK;/InOrderTraverse_Thr第43页，共116页，2022年，5月20日，19点55分，星期三44BDECFHIKGJLA(1)while (p-LTag=Link) p=p-lchild;(2)if(!visit(p-data) return ERROR；/访问其左子树为空的结点 (3)while(p-rchild!=T&p-RTag=Thread) /访问后继结点 p=p-rchild; Visit(p-data); (4)p=p-rchild;NU

24、LLNULLpp1p2p3p4p5p6p7p8p9p10p11p12p13p14p15第44页，共116页，2022年，5月20日，19点55分，星期三45BDECFHIKGJLA(1)while (p-LTag=Link) p=p-lchild;(2)if(!visit(p-data) return ERROR；/访问其左子树为空的结点 (3)while(p-rchild!=T&p-RTag=Thread) /访问后继结点 p=p-rchild; Visit(p-data); (4)p=p-rchild;NULLNULLP怎样移动p第45页，共116页，2022年，5月20日，19点55分，

25、星期三46if (currentRTag =Thread) 后继为 currentrchildelse /currentRTag =Link 后继为中序遍历其右子树时访问的第一个结点(即其右子树最左下的结点) 寻找当前结点*current在中序下的后继ABDECFHIKGJL中序后继线索二叉树DBGJEACHLKFI第46页，共116页，2022年，5月20日，19点55分，星期三47if (currentLTag =Thread)前驱为currentlchild else /currentLTag =Link 前驱为中序遍历其左子树时最后访问的一个结点(即其左子树最右下的结点) 寻找当前结点

26、在中序下的前驱ABDECFHIKGJL中序前驱线索二叉树中序序列：DBGJEACHLKFI第47页，共116页，2022年，5月20日，19点55分，星期三48if(currentRTag =Thread) 后继为 currentrchildelse /currentRTag=Link后继为其左孩子，若无左孩子，则后继为其右孩子 寻找当前结点*current在先序下的后继先序线索二叉树先序序列ABDEGJCFHKLIABDECFHIKGJL第48页，共116页，2022年，5月20日，19点55分，星期三49if (currentLTag =Thread)前驱为currentlchild el

27、se /currentLTag=Link 前驱为： 若为根结点，则无前驱； 若结点无左兄弟，则其前驱为其父结点 若结点有左兄弟。则其前驱为先序遍历其左兄弟子树时访问的最后一个结点 寻找当前结点在先序下的前驱先序线索二叉树先序序列ABDEGJCFHKLIABDECFHIKGJL第49页，共116页，2022年，5月20日，19点55分，星期三50if(currentRTag =Thread) 后继为currentrchildelse/currentRTag =Link 后继为：若为根结点，则无后继； 若结点无右兄弟，则其后继为其父结点 若结点有右兄弟。则其后继为后序遍历其右兄弟子树时访问的第一个

28、结点 寻找当前结点*current在后序下的后继后序线索二叉树后序序列： DJGEBLKHIFCAABDECFHIKGJL第50页，共116页，2022年，5月20日，19点55分，星期三51if(currentLTag =Thread)前驱为currentlchild else/currentLTag =Link前驱为其右孩子，若无右孩子，则前驱为其左孩子 寻找当前结点在后序下的前驱后序线索二叉树后序序列： DJGEBLKHIFCAABDECFHIKGJL第51页，共116页，2022年，5月20日，19点55分，星期三第52页，共116页，2022年，5月20日，19点55分，星期三536

29、.4.2.森林与二叉树的转换将一棵树转换成二叉树的方法：树 二叉树将一棵树转换成二叉树实际上就是将这棵树用孩子兄弟表示法存储即可，此时，树中的每个结点最多有两个指针：一个指针指向第一个孩子，另一个指针指向右侧第一个兄弟。当你将这两个指针看作是二叉树中的左孩子指针和孩子右指针时，就是一棵二叉树了。特点：一棵树转换成二叉树后，根结点没有右孩子。 将森林转换成二叉树的方法与一棵树转换成二叉树的方法类似，只是把森林中所有树的根结点看作兄弟关系，并对其中的每棵树依依地进行转换。森林 二叉树 第53页，共116页，2022年，5月20日，19点55分，星期三54森林与二叉树的对应关系(a)三棵树的森林：

30、T1 T2 T3ACDEFGBIKHJ(b)树的二叉树表示(c)森林的二叉树表示ABCEDFGHIKJABCEDFGHIKJ第54页，共116页，2022年，5月20日，19点55分，星期三55树转化成二叉树的简单方法依据：树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟。按照这种关系很自然地就能将树转换成相应的二叉树转换步骤：在同胞兄弟之间加连线；保留结点与第一个孩子之间的连线，去掉其余连线；顺时针旋转45度。以根结点为轴；左孩子不再旋转。第55页，共116页，2022年，5月20日，19点55分，星期三56树转换为二叉树的示例ACDIBFEJHGACDIBFEJHGACDIBF

31、EJHG第56页，共116页，2022年，5月20日，19点55分，星期三57(2)森林转化成二叉树a.将森林中的每棵树转换成对应的二叉树；b.将森林中已经转换成的二叉树的各个根视为兄弟，各兄弟之间自第一棵树根到最后一棵树根之间加连线；c.以第一棵树的根为轴，顺时针旋转45度。森林二叉树第57页，共116页，2022年，5月20日，19点55分，星期三58森林转换成二叉树的定义：如果F=T1，T2，Tm是森林，则可按如下规则转换成一棵二叉树B=root，LB，RB。(1)若F为空，即m=0，则对应的二叉树B为空二叉树。(2)若F不空，则对应二叉树B的根root(B)是F中第一棵树T1的根roo

32、t(T1)；其左子树为B(T11，T12，T1m)，其中，T11，T12，T1m是root(T1)的子树；其右子树为B(T2，T3，Tn)，其中，T2，T3，Tn是除T1外其它树构成的森林。第58页，共116页，2022年，5月20日，19点55分，星期三59森林转换为二叉树acdbefgihacdbefgihacdbefgihacdbefgih第59页，共116页，2022年，5月20日，19点55分，星期三602. 二叉树转换为森林如果B=root，LB，RB是一棵二叉树，则可按如下规则转换成森林F=T1，T2，Tm 。(1)如果B为空，则对应的森林F也为空。(2)如果B非空，则F中第一棵

33、树T1的根为root；T1的根的子树森林T11，T12，T1m 是由root 的左子树LB转换而来，F中除了T1之外，其余的树组成的森林T2，T3，Tn是由root的右子树RB转换而成的森林。二叉树 森林第60页，共116页，2022年，5月20日，19点55分，星期三61课堂作业：ACDIBFEJHGacdbefgihBCDEFGIHJKLM1.将下面这棵树转换成二叉树。2.将下面的森林转换成二叉树。3.下面这棵二叉树还原。第61页，共116页，2022年，5月20日，19点55分，星期三62树和森林的遍历一、树的遍历(先根遍历、后根遍历、层次遍历)1.先根遍历：(1)先访问树的根结点 (2

34、)然后依次先根遍历根的每棵子树2.后根遍历：(1)先依次后根遍历每棵子树(2)然后访问根结点树的先根遍历 转换后的二叉树的先序遍历树的后根遍历 转换后的二叉树的中序遍历第62页，共116页，2022年，5月20日，19点55分，星期三63ABCDEFGIHJKLM先根遍历:A BEF CGKL DHIJM后根遍历:EFB KLGC HIMJD A ABCDEFGIHJKLM先根遍历:A BEF CGKL DHIJM中根遍历:EFB KLGC HIMJD A后根遍历:FEB LKG MJIHDC A 第63页，共116页，2022年，5月20日，19点55分，星期三641.先根次序遍历的规则：(

35、1)若森林F为空， 返回；(2)否则a.访问F的第一棵树的根结点；b.先根次序遍历第一棵树的子树森林；c.先根次序遍历其它树组成的森林。二、森林的遍历ABEF CGKL DHIJMDIHJMABCDEFGIHJKLM第64页，共116页，2022年，5月20日，19点55分，星期三65ABCDEFGIHJKLM先根遍历:A BEF CGKL DHIJM中根遍历:EFB KLGC HIMJD A后根遍历:FEB LKG MJIHDC A A森林对应的二叉树：第65页，共116页，2022年，5月20日，19点55分，星期三662.中根次序遍历的规则：(1)若森林F为空，返回；(2)否则a.中根次

36、序遍历第一棵树的子树森林；b. 访问F的第一棵树的根结点；c.中根次序序遍历其它树组成的森林。EFBA KLGC HIMJDDIHJMABCDEFGIHJKLM第66页，共116页，2022年，5月20日，19点55分，星期三67BCDEFGIHJKLM先根遍历:A BEF CGKL DHIJM中根遍历:EFB KLGC A HIMJD后根遍历:FEB LKG MJIHDC AA森林对应的二叉树：ABCDEFGIHJKLM第67页，共116页，2022年，5月20日，19点55分，星期三683.后根次序遍历的规则:(1)若森林F为空，返回；(2)否则a. 后根次序遍历第一棵树的子树森林；b.

37、后根次序遍历其它树组成的森林；c. 访问F的第一棵树的根结点。EFB KLGHIMJDC AABCDEFGIHJKLM第68页，共116页，2022年，5月20日，19点55分，星期三69ABCDEFGIHJKLM先根遍历:A BEF CGKL DHIJM中根遍历:EFB KLGC HIMJD A后根遍历:FEB LKG MJIHDC A 森林对应的二叉树：第69页，共116页，2022年，5月20日，19点55分，星期三70(4) 广度优先遍历(层次序遍历) ：(1)若森林F为空，返回；(2)否则a.依次遍历各棵树的根结点；b.依次遍历各棵树根结点的所有孩子；c.依次遍历这些孩子结点的孩子结

38、点。ABCDEFGIHJKLMACD BGHIJ EFKLM第70页，共116页，2022年，5月20日，19点55分，星期三71ABCDEFGIHJKLM层次遍历: A B EC FGD KH LI J M森林对应的二叉树：第71页，共116页，2022年，5月20日，19点55分，星期三726.6 赫夫曼树 (Huffman Tree)及其应用p144最优二叉树(哈夫曼树)从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。 路径长度 (Path Length)两个结点之间的路径长度是连接两结点的路径上的分支数。树的路径长度是各结点到根结点的路径长度之和。第72页，共116页，2

39、022年，5月20日，19点55分，星期三73具有不同路径长度的二叉树(a)的路径长度：1+1+2+2+2+2+3=13(b)的路径长度：1+1+2+2+2+3+3=14在结点数目相同的二叉树中，完全二叉树的路径长度最短。1234567812348567第73页，共116页，2022年，5月20日，19点55分，星期三74带权路径长度 ( Weighted Path Length， WPL )结点的权：在一些应用中，赋予树中结点的一个有某种意义的实数。树的带权路径长度是树的各叶结点所带的权值与该结点到根的路径长度的乘积的和。具有不同带权路径长度的二叉树(a)WPL=36(b)WPL=46(c)

40、WPL=35777555222444第74页，共116页，2022年，5月20日，19点55分，星期三75赫夫曼(Huffman)树设有n个权值w1，w2，wn，构造一棵有n个叶子结点的二叉树，第i个叶子的权值为wi，则WPL最小的二叉树叫最优二叉树(哈夫曼树)，即带权路径长度最短的树。记作：n其中：权值结点到根的路径长度第75页，共116页，2022年，5月20日，19点55分，星期三76说明叶子上的权值均相同时，完全二叉树一定是最优二叉树，否则完全二叉树不一定是最优二叉树。最优二叉树中，权越大的叶子离根越近。最优二叉树的形态不唯一，WPL最小第76页，共116页，2022年，5月20日，1

41、9点55分，星期三77判定树在很多问题的处理过程中，需要进行大量的条件判断，这些判断结构的设计直接影响着程序的执行效率。例如，编制一个程序，将百分制转换成五个等级输出。大家可能认为这个程序很简单，并且很快就可以用下列形式编写出来：if(socre60) printf(“E”);else if(socre70) printf(“D”); else if(score80) printf(“C”); else if(score90) printf(“B”); esle printf(“A”);在实际应用中，往往各个分数段的分布并不是均匀的。下面就是在一次考试中某门课程的各分数段的分布情况： 第77页

42、，共116页，2022年，5月20日，19点55分，星期三78等级分数段比例ABCDE059606970798089901000.050.150.400.300.10a60a90a80a70EYNDYNCYNBYNABACDE例：比较次数=5*1+15*2+40*3+30*4+10*4=285假设输入100个数第78页，共116页，2022年，5月20日，19点55分，星期三79a80a70a60a90EYNDYNCYNBYNA比较220次CBAED第79页，共116页，2022年，5月20日，19点55分，星期三80a80a70a60a90EYNDYNCYNBYNAif(socre80) i

43、f(score70) if(score60) printf(“E”); else printf(“D”); else printf(“C”);else if(socre=m【例】设待压缩的数据文件共有100个字符，这些字符均取自字符集C=a，b，c，d，e，f，g，h，等长编码需要三位二进制数字来表示六个字符，因此，整个文件的编码长度为300位。第95页，共116页，2022年，5月20日，19点55分，星期三96C =a，b，c，d，e，f，g，h则字符串efgbacd可译为对方接受时，可按三位一分进行译码，即 e f g b a c d100，101，110，001，000，010，011

44、 a000b001c010d011e100f101g110h111第96页，共116页，2022年，5月20日，19点55分，星期三97当然，在进行电文传送时，希望电文总长尽可能短，即传送时间尽可能短。如果对每个字符设计长度不等的编码，且让电文中出现次数较多的字符采用尽可能短的编码，则传送长度便可减少。(2)变长编码方案变长编码方案将频度高的字符编码设置短，将频度低的字符编码设置较长。【例】设待压缩的数据文件共有100个字符，这些字符均取自字符集C=a，b，c，d，e，f，其中每个字符在文件中出现的次数(简称频度)如下：第97页，共116页，2022年，5月20日，19点55分，星期三98-字

45、符a b c d e f频度 45 13 12 16 9 5定长编码000001010 011100 101变长编码0 101 100 111 1101 1100-1X45+3X13+3X12+3X16+4X9+4X5=224第98页，共116页，2022年，5月20日，19点55分，星期三99注意：变长编码可能使解码(译码)产生二义性。产生该问题的原因是某些字符的编码可能与其他字符的编码开始部分(称为前缀)相同。【例】设E、T、W分别编码为01、00、0001，则解码时无法确定信息串0001是ET还是W。第99页，共116页，2022年，5月20日，19点55分，星期三100(3)前缀码方案

46、对字符集进行编码时，要求字符集中任一字符的编码都不是其它字符的编码的前缀，这种编码称为前缀(编)码。利用哈夫曼树很容易求出给定字符集及其概率(或频度)分布的最优前缀码。具体做法：(1)用字符ci作为叶子，pi做为叶子ci的权，构造一棵哈夫曼树，并将树中左分支和右分支分别标记为0和1；(2)将从根到叶子的路径上的标号依次相连，作为该叶子所表示字符的编码。该编码即为最优前缀码(也称哈夫曼编码)。第100页，共116页，2022年，5月20日，19点55分，星期三101假设有一个电文字符集中有8个字符a，b，c，d，e，f，g，h，每个字符的使用频率分别为0.05，0.29，0.07，0.08，0.

47、14，0.23，0.03，0.11，现以此为例设计哈夫曼编码。哈夫曼编码设计过程为：(1)为方便计算，将所有字符的频度乘以100，使其转换成整型数值集合，得到5，29，7，8，14，23，3，11；(2)以此集合中的数值作为叶子结点的权值构造一棵哈夫曼树，如图所示；(3)由此哈夫曼树生成哈夫曼编码，如图所示。第101页，共116页，2022年，5月20日，19点55分，星期三102字符字符的使用频率编码abcdefgh0.050.290.070.080.140.230.030.1101111011101111110000110010achefg8b52971114233/p>

48、00000100111011011101111011001118010111111第102页，共116页，2022年，5月20日，19点55分，星期三103比如，发送一段编码：接收方可以准确地通过译码得到：ffgebh(00，00，0110，110，10，010)。 最后得出每个字符的编码为：a0111，b10，c1110，d1111，e110， f00，g0110，h010第103页，共116页，2022年，5月20日，19点55分，星期三104假设一串待译码的字符串总长为100电文总长为：5*4+29*2+7*4+8*4+14*3+23*2+3*4+11*3=字符字符的使用频率编码abcd

49、efgh0.050.290.070.080.140.230.030.1101111011101111110000110010路径长度权值电文总长=对应的Huffman树的带权路径长度第104页，共116页，2022年，5月20日，19点55分，星期三105eg.设给出一段报文：CASTCASTSATATATASA字符集合是C，A，S，T，各个字符出现的频度(次数)是2，7，4，5。若给每个字符以等长编码A:00，T:10，C:01，S:11则总编码长度为：(2+7+4+5)*2=36.若按各个字符出现的概率不同而给予不等长编码，可望减少总编码长度。因各字符出现的概率为2/18，7/18，4/1

50、8，5/18，化整为 2，7，4，5，以它们为各叶结点上的权值，建立赫夫曼树。第105页，共116页，2022年，5月20日，19点55分，星期三106左分支赋0，右分支赋1，得赫夫曼编码(变长编码)。A:0，T:10，C:110，S:111，它的总编码长度：7*1+5*2+(2+4)*3=35，比等长编码的情形要短。总编码长度正好等于赫夫曼树的带权路径长度WPL。赫夫曼编码是一种无前缀的编码。解码时不会混淆。赫夫曼编码树181164247ATCS010110111111第106页，共116页，2022年，5月20日，19点55分，星期三107思想方法(自学)给定字符集的哈夫曼树生成后，求哈夫

51、曼编码的具体实现过程是：依次以叶子Ti(0in-1)为出发点，向上回溯至根为止。上溯时走左分支则生成代码0，走右分支则生成代码1。注意： 由于生成的编码与要求的编码反序，将生成的代码先从后往前依次存放在一个临时向量中，并设一个指针start指示编码在该向量中的起始位置(start初始时指示向量的结束位置)。 当某字符编码完成时，从临时向量的start处将编码复制到该字符相应的位串bits中即可。 因为字符集大小为n，故变长编码的长度不会超过n，加上一个结束符0，bits的大小应为n+1。第107页，共116页，2022年，5月20日，19点55分，星期三108typedef struct un

52、signed int weight;unsigned int parent，lchild，rchild; HTNode， *HuffmanTree;/动态分配数组存储Huffman树typedef char *HuffmanCode;/动态分配数组存储Huffman树Huffman树和Huffman编码的存储表示：第108页，共116页，2022年，5月20日，19点55分，星期三109建立赫夫曼树及求赫夫曼编码的算法(p147算法6.12)第109页，共116页，2022年，5月20日，19点55分，星期三110void HuffmanCoding(HuffmanTree &HT，HuffmanCode &HC，int *w，int n)/w存放n个字符的权值(均0)，构造Huffman树HT，并求出n个字符的Huffman编码HC。 HuffmanTree p; char *cd; int i，s1，s2，start; unsigned int c，f; if(n=1) return;/n为字符数目，m为结点数目 int m=2*n-1; HT=(HuffmanTree)mall