第六章树状结构

第六章树状结构第1页，共139页，2023年，2月20日，星期三26.1树的类型定义6.2二叉树的类型定义6.3

二叉树的存储结构6.4二叉树的遍历6.5线索二叉树6.6树和森林的表示方法6.7树和森林的遍历6.8哈夫曼树与哈夫曼编码第2页，共139页，2023年，2月20日，星期三36.1树的类型定义第3页，共139页，2023年，2月20日，星期三4数据对象D：D是具有相同特性的数据元素的集合。

若D为空集，则称为空树。否则:(1)在D中存在唯一的称为根的数据元素root；

(2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm，其中每一个子集本身又是一棵符合本定义的树，称为根root的子树。

数据关系R：第4页，共139页，2023年，2月20日，星期三5

基本操作：查找类

插入类删除类第5页，共139页，2023年，2月20日，星期三6

Root(T)//求树的根结点

查找类：Value(T,cur_e)//求cur_e结点的元素值

Parent(T,cur_e)//求cur_e结点的双亲结点LeftChild(T,cur_e)//求cur_e结点的最左孩子RightSibling(T,cur_e)//求cur_e结点的右兄弟TreeEmpty(T)//判定树是否为空树TreeDepth(T)//求树的深度TraverseTree(T,Visit())//遍历第6页，共139页，2023年，2月20日，星期三7InitTree(&T)//初始化置空树

插入类：CreateTree(&T,definition)//按定义构造树Assign(T,&cur_e,value)//给cur_e结点赋值InsertChild(&T,&p,i,c)//插入c为T中P所指结点的第i棵子树第7页，共139页，2023年，2月20日，星期三8

ClearTree(&T)//将树清空

删除类：DestroyTree(&T)//销毁树的结构DeleteChild(&T,&p,i)//删除结点p的第i棵子树第8页，共139页，2023年，2月20日，星期三9ABCDEFGHIJMKLA(B(E,F(K,L)),

C(G),

D(H,I,J(M))

)T1T3T2树根例如:树的图示表示法树的广义表表示法第9页，共139页，2023年，2月20日，星期三10ABDCJIHMEFGKL树的嵌套集合表示法第10页，共139页，2023年，2月20日，星期三11(１)有确定的根；(２)树根和子树根之间为有向关系。有向树：有序树：子树之间存在确定的次序关系。无序树：子树之间不存在确定的次序关系。第11页，共139页，2023年，2月20日，星期三12基本术语第12页，共139页，2023年，2月20日，星期三13结点:结点的度:树的度:叶子结点:分支结点:数据元素+若干指向子树的分支分支的个数（子树的个数）树中所有结点的度的最大值度为零的结点度大于零的结点包含根结点和中间结点DHIJM第13页，共139页，2023年，2月20日，星期三14(从根到结点的)路径：孩子结点、双亲结点兄弟结点、堂兄弟祖先结点、子孙结点结点的层次:树的深度：

由从根到该结点所经分支和结点构成ABCDEFGHIJMKL假设根结点的层次为1，根的孩子为第2层，如果某结点在第L层,则其子树的根在L+1层。树中叶子结点所在的最大层次第14页，共139页，2023年，2月20日，星期三15任何一棵非空树是一个二元组

Tree=（root，F）其中：root被称为根结点

F被称为子树森林森林：是m（m≥0）棵互不相交的树的集合ArootBCDEFGHIJMKLF第15页，共139页，2023年，2月20日，星期三16对比树型结构和线性结构的结构特点第16页，共139页，2023年，2月20日，星期三17~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~线性结构

树型结构

（非线性结构）第一个数据元素

(无前驱)

根结点

(无前驱)最后一个数据元素

(无后继)多个叶子结点

(无后继)其它数据元素(一个前驱、一个后继)其它数据元素(一个前驱、

多个后继)第17页，共139页，2023年，2月20日，星期三18赵老根赵跃进赵小康赵改革赵开放赵抗美赵援朝赵卫兵赵永红第18页，共139页，2023年，2月20日，星期三196.2

