工程09级使用数据结构第6章

返回主目录

本章说明6.1树的基本定义6.2二叉树6.3遍历二叉树和线索二叉树6.4树和森林6.6赫夫曼树及其应用

本章小结

学习目标领会树和二叉树的类型定义，理解树和二叉树的结构差别熟记二叉树的主要特性，并掌握它们的证明方法熟练掌握二叉树的各种遍历算法，并能灵活运用遍历算法实现二叉树的其它操作理解二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法熟练掌握二叉树和树的各种存储结构及其建立的算法学会编写实现树的各种操作的算法了解最优树的特性，掌握建立最优树和赫夫曼编码的方法。本章说明本章说明

重点和难点二叉树和树的遍历及其应用是本章的学习重点，而编写实现二叉树和树的各种操作的递归算法也恰是本章的难点所在。知识点树的类型定义、二叉树的类型定义、二叉树的存储表示、二叉树的遍历以及其它操作的实现、线索二叉树、树和森林的存储表示、树和森林的遍历以及其它操作的实现、最优树和赫夫曼编码学习指南本章是整个课程的第二个学习重点，也是整个课程中的一大难点。在本章的学习过程中主要应该学会如何根据二叉树和树的结构及其操作的递归定义编写递归算法。6.1树的定义和基本术语

树是一类重要的非线性数据结构，是以分支关系定义的层次结构1、树的定义定义：树(tree)是n(n>0)个结点的有限集T，其中：有且仅有一个特定的结点，称为树的根(root)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,……Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree)特点：树中至少有一个结点——根树中各子树是互不相交的集合6.1树的定义和基本术语A只有根结点的树ABCDEFGHIJKLM有子树的树根子树ADTTree