二叉树的类型定义第19页，共139页，2023年，2月20日，星期三20

二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。(二叉树的度最大为2)ABCDEFGHK根结点左子树右子树第20页，共139页，2023年，2月20日，星期三21二叉树的五种基本形态：N空树只含根结点NNNLRR右子树为空树L左子树为空树左右子树均不为空树第21页，共139页，2023年，2月20日，星期三22

二叉树的主要基本操作：查找类插入类删除类第22页，共139页，2023年，2月20日，星期三23

Root(T);Value(T,e);Parent(T,e);LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);BiTreeEmpty(T);BiTreeDepth(T);

PreOrderTraverse(T,Visit());InOrderTraverse(T,Visit());PostOrderTraverse(T,Visit());LevelOrderTraverse(T,Visit());第23页，共139页，2023年，2月20日，星期三24

InitBiTree(&T);Assign(T,&e,value);CreateBiTree(&T,definition);InsertChild(T,p,LR,c);第24页，共139页，2023年，2月20日，星期三25ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T,p,LR);第25页，共139页，2023年，2月20日，星期三26二叉树

的重要特性第26页，共139页，2023年，2月20日，星期三27性质1：二叉树第i层上至多有2i-1个结点。(i≥1)用归纳法证明：

归纳基：归纳假设：归纳证明：i=1层时，只有一个根结点：

2i-1=20=1；假设当j=i-1时,命题成立；即j层最多有2j-1（2i-2）个节点二叉树上每个结点至多有两棵子树，则第i层的结点数=2i-22=2i-1。第27页，共139页，2023年，2月20日，星期三28性质2：

深度为k的二叉树上至多含2k-1个结点（k≥1）。证明：

基于上一条性质，深度为k的二叉树上的结点数至多为

20+21+

+2k-1=2k-1

。（等比数列求和）第28页，共139页，2023年，2月20日，星期三29

性质3：

对任何一棵二叉树，若它含有n0个叶子结点（0度节点）、n2个度为2的结点，则必存在关系式：n0=n2+1。证明：二叉树上结点总数n=n0+n1+n2又二叉树上分支总数b=n1+2n2

而b=n-1=n0+n1+n2-1由此，n0=n2+1。第29页，共139页，2023年，2月20日，星期三30两类特殊的二叉树：满二叉树：指的是深度为k且含有2k-1个结点的二叉树。完全二叉树：树中所含的n个结点和满二叉树中编号为1至n的结点一一对应。（编号的规则为，由上到下，从左到右。）123456789101112131415abcdefghij特点

1.叶子结点出现在最后2层

2.对于任意结点，若其右分支下的子孙的最大层次为L,

则左分支下的子孙的最大层次为L或L+1第30页，共139页，2023年，2月20日，星期三31

性质4：具有n个结点的完全二叉树的深度为

log2n+1(k≥1）证明：设完全二叉树的深度为k则根据第二条性质得2k-1-1<

n≤2k-1

即k-1≤

log2n<

k

k是整数，因此，k=log2n+1第31页，共139页，2023年，2月20日，星期三32性质5：若对含n个结点的完全二叉树从上到下且从左至右进行1

至n

的编号，则对完全二叉树中任意一个编号为i

的结点：

(1)若i=1，则该结点是二叉树的根，无双亲，否则，编号为i/2的结点为其双亲结点；

(2)若2i＞n，则序号为i的结点无左孩子；

否则，编号为2i的结点为其左孩子结点；

(3)若2i+1＞n，则该序号为i的结点无右孩子；

否则，编号为2i+1的结点为其右孩子结点。第32页，共139页，2023年，2月20日，星期三深度为k的完全二叉树至少有

个结点，至多有

个结点，k和n之间关系为

。设高度为h的二叉树只有度为偶数的结点，则至少有

个结点，至多有

个结点。一棵有124个叶子结点的完全二叉树，最多有

个结点。完全二叉树的某结点若无左孩子，则必为叶子结点？具有n个结点的满二叉树叶子结点有

。2k-12k-1log2n+1

2h-12h-1248(n+1)/2第33页，共139页，2023年，2月20日，星期三346.3二叉树的存储结构二、二叉树的链式存储表示一、二叉树的顺序存储表示第34页，共139页，2023年，2月20日，星期三35#defineMAX_TREE_SIZE100//二叉树的最大结点数typedefunsignedcharTElemType;typedefTElemTypeSqBiTree[MAX_TREE_SIZE+1];SqBiTreebt;一、二叉树的顺序存储表示第35页，共139页，2023年，2月20日，星期三36例如:ABCDEF

ABD0C0E000000F12345678910111213142511437一般树按完全二叉的方式存储非常浪费空间！深度为K的单支树，需要2k个空间

第36页，共139页，2023年，2月20日，星期三37二、二叉树的链式存储表示1.二叉链表2．三叉链表第37页，共139页，2023年，2月20日，星期三38ADEBCFrootlchilddatarchild结点结构:1.二叉链表第38页，共139页，2023年，2月20日，星期三39typedefcharTElemType;typedefstructNode{//结点结构

TElemTypedata;structNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;lchilddatarchild结点结构:C语言的类型描述如下:第39页，共139页，2023年，2月20日，星期三40ADEBCFroot2．三叉链表parent

lchilddatarchild结点结构:第40页，共139页，2023年，2月20日，星期三41

typedefstructNode{//结点结构

structNode*parent;//双亲指针

TElemTypedata;structNode*lchild,*rchild;//左右孩子指针

}TriTreeNode,*TriTree;parentlchilddatarchild结点结构:C语言的类型描述如下:第41页，共139页，2023年，2月20日，星期三426.4二叉树的遍历第42页，共139页，2023年，2月20日，星期三43一、问题的提出二、先左后右的遍历算法三、算法的递归描述四、遍历算法的非递归描述第43页，共139页，2023年，2月20日，星期三44

顺着某一条搜索路径寻访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。（将树线性化）一、问题的提出（寻找某个结点）“访问”的含义可以很广，如：输出结点的信息或判定结点满足某些条件等。第44页，共139页，2023年，2月20日，星期三45

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

每个结点有两个后继，则存在如何遍历即按什么样的搜索路径遍历的问题。第45页，共139页，2023年，2月20日，星期三46对“二叉树”而言，可以有三条搜索方法：1．先上后下的按层次遍历；2．先左（子树）后右（子树）的遍历；3．先右（子树）后左（子树）的遍历。第46页，共139页，2023年，2月20日，星期三47二、先左后右的遍历算法先（根）序的遍历算法中（根）序的遍历算法后（根）序的遍历算法第47页，共139页，2023年，2月20日，星期三48例：将如下表达式

a+b*(c-d)-e/f存入一个树结构。叶子结点为操作数中间结点为运算符f/e-dc-ab*+第48页，共139页，2023年，2月20日，星期三49

若二叉树为空树，则空操作；否则，（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。先（根）序的遍历算法：顺序：-+a*b-cd/ef正好是前缀表达式第49页，共139页，2023年，2月20日，星期三50

若二叉树为空树，则空操作；否则，（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。中（根）序的遍历算法：顺序：a+b*c-d-e/f正好是中缀表达式第50页，共139页，2023年，2月20日，星期三51

若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。后（根）序的遍历算法：顺序：abcd-*+ef/-正好是后缀表达式第51页，共139页，2023年，2月20日，星期三52三、算法的递归描述voidPreOrder(BiTreeT,void(*Visit)(TElemType)){if(T){

visit(T->data);//访问根结点

PreOrder(T->lchild,visit);//遍历左子树

PreOrder(T->rchild,visit);//遍历右子树

}}ADBT第52页，共139页，2023年，2月20日，星期三53voidInOrder(BiTreeT,void(*Visit)(TElemType)){//中序遍历二叉树

if(T){

InOrder(T->lchild,visit);//遍历左子树

visit(T->data);//访问根结点

InOrder(T->rchild,visit);//遍历右子树

}}第53页，共139页，2023年，2月20日，星期三54voidPostOrder(BiTreeT,void(*Visit)(TElemType)){//后序遍历二叉树

if(T){

PostOrder(T->lchild,visit);//遍历左子树

PostOrder(T->rchild,visit);//遍历右子树

visit(T->data);//访问根结点

}}第54页，共139页，2023年，2月20日，星期三55

可以这样理解：无论先序、中序、后序遍历二叉树，遍历时的搜索路线是相同的：从根结点出发，逆时针沿二叉树外缘移动对每个结点均途经三次。先序遍历：第一次经过结点时访问。中序遍历：第二次经过结点时访问。后序遍历：第三次经过结点时访问。ABΦΦΦ123第55页，共139页，2023年，2月20日，星期三56四、先序遍历算法的非递归描述1.初始化设置一个栈；

2.根结点指针入栈；

3.堆栈非空时：（1）出栈取得结点指针，visit该结点（2）若该结点右子树不空，右子树指针进栈；（3）若该结点左子树不空，左子树指针进栈；第56页，共139页，2023年，2月20日，星期三57voidpre_s(BiTreet){SqStacks;BiTreep;Init_Sq(s);if(t){push(s,t);while(!StackEmpty(s)){pop(s,p);printf("%d",p->data);if(p->rchild)push(s,p->rchild);if(p->lchild)push(s,p->lchild);}}}第57页，共139页，2023年，2月20日，星期三58五、中序遍历算法的非递归描述voidGoFarLeft(BiTreebt,BiTree&p){if(bt){p=bt;while(p->lchild){push(s,p);p=p->lchild;}}//得到树T最左结点的指针}第58页，共139页，2023年，2月20日，星期三59voidin_s(BiTreet){BiTreep=t;Init_Sq(s);GoFarLeft(t,p);//找到最左的结点

while(p){printf("%d",p->data);if(p->rchild)GoFarLeft(p->rchild,p);elseif(!StackEmpty(s))//栈不空时退栈

pop(s,p);else p=NULL;//栈空表明遍历结束

}//while}第59页，共139页，2023年，2月20日，星期三60遍历算法的应用举例1、建立二叉树的存储结构3、求二叉树的深度(后序遍历)2、统计二叉树中叶子结点的个数

第60页，共139页，2023年，2月20日，星期三611、建立二叉树的存储结构不同的定义方法相应有不同的存储结构的建立算法第61页，共139页，2023年，2月20日，星期三62

以字符串的形式根左子树右子树定义一棵二叉树例如:ABCD以字符“#”表示A(B(#,C(#,#)),D(#,#))空树只含一个根结点的二叉树A以字符串“A##”表示以下列字符串表示第62页，共139页，2023年，2月20日，星期三63voidCreateBiTree(BiTree&bt){/*以扩展的先序序列输入数据*/charch;scanf("%c",&ch);if(ch=='#')bt=NULL;else{bt=(BiTree)malloc(sizeof(BiTNode));if(!bt)exit(1);bt->data=ch;CreateBiTree(bt->lchild);CreateBiTree(bt->rchild);}}第63页，共139页，2023年，2月20日，星期三64AB

C

D

ABCD上页算法执行过程举例如下：ATBCD^^^^^第64页，共139页，2023年，2月20日，星期三652、统计二叉树中叶子结点的个数算法基本思想:遍历二叉树，在遍历过程中查找叶子结点，并计数。由此，需在遍历算法中增添一个“计数”的参数，并将算法中“访问结点”的操作改为：若是叶子，则计数器增1。第65页，共139页，2023年，2月20日，星期三663、求二叉树的深度(后序遍历)算法基本思想:

从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度的最大值，然后加1。

首先分析二叉树的深度和它的左、右子树深度之间的关系。第66页，共139页，2023年，2月20日，星期三67intdepthval,depthLeft,depthRight;intDepth(BiTreeT){//返回二叉树的深度,T为树根的指针

if(!T)depthval=0;else{depthLeft=Depth(T->lchild);depthRight=Depth(T->rchild);depthval=1+(depthLeft>depthRight?depthLeft:depthRight);}returndepthval;}第67页，共139页，2023年，2月20日，星期三68例1.已知树的先序次序为abdcegf

中序次序为bdaegcf则树为？abdcfeg例2.已知树的后序次序为dbgefca

中序次序为bdaegcf则树为？我们可以利用先序次序和中序次序、后序次序和中序次序来确定一棵二叉树。第68页，共139页，2023年，2月20日，星期三696.5

线索二叉树何谓线索二叉树？线索链表的遍历算法如何建立线索链表？第69页，共139页，2023年，2月20日，星期三70一、何谓线索二叉树？遍历二叉树的结果是，求得结点的一个线性序列。ABCDEFGHK例如:先序序列:

ABCDEFGHK中序序列:

BDCAHGKFE后序序列:

DCBHKGFEA第70页，共139页，2023年，2月20日，星期三71指向该线性序列中的“前驱”和“后继”的指针，称作“线索”与其相应的二叉树，称作“线索二叉树”包含“线索”的存储结构，称作“线索链表”ABCDEFGHK^D^

C^^B

E^第71页，共139页，2023年，2月20日，星期三72例求如下二叉树的先序线索树、中序线索树和后序线索树。ABCDABCDABCDABCD先序线索树中序线索树后序线索树abcdbcadcbdaNULLNULLNULLNULLNULL第72页，共139页，2023年，2月20日，星期三73如何保存这种在遍历过程中得到的信息？最简单的方法是在每个结点上增加二个指针域：fwd和bkwd用来指示此结点在遍历中的前驱和后继结点。这样，使结点的存储密度大大降低。我们知道在n个结点的二叉树中，有n+1个空链域。（空链域的个数=结点数*2–分支个数）

n结点二叉树的空链域=2*n-(n-1)=n+1我们可以利用这n+1个空链域来存储线索。第73页，共139页，2023年，2月20日，星期三74对线索链表中结点的约定：

在二叉链表的结点中增加两个标志域，并作如下规定：若该结点的左子树不空，则Lchild域的指针指向其左子树，且左标志域的值为“Link（指针）”；否则，Lchild域的指针指向其“前驱”，且左标志的值为“Thread（线索）”

。第74页，共139页，2023年，2月20日，星期三75若该结点的右子树不空，则rchild域的指针指向其右子树，且右标志域的值为“Link（指针）”；否则，rchild域的指针指向其“后继”，且右标志的值为“Thread（线索）”。

如此定义的二叉树的存储结构称作“线索链表”。第75页，共139页，2023年，2月20日，星期三76typedefstruct

BiThrNod{

TElemTypedata;

structBiThrNode*lchild,*rchild;//左右指针

PointerThrLTag,RTag;//左右标志}BiThrNode,*BiThrTree;线索链表的类型描述：

#defineLink0//指针

#defineThread

1//线索

typedef

enum{

Link,Thread

}PointerThr;

第76页，共139页，2023年，2月20日，星期三77要求：已知一个二叉树，我们要会画出它的各种线索树。ABCDEFGHK画出它的先序线索树、中序线索树、后序线索树？第77页，共139页，2023年，2月20日，星期三78ABCDEFGHK先序线索树ABCDEFGHKNULL第78页，共139页，2023年，2月20日，星期三79ABCDEFGHK后序线索树DCBHKGFEANULL第79页，共139页，2023年，2月20日，星期三80ABCDEFGHK中序线索树BDCAHGKFENULLNULL第80页，共139页，2023年，2月20日，星期三81二、线索链表的遍历算法:对于增加二个指针域的结构：for(p=

firstNode(T);p;p=Succ(p))Visit(p);由于在线索链表中添加了遍历中得到的“前驱”和“后继”的信息，从而简化了遍历的算法。第81页，共139页，2023年，2月20日，星期三82例如：（对于利用空指针域的结构）

//中序线索化链表的遍历算法

※中序遍历的第一个结点？

※在中序线索化链表中结点的后继？左子树上处于“最左”（没有左子树）的结点。若无右子树，则为后继线索所指结点；否则为对其右子树进行中序遍历时访问的第一个结点。第82页，共139页，2023年，2月20日，星期三83voidInOrderTraverse_Thr(BiThrTreeT,

Status(*Visit)(TElemType)){

p=T->lchild;//p指向根结点,T指向二叉线索树的头结点

while(p!=T){//空树或遍历结束时，p==Twhile(p->LTag==Link)p=p->lchild;//第一个结点

if(!visit(p->data))returnERROR;while(p->RTag==Thread&&p->rchild!=T)

{//访问后继结点

p=p->rchild;Visit(p->data)；

}p=p->rchild;//p进至其右子树根

}}//InOrderTraverse_Thr第83页，共139页，2023年，2月20日，星期三84

在中序遍历过程中修改结点的左、右指针域，以保存当前访问结点的“前驱”和“后继”信息。遍历过程中，附设指针pre,并始终保持指针p所指结点是当前访问的结点，pre指向p结点的前驱。三、如何建立线索链表？第84页，共139页，2023年，2月20日，星期三85//已知一棵二叉树，将其中序线索化//pre指向p的前驱,第一次值为NULLvoid

InThreading(BiThrTreep)

{

if(p){//对以p为根的非空二叉树进行线索化

InThreading(p->lchild);

//左子树线索化

if(!p->lchild)//建前驱线索

{p->LTag=Thread;p->lchild=pre;}

if(!pre->rchild)//建后继线索

{pre->RTag=Thread;pre->rchild=p;}

pre=p;//保持pre指向p的前驱

InThreading(p->rchild);//右子树线索化

}//if}//InThreading第85页，共139页，2023年，2月20日，星期三86ABCDif(A){//InThreading(A),pre=NULL

InThreading(A->lchild);

//左子树线索化

if(!A->lchild)//建前驱线索,pre=C

{A->LTag=Thread;A->lchild=pre;}

if(!pre->rchild)//建后继线索

{pre->RTag=Thread;pre->rchild=A;}

pre=A;//保持pre指向p的前驱

InThreading(A->rchild);}if(B){//InThreading(B),pre=NULL

InThreading(B->lchild);

//左子树线索化

if(!B->lchild)//建前驱线索

{B->LTag=Thread;B->lchild=pre;}

if(!pre->rchild)//建后继线索

{pre->RTag=Thread;pre->rchild=B;}

pre=B;//保持pre指向p的前驱

InThreading(B->rchild);}ABCDNULL第86页，共139页，2023年，2月20日，星期三87if(C){//InThreading(C),pre=B

InThreading(C->lchild);

//左子树线索化

if(!C->lchild)//建前驱线索

{C->LTag=Thread;C->lchild=B;}

if(!B->rchild)//建后继线索

{B->RTag=Thread;B->rchild=C;}

pre=C;//保持pre指向p的前驱

InThreading(C->rchild);}//pre=Cif(D){//InThreading(D),pre=A

InThreading(D->lchild);

//左子树线索化

if(!D->lchild)//建前驱线索

{D->LTag=Thread;D->lchild=A;}

if(!A->rchild)//建后继线索

{A->RTag=Thread;A->rchild=D;}

pre=D;//保持pre指向p的前驱

InThreading(D->rchild);}ABCDABCD第87页，共139页，2023年，2月20日，星期三88StatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT){//构建中序线索链表

if(!(Thrt=(BiThrTree)malloc(

sizeof(BiThrNode))))

exit(OVERFLOW);

Thrt->LTag=Link;Thrt->RTag=Thread;Thrt->rchild=Thrt;

//添加头结点

returnOK;`}//InOrderThreading

……第88页，共139页，2023年，2月20日，星期三89if(!T)

Thrt->lchild=Thrt;

else{Thrt->lchild=T;

pre=Thrt;InThreading(T);

pre->rchild=Thrt;//处理最后一个结点

pre->RTag=Thread;

Thrt->rchild=pre;}第89页，共139页，2023年，2月20日，星期三90

6.6树和森林的表示方法第90页，共139页，2023年，2月20日，星期三91树的三种存储结构一、双亲表示法二、孩子链表表示法三、树的二叉链表(孩子-兄弟）存储表示法第91页，共139页，2023年，2月20日，星期三92ABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

5r=0n=7dataparent一、双亲表示法:第92页，共139页，2023年，2月20日，星期三93

typedefstructPTNode{TElemTypedata;

intparent;//双亲位置域

}PTNode;

dataparent#defineMAX_TREE_SIZE100结点结构:C语言的类型描述:第93页，共139页，2023年，2月20日，星期三94typedefstruct{PTNodenodes[MAX_TREE_SIZE];

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

}PTree;树结构:第94页，共139页，2023年，2月20日，星期三95ABCDEFG0

A1

B

2

C

3

D

4

E

5

F

6

G

r=0n=7datafirstchild123456二、孩子链表表示法:-1000224第95页，共139页，2023年，2月20日，星期三96typedefstructCTNode{

intchild;//不是TElemType

structCTNode*next;

}*ChildPtr;孩子结点结构:

childnextC语言的类型描述:第96页，共139页，2023年，2月20日，星期三97

typedefstruct{TElemTypedata;intparent;ChildPtrfirstchild;//孩子链表的头指针

}CTBox;表结点结构

datafirstchildparent第97页，共139页，2023年，2月20日，星期三98typedefstruct{CTBoxnodes[MAX_TREE_SIZE];

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

}CTree;树结构:第98页，共139页，2023年，2月20日，星期三99ABCDEFGABCEDFGrootABCEDFG

三、树的二叉链表(孩子-兄弟）存储表示法第99页，共139页，2023年，2月20日，星期三100要求

将一棵树转化为二叉树

ABCDEFGHIJKLABCDEFKLGHIJ第100页，共139页，2023年，2月20日，星期三101typedefstructCSNode{TElemTypedata;

structCSNode

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

firstchilddatanextsibling第101页，共139页，2023年，2月20日，星期三102

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

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

B=(LBT,Node(root),RBT);第102页，共139页，2023年，2月20日，星期三103。。。T1T2T3T4TnT1T11T12T1m。。。T1T11T12T1m。。。T2T3Tn。。。第103页，共139页，2023年，2月20日，星期三104由森林转换成二叉树的转换规则为:若F=Φ，则B=Φ；否则，由ROOT(T1)

对应得到Node(root)；由(t11,t12,…,t1m)

对应得到LBT；由(T2,T3,…,Tn)

对应得到RBT。第104页，共139页，2023年，2月20日，星期三105由二叉树转换为森林的转换规则为：若B=Φ，则F=Φ；否则，由Node(root)

对应得到ROOT(T1

)；由LBT

对应得到(t11,t12,…，t1m)；由RBT

对应得到(T2,T3,…,Tn)。第105页，共139页，2023年，2月20日，星期三106BCDEFGHIJKLBCDEFKLGHIJ第106页，共139页，2023年，2月20日，星期三107

由此，树的各种操作均可对应二叉树的操作来完成。

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

左是孩子，右是兄弟。第107页，共139页，2023年，2月20日，星期三1086.7树和森林的遍历第108页，共139页，2023年，2月20日，星期三109一、树的遍历二、森林的遍历第109页，共139页，2023年，2月20日，星期三110树的遍历可有三条搜索路径:按层次遍历:先根(次序)遍历:后根(次序)遍历:

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

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

若树不空，则自上而下自左至右访问树中每个结点。第110页，共139页，2023年，2月20日，星期三111ABCDEFGHIJK

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

后根遍历时顶点的访问次序：EFBCIJKHGDA

层次遍历时顶点的访问次序：ABCDEFGHIJK第111页，共139页，2023年，2月20日，星期三112

BCDEFGHIJK1．森林中第一棵树的根结点；2．森林中第一棵树的子树森林；3．森林中其它树构成的森林。森林由三部分构成：第112页，共139页，2023年，2月20日，星期三1131.先序遍历森林的遍历

若森林不空，则访问森林中第一棵树的根结点；先序遍历森林中第一棵树的子树森林；先序遍历森林中(除第一棵树之外)其余树构成的森林。即：依次从左至右对森林中的每一棵树进行先根遍历。第113页，共139页，2023年，2月20日，星期三114２．中序遍历

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

余树构成的森林。即：依次从左至右对森林中的每一棵树进行后根遍历。第114页，共139页，2023年，2月20日，星期三115

树的遍历和二叉树遍历的对应关系？先根遍历后根遍历树二叉树森林先序遍历先序遍历中序遍历中序遍历第115页，共139页，2023年，2月20日，星期三1166.8哈夫曼树与

哈夫曼编码

最优树的定义

如何构造最优树

哈夫曼编码

第116页，共139页，2023年，2月20日，星期三117

一、最优树的定义树的路径长度定义为：

根结点到每个结点的路径长度之和。

结点的路径长度定义为：

从树中一结点到另一结点的路径上分支的数目。第117页，共139页，2023年，2月20日，星期三118

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

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

WPL(T)=wklk(对所有叶子结点)。

在所有含n个叶子结点、并带相同权值的m叉树中，必存在一棵其带权路径长度取最小值的树，称为“最优树”。例如：第118页，共139页，2023年，2月20日，星期三11922475499WPL(T)=72+52+23+43+92=60WPL(T)=72+91+53+24+44=6257第119页，共139页，2023年，2月20日，星期三12024579WPL(T)=92+72+52+23+43=60第120页，共139页，2023年，2月20日，星期三121

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

F={T1,T2,…,Tn}，其中每棵二叉树中均只含一个带权值为wi的根结点，其左、右子树为空树；二、如何构造最优树(1)(哈夫曼算法)以二叉树为例：第121页，共139页，2023年，2月20日，星期三122

在F中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和；(2)第122页，共139页，2023年，2月20日，星期三123

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

重复

(2)

和

(3)

两步，直至F中只含一棵树为止。(3)(4)约定：为了保证得到的哈夫曼树结构尽量唯一，约定每个结点的左子树根结点权值小于等于右子树根结点的权值。第123页，共139页，2023年，2月20日，星期三1249例如:已知权值W={5,6,2,9,7}562752769767139527第124页，共139页，2023年，2月20日，星期三1256713952795271667132900001111000111100101第125页，共139页，2023年，2月20日，星期三126哈夫曼编码假设我们发送的电文为“ABACCD”,它只有四个字符，只需要2位二进制编码

A---00B---01C---10D---11发送电文的序列为000100101011

在传送电文时，要求总长度尽量短，因此出现次数多的字符适用短的编码。

A---0B---00C---1D---11发送电文的序列为00001111(可以解释为AAAACCCC,AABDD,BBCCCC…….)我们必须使用前缀编码第126页，共139页，2023年，2月20日，星期三127前缀编码：任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。如：ABCD四个字符的使用率由高到低，编码为A---0B---10C---110D---111做法：以字符概率作为叶子结点，构造二叉树，左分支标0；右分支标1；构成编码一定是前缀编码。

利用哈夫曼树可以构造一种不等长的二进制编码，并且构造