数据对象D：数据关系R：基本操作P：InitTree(&T);DestroyTree(&T);CreateTree(&T,definition);ClearTree(&T);……2、树的抽象数据类型的定义P1186.1树的定义和基本术语树形表示法：自然界倒长的树(Knuth开初用正长的树表示)文氏表示法：用嵌套集合表示(a)嵌套括号表示法：广义表表示法凹入表示法：类似书目3、树的表示方法6.1树的定义和基本术语KLEADJIMHGCBF(a)ACDBEKLFGHMIJ(c)(b)(A(B(E(K,L),F),C(G),D(H(M),I,J)))4、树的术语6.1树的定义和基本术语结点(node)——表示树中的元素，包括数据项及若干指向其子树的分支结点的度(degree)——结点拥有的子树数叶子(leaf)——度为0的结点孩子(child)——结点子树的根称为该结点的孩子双亲(parents)——孩子结点的上层结点叫该结点的~兄弟(sibling)——同一双亲的孩子树的度——一棵树中最大的结点度数结点的层次(level)——从根结点算起，根为第一层，它的孩子为第二层……堂兄——其父母为兄弟的结点互称堂兄祖先——结点的祖先是从根到该结点所经分支上的所有结点子孙——以某结点为根的子树中的任一结点都称为该结点的子孙有序树——结点的子树从左到右有顺序，否则，称为无序树深度(depth)——树中结点的最大层次数森林(forest)——m(m

0)棵互不相交的树的集合6.1树的定义和基本术语6.1树的定义和基本术语ABCDEFGHIJKLM结点A的度：3结点B的度：2结点M的度：0叶子：K，L，F，G，M，I，J结点A的孩子：B，C，D结点B的孩子：E，F结点I的双亲：D结点L的双亲：E结点B，C，D为兄弟结点K，L为兄弟树的度：3结点A的层次：1结点M的层次：4树的深度：4结点F，G为堂兄弟结点A是结点F，G的祖先6.2二叉树1、二叉树定义定义：二叉树是n(n0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成特点每个结点至多有二棵子树(即不存在度大于2的结点)二叉树的子树有左、右之分，且其次序不能任意颠倒基本形态A只有根结点的二叉树

空二叉树AB右子树为空AB左子树为空ABC左、右子树均非空证明：用归纳法证明之

i=1时，只有一个根结点，显然，2i-1=20=1

是对的假设对所有j,(1j<i)命题成立，即第j层上

至多有2j-1个结点，可证明j=i命题成立

③那么，第i-1层至多有2i-2个结点

又二叉树每个结点的度至多为2

第i层上最大结点数是第i-1层的2倍，即

2×2i-2=2i-1

故命题得证2、二叉树的性质6.2二叉树性质1：性质2：深度为k的二叉树至多有2k-1个结点(k1)6.2二叉树证明：由性质1，可得深度为k的二叉树最大结点数是性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1证明：设n1为二叉树T中度为1的结点数

因为：二叉树中所有结点的度均小于或等于2

所以：其结点总数n=n0+n1+n2

又二叉树中，除根结点外，其余结点都只有一

个分支进入，设B为分支总数，则n=B+1

又：分支由度为1和度为2的结点射出，

B=n1+2n2

于是，n=B+1=n1+2n2+1=n0+n1+n2n0=n2+1特点：每一层上的结点数都是最大结点数完全二叉树定义：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为~特点叶子结点只可能在层次最大的两层上出现对任一结点，若其右分支下子孙的最大层次为l，则其左分支下子孙的最大层次必为l或l+16.2二叉树几种特殊形式的二叉树满二叉树定义：6.2二叉树1231145891213671014151231145891267101234567123456思考：满二叉树与完全二叉树的关系？性质4：具有n个结点的完全二叉树的深度为

log2n+1

证明：设深度为k，则由性质2和完全二叉树定义

(k-1层)2k-1-1<n≤2k-1(k层）或2k-1≤n<2k

于是k-1≤log2n<k

又k是整数

k=log2n+1性质5：对于一棵完全二叉树，从上到下从左至右对结点进行编号,根结点为1,则对任一结点i(1<=i<=n)，有：若i=1,则结点是二叉树的根，无双亲，否则其双亲是

i/2如果2i>n，则结点i无左子女，否则，其左子女为2i如果2i+1>n，则结点i无右子女，否则，其右子女为2i+16.2二叉树3、二叉树的存储结构顺序的存储结构实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素特点：结点间关系蕴含在其存储位置中浪费空间，适于存满二叉树和完全二叉树abcdefgabcde0000fg12345678910116.2二叉树浪费空间二叉树的顺序存储表示

#defineMAX_TREE_SIZE100TypedefTElemTypeSqBiTree[MAX_TREE_SIZE];//

0号单元存储根结点

SqBiTreebt;缺点：按完全二叉树形式存储，浪费空间。例如，在最坏情况下，n个结点的单枝树，要占用2n-1个元素的存储空间。6.2二叉树顺序存储结构适用于满二叉树和完全二叉树的存储。链式存储结构二叉链表表示typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;lchilddatarchildABCDEFG在n个结点的二叉链表中，有n+1个空指针域ABCDEFG^^^^^^^^6.2二叉树三叉链表表示typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild,*parent;}BiTNode,*Bitree;lchilddataparentrchildABCDEFGABCDEFG^^^^^^^^^6.2二叉树6.3遍历二叉树和线索二叉树

问题的提出

先左后右的遍历算法

算法的递归描述

遍历算法的应用举例1、遍历二叉树

算法的非递归描述

顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。

问题的提出“访问”的含义可以很广，如：输出结点的信息等。6.3遍历二叉树和线索二叉树6.3遍历二叉树和线索二叉树

“遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论。而二叉树是非线性结构，

每个结点有两个后继，则存在如何遍历即按什么样的搜索路径进行遍历的问题。6.3遍历二叉树和线索二叉树

对“二叉树”而言，可以有三条搜索路径：（1）先上后下的按层次遍历；（2）先左（子树）后右（子树）的遍历；（3）先右（子树）后左（子树）的遍历。6.3遍历二叉树和线索二叉树

先左后右的遍历算法先（根）序的遍历算法中（根）序的遍历算法后（根）序的遍历算法根左子树右子树根根根根根访问根结点、遍历左子树、遍历右子树6.3遍历二叉树和线索二叉树

若二叉树为空树，则空操作；否则，（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。先（根）序的遍历算法：6.3遍历二叉树和线索二叉树

若二叉树为空树，则空操作；否则，（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。中（根）序的遍历算法：6.3遍历二叉树和线索二叉树

若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。后（根）序的遍历算法：6.3遍历二叉树和线索二叉树ABCDEFGHK例如：先序序列：中序序列：后序序列：A

BCD

EFGHKBDC

A

EHGKFDCBHKGFE

A6.3遍历二叉树和线索二叉树

算法的递归描述（6.1）6.3遍历二叉树和线索二叉树voidpreorder(BiTree*T){if(T){printf("%d\t",T->data);preorder(T->lchild);preorder(T->rchild);}}主程序Pre(T)返回返回pre(TR);返回返回pre(TR);ACBDTBprintf(B);pre(TL);BTAprintf(A);pre(TL);ATDprintf(D);pre(TL);DTCprintf(C);pre(TL);C返回T>左是空返回pre(TR);T>左是空返回T>右是空返回T>左是空返回T>右是空返回pre(TR);先序序列：ABDC6.3遍历二叉树和线索二叉树

算法的非递归描述

二叉树表示表达式

基本思想

若表达式为数或简单变量，则相应二叉树只有根结点，其数据域存放表达式信息；否则，表达式均可写成<第一操作数>（运算符）<第二操作数>形式，其中，“运算符”可用二叉树的根结点表示，“第一操作数”用二叉树的左子树表示，“第二操作数”用二叉树的右子树表示。操作数本身可以是表达式。6.3遍历二叉树和线索二叉树表达式=(操作数1)(运算符)(操作数2)运算符操作数1操作数26.3遍历二叉树和线索二叉树例如：a+b*(c-d)-e/f的二叉树表示。abcef-+*/d-先序（前缀表达式）中序（中缀表达式）后序（后缀表达式）-+a*b-cd/efa+b*c-d-e/fabcd-*+ef/-6.3遍历二叉树和线索二叉树abc-*-*cab-*abc先序遍历：-*abc6.3遍历二叉树和线索二叉树abc-*-*cab中序遍历：

a*b-ca*bc-6.3遍历二叉树和线索二叉树abc-*-*cab后序遍历：

ab*c-ab*c-6.3遍历二叉树和线索二叉树

二叉树遍历的非递归算法6.2ABCDEFGpiP->A(1)ABCDEFGpiP->AP->B(2)ABCDEFGpiP->AP->BP->C(3)p=NULLABCDEFGiP->AP->B访问：C(4)6.3遍历二叉树和线索二叉树pABCDEFGiP->A访问：CB(5)ABCDEFGiP->AP->D访问：CBp(6)ABCDEFGiP->AP->DP->E访问：CBp(7)ABCDEFGiP->AP->D访问：CBEp(8)6.3遍历二叉树和线索二叉树ABCDEFGiP->AP->DP->G访问：CBEP=NULL(9)ABCDEFGiP->A访问：CBEGDp(11)ABCDEFGiP->AP->F访问：CBEGDp(12)ABCDEFGiP->AP->D访问：CBEGp(10)6.3遍历二叉树和线索二叉树ABCDEFGiP->A访问：CBEGDFp=NULL(13)ABCDEFGi访问：CBEGDFAp(14)ABCDEFGi访问：CBEGDFAp=NULL(15)6.3遍历二叉树和线索二叉树

建立二叉树的存储结构

遍历算法的应用举例

统计二叉树中叶子结点的个数

求二叉树的深度

二叉树表示表达式6.3遍历二叉树和线索二叉树

统计二叉树中叶子结点的个数

算法基本思想:

先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。由此，需在遍历算法中增添一个“计数”的参数，并将算法中“访问结点”的操作改为:若是叶子，则计数器增1。算法实现6.3遍历二叉树和线索二叉树否则，整个二叉树中的叶子结点个数等于其左子树中的叶子结点个数和其右子树中的叶子结点个数之和。

另一种算法思想分析方法:若二叉树为空，则叶子结点的个数为零;若二叉树中只有一个(根)结点，则叶子结点的个数为1;(后序遍历)算法实现6.3遍历二叉树和线索二叉树

求二叉树的深度算法基本思想:若二叉树为空树，则深度为0;否则，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度。

首先分析二叉树的深度和它的左、右子树深度之间的关系(后序遍历)6.3遍历二叉树和线索二叉树intDepth(BiTreeT){//返回二叉树的深度

if(!T)depthval=0;else{depthLeft=Depth(T->lchild);depthRight=Depth(T->rchild);

depthval=1+(depthLeft>depthRight?depthLeft:depthRight);}returndepthval;}6.3遍历二叉树和线索二叉树也可以从另一角度去分析:

从二叉树深度的定义还可知，二叉树的深度即为其叶子结点所在层次的最大值。由此，可通过遍历求得二叉树中所有结点的“层次”，从中取其最大值。算法中需引入一个计结点层次的参数。

首先分析二叉树的深度和结点的“层次”间的关系。6.3遍历二叉树和线索二叉树voidDepth(BiTreeT,intlevel,int&dval){if(T){if(level>dval)dval=level;

Depth(T->lchild,level+1,dval);

Depth(T->rchild,level+1,dval);}}//调用之前level的初值为1。

//dval的初值为0.6.3遍历二叉树和线索二叉树

建立二叉树的存储结构

不同的定义方法相应有不同的存储结构的建立算法6.3遍历二叉树和线索二叉树

以字符串的形式“根左子树右子树”定义一棵二叉树（算法6.4）例如:A(B(,C(,)),D(,))以字符串“A”表示ABCD以空白字符“”表示空树只含一个根结点的二叉树A以下列字符串表示6.3遍历二叉树和线索二叉树void

CreateBiTree(BiTree&T)

{

scanf(&ch);if(ch=='')T=NULL;else{

T=(BiTNode*)malloc(sizeof(BiTNode));T->data=ch;//生成根结点

CreateBiTree(T->lchild);//构造左子树

CreateBiTree(T->rchild);//构造右子树

}}//CreateBiTree6.3遍历二叉树和线索二叉树AB

C

D

ABCD上页算法执行过程举例如下:ATBCD^^^^^scanf(&ch);if(ch=='')T=NULL;else{T=(BiTNode*)malloc(sizeof(BiTNode));T->data=ch;CreateBiTree(T->lchild);

CreateBiTree(T->rchild);}6.3遍历二叉树和线索二叉树

二叉树的遍历有许多重要性质，现以例子加以说明。例如：仅知二叉树的先序序列“abcdefg”不能唯一确定一棵二叉树，如果同时已知二叉树的中序序列“cbdaegf”，则会如何？二叉树的先序序列二叉树的中序序列左子树左子树右子树右子树根根abcdefgcbdaegf例如:aabbccddeeffggabcdefg^^^^^^^^先序序列中序序列6.3遍历二叉树和线索二叉树此例推论可知，二叉树遍历的重要性质：若已知二叉树的先序序列和中序序列，可唯一确定一棵二叉树；若已知二叉树的后序序列和中序序列，也可唯一确定一棵二叉树。6.3遍历二叉树和线索二叉树6.3遍历二叉树和线索二叉树2、线索二叉树

线索二叉树定义

线索二叉树的遍历

中序遍历二叉线索树的算法6.3遍历二叉树和线索二叉树

二叉树的遍历本质上是将一个复杂的非线性结构转换为线性结构，使每个结点都有了唯一前驱和后继（第一个结点无前驱，最后一个结点无后继）。对于二叉树的一个结点，查找其左、右孩子是方便的，其前驱后继只有在遍历中得到。为了容易找到前驱和后继，有两种方法：在结点结构中增加向前和向后的指针fwd和bkd，这种方法增加了存储开销

利用二叉树的空链指针。

线索二叉树定义n个结点的二叉链表有n+1个空链域证明：因除了根结点外，每个结点都有一指针射入。

n个结点便有n-1个指针，即有n-1个非空链域。因有2n个链域

空链域个数为：2n-(n-1)=n+16.3遍历二叉树和线索二叉树

为了节省存贮空间，我们可以利用这些空链域来存放结点的前趋和后继的信息。为避免混淆，需在结点中增加两个标志域：lchildltagdatartagrchild(特征位)0lchild域指示结点的左孩子ltag=1lchild域指示结点的前趋

rtag=0rchild域指示结点的右孩子

1rchild域指示结点的后继6.3遍历二叉树和线索二叉树

线索链表：以上述结点结构构成的二叉链表其中指向结点前趋和后继的指针，叫做线索

线索二叉树：加上线索的二叉树对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。例如：中序线索二叉树作业：画先序，后序线索树！6.3遍历二叉树和线索二叉树6.3遍历二叉树和线索二叉树abcef-+*/d-NILNIL中序线索二叉树6.3遍历二叉树和线索二叉树010-00+00/01a10*01e11b10-01c11d11f1thrtbt中序线索链表头结点：lt=0,lc指向根结点rt=1,rc指向遍历序列中最后一个结点遍历序列中第一个结点的lc域和最后一个结点的rc域都指向头结点

只要先找到序列中的第一个结点，依次找结点的后继直到其后继为空为止。6.3遍历二叉树和线索二叉树

线索二叉树的遍历

在中序线索树中找结点的后继：

(1)若结点的rtag为1（叶子），则其后继为线索rchild所指结点（2）（否则）若结点的rtag为0（非叶子），则其后继为“从其右孩子沿着左链找到ltag为1的那个结点”

(即右子树最左下的结点）6.3遍历二叉树和线索二叉树

在中序线索树中找结点的前驱：

(1)若结点的ltag为1（叶子），则其前驱为线索lchild所指结点（2）（否则）若结点的ltag为0（非叶子），则其前驱为“从其左孩子沿着右链找到rtag为1的那个结点”(即左子树最右下的结点）

在后序线索二叉树中查找结点的前驱和后继要知道其双亲的信息，要使用栈，所以说后序线索二叉树是不完善的。6.3遍历二叉树和线索二叉树

二叉树的二叉线索存储表示Typedefenum{Link,Thread}pointerTag;//Link==0:指针，Thread==1：线索TypedefstructBiThrNode{TElemTypedata;structBiThrNode*lchild,*rchild;PointerTagLtag,Rtag;}BiThrNode,*BiThrTree;二叉树的线索化：是在遍历的过程中，将二叉链表中的空指针改为线索中序遍历的线索化算法在二叉树的线索链表上加一个头结点，令其lchild指向二叉树的根结点，rchild指向中序遍历时访问的最后一个结点令二叉树中序序列中的第一个结点的lchild和最后一个结点的rchild均指向头结点（象双向链表，可双向遍历）设指针p指向当前访问结点，pre指向其前驱结点6.3遍历二叉树和线索二叉树

中序遍历二叉线索树的算法

中序遍历二叉线索树T的非递归算法思想：找左子树的最左叶子结点，访问访问后继结点6.3遍历二叉树和线索二叉树

学习线索化时，有三点必须注意：

何种序的线索化，是先序、中序还是后序要前驱线索化、后继线索化还是全线索化（前驱后继都要）只有空指针处才能加线索;6.4

树和森林1、树的三种存储结构

双亲表示法

孩子链表表示法

树的二叉链表(孩子-兄弟）存储表示法6.4

树和森林ABCDEFGr=0n=60

A

-11

B

02

C

03

D

04

E

25

F

26

G

5dataparent

双亲表示法双亲位置缺点：只反映了双亲位置6.4

树和森林

typedefstructPTNode{ElemTypedata;

intparent;//双亲位置域

}PTNode;

dataparent#defineMAX_TREE_SIZE100结点结构:C语言的类型描述:6.4

树和森林typedefstruct{

PTNodenodes[MAX_TREE_SIZE];

intr,n;//根结点的位置和结点个数

}PTree;树结构:6.4

树和森林r=0n=6

datafirstchildABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

4645

123

孩子链表表示法-1000224parent6.4

树和森林typedefstructCTNode{

intchild;

structCTNode*next;}*ChildPtr;孩子结点结构:

childnextchildC语言的类型描述:6.4

树和森林

typedefstruct{ElemTypedata;ChildPtrfirstchild;//孩子链的头指针

}CTBox;双亲结点结构

datafirstchild6.4

树和森林typedefstruct{CTBoxnodes[MAX_TREE_SIZE];

intn,r;//结点数和根结点的位置

}CTree;树结构:6.4

树和森林ABCDEFGrootABCEDFGABCEDFG

树的二叉链表(孩子-兄弟）存储表示法root6.4

树和森林typedefstructCSNode{ElemTypedata;

structCSNode

*firstchild,*nextsibling;}CSNode,*CSTree;C语言的类型描述:结点结构:

firstchilddatanextsibling6.4

树和森林2、森林与二叉树的转换

森林和二叉树的对应关系

森林转换成二叉树

二叉树转换成森林6.4

树和森林

森林和二叉树的对应关系设森林

F=(T1,T2,…,Tn);T1=(root，t11,t12,…,t1m);二叉树

B=(LBT,Node(root),RBT);6.4

树和森林T1T11,T12,…,T1mT2,…,TnLBTRBTroot6.4

树和森林BCADEBACDE二叉链表作为中间媒介6.4

树和森林BCADBACDFEGHIJACDBGHIJEFFEHIJG树与二叉树对应树根相连森林与二叉树对应6.4

树和森林由森林转换成二叉树的转换规则为:若F=Φ，即m=0，则B=Φ;

由ROOT(T1)

对应得到Node(root);否则，即m

0由(T2,T3,…,Tn)

对应得到RBT。RBT是由(T2,T3,…,Tn)

转换的二叉树若F={T1,T2,T3,…,Tn},则按如下规则转换二叉树B=(root,LBT,RBT)：6.4

树和森林由二叉树转换为森林的转换规则为:由LBT

对应得到(t11,t12,…，t1m);若B=Φ,则F=Φ;否则，由Node(root)

对应得到ROOT(T1

);由RBT

对应得到(T2,T3,…,Tn)。6.4

树和森林

由此，树和森林的各种操作均可与二叉树的各种操作相对应。

应当注意的是，和树对应的二叉树，其左、右子树的概念已改变为：

左是孩子，右是兄弟6.4

树和森林

树的遍历

森林的遍历3、树和森林的遍历6.4

树和森林树的遍历可有2条搜索路径:按层次遍历:先根(次序)遍历:后根(次序)遍历:

若树不空，则先访问根结点，然后依次先根遍历各棵子树。

若树不空，则先依次后根遍历各棵子树，然后访问根结点。

若树不空，则自上而下自左至右访问树中每个结点。6.4

树和森林ABCDEFGHIJK层次遍历时顶点的访问次序：

先根遍历时顶点的访问次序：ABEFCDGHIJK后根遍历时顶点的访问次序：EFBCIJKHGDAABCDEFGHIJK6.4

树和森林

层次遍历时顶点的访问次序：ABCDEFGHIJK

先根遍历时顶点的访问次序：ABEFCDGHIJK

后根遍历时顶点的访问次序：EFBCIJKHGDAABCDEFGHIJK6.4

树和森林

BCDEFGHIJK（1）森林中第一棵树的根结点；（2）森林中第一棵树的子树森林；（3）森林中其它树构成的森林。可以分解成三部分：森林6.4

树和森林

若森林不空，则访问森林中第一棵树的根结点;先序遍历森林中第一棵树的子树森林;先序遍历森林中(除第一棵树之外)其余树构成的森林。先序遍历

森林的遍历即：依次从左至右对森林中的每一棵树进行先根遍历。6.4

树和森林

中序遍历

若森林不空，则中序遍历森林中第一棵树的子树森林;访问森林中第一棵树的根结点;中序遍历森林中(除第一棵树之外)其

余树构成的森林。即：依次从左至右对森林中的每一棵树进行后根遍历。6.4

树和森林

树的遍历和二叉树遍历的对应关系？先根遍历后根遍历树二叉树森林先序遍历先序遍历中序遍历中序遍历6.6

赫夫曼树及其应用

最优二叉树（赫夫曼树）

如何构造最优二叉树

赫夫曼树应用

最优二叉树的定义树的路径长度定义为：

树中每个结点的路径长度之和。

结点的路径长度定义为：

从根结点到该结点的路径上分支的数目。6.6

赫夫曼树及其应用

树的带权路径长度定义为：

树中所有叶子结点的带权路径长度之和

WPL(T)=

wklk(对所有叶子结点)

其中：wk——权值

lk——结点到根的路径长度

在所有含n个叶子结点、并带相同权值的m叉树中，必存在一棵其带权路径长度取最小值的树，称为“最优二叉树”。例如：6.6

赫夫曼树及其应用WPL(T)=72+52+23+43+92=60WPL(T)=74+94+53+42+21=896.6赫夫曼树及其应用2475979542

根据给定的n个权值{w1,w2,…,wn}，构造n棵二叉树的集合

F={T1,T2,…,Tn}

其中每棵二叉树中均只含一个带权值为wi的根结点，其左、右子树为空树;

如何构造最优二叉树(1)(赫夫曼算法)以二叉树为例:6.6赫夫曼树及其应用

在F中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值

为其左、右子树根结点的权值之和;(2)6.6赫夫曼树及其应用

从F中删去这两棵树，同时加入刚生成的新树;

重复(2)和(3)两步，直至F中只含一棵树为止。(3)(4)6.6赫夫曼树及其应用9例如:已知权值W={5,6,2,9,7}5627527697671395276.6赫夫曼树及其应用67139527952716671329000011110001111001016.6赫夫曼树及其应用

利用赫夫曼树解决判别问题分数0-5960-6970-7980-8990-100比例树0.050.150.400.300.10A<60A<70A<80A<90不及格及格中等良好优秀NNNNYYYY6.6赫夫曼树及其应用(a)10000个输入比较31500次利用赫夫曼树构造最佳判定树6.6赫夫曼树及其应用70A<80不及格及格中等良好优秀NNYNYYY80A<90A<6060A<70N(b)仅比较22000次A<80不及格及格中等良好优秀NNYNYYYNA<70A<90A<60(c)拆分条件515403010

Huffman编码构造所得的赫夫曼编码是一种最优前缀编码，即使所传电文的总长度最短。6.6赫夫曼树及其应用

数据通信用的二进制编码思想：根据字符出现频率编码，利