《数据结构C语言树二叉树详细举例介绍.pptx》由会员分享，可在线阅读，更多相关《数据结构C语言树二叉树详细举例介绍.pptx（138页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、6.1 树的类型定义6.2 二叉树的类型定义6.3 二叉树的存储结构6.4 二叉树的遍历6.5 线索二叉树6.6 树和森林的表示方法6.7 树和森林的遍历6.8 哈夫曼树与哈夫曼编码目目 录录第1页/共138页6.1 树的类型定义树的类型定义第2页/共138页数据对象 D：D是具有相同特性的数据元素的集合。若D为空集，则称为空树；否则:(1)在D中存在唯一的称为根的数据元素root,(2)当n1时，其余结点可分为m(m0)个互 不相交的有限集T1,T2,Tm,其中每一 个子集本身又是一棵符合本定义的树，称为根root的子树。数据关系 R：ADTA AB BC CD DE EF FGGH HI
2、IJ JK KL LMM第3页/共138页2023/3/254树的示例树的示例A AB BC CD DE EF FGGH HI IJ JK KL LMMA AB BC CD DE EF FGGH HI IJ JK KL LMMA AB BC CD DE EF FGGH HI IJ JK KL LMM第4页/共138页 基本操作：查 找 类 插 入 类删 除 类第5页/共138页Root(T)/求树的根结点 Value(T,cur_e)/求当前结点的元素值 Parent(T,cur_e)/求当前结点的双亲结点LeftChild(T,cur_e)/求当前结点的最左孩子 RightSibling(T
3、,cur_e)/求当前结点的右兄弟TreeEmpty(T)/判定树是否为空树 TreeDepth(T)/求树的深度TraverseTree(T,Visit()/遍历查找类操作查找类操作第6页/共138页InitTree(&T)/初始化置空树 CreateTree(&T,definition)/按定义构造树Assign(T,cur_e,value)/给当前结点赋值InsertChild(&T,&p,i,c)/将以c为根的树插入为结点p的第i棵子树插入类操作插入类操作第7页/共138页 ClearTree(&T)/将树清空 DestroyTree(&T)/销毁树的结构DeleteChild(&T,
4、&p,i)/删除结点p的第i棵子树删除类操作删除类操作第8页/共138页ABCDEFGHIJMKLA(B(E,F(K,L),C(G),D(H,I,J(M)T1T3T2树根树的广义表表示树的广义表表示第9页/共138页()有确定的根；()树根和子树根之间为有向关系。有向树有序树子树之间存在确定的次序关系。无序树子树之间不存在确定的次序关系。第10页/共138页对比对比树型结构树型结构和和线性结构线性结构的结构特点的结构特点第11页/共138页线性结构树型结构第一个数据元素 (无前驱)根结点 (无前驱)最后一个数据元素 (无后继)多个叶子结点 (无后继)其它数据元素(一个前驱、一个后继)其它数据元
5、素(一个前驱、多个后继)第12页/共138页基基 本本 术术 语语第13页/共138页结点:结点的度:树的度:叶子结点:分支结点:数据元素+若干指向子树的分支分支的个数树中所有结点的度的最大值度为零的结点度大于零的结点DHIJM第14页/共138页(从根到结点的)路径：孩子结点、双亲结点、兄弟结点、堂兄弟祖先结点、子孙结点结点的层次:树的深度：由从根到该结点所经分支和结点构成ABCDEFGHIJMKL假设根结点的层次为1,第l 层的结点的子树根结点的层次为l+1树中叶子结点所在的最大层次第15页/共138页任何一棵非空树是一个二元组 Tree=（root，F）其中：root 被称为根结点，F
6、被称为子树森林森林：是m（m0）棵互不相交的树的集合ArootBCDEFGHIJMKLF第16页/共138页6.2 二叉树的类型定义第17页/共138页 二叉树或为空树；或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。ABCDEFGHK根结点左子树右子树第18页/共138页NNNNLRRL空树只含根结点右子树为空树左子树为空树左右子树均不为空树二叉树的五种基本形态：二叉树的五种基本形态：第19页/共138页查 找 类插 入 类删 除 类 二叉树的主要基本操作二叉树的主要基本操作第20页/共138页 Root(T);Value(T,e);Parent(T,e);LeftCh
7、ild(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();查查查查 找找找找 类类类类 操操操操 作作作作第21页/共138页 InitBiTree(&T);Assign(T,&e,value);CreateBiTree(&T,definition);Ins
8、ertChild(T,p,LR,c);插插插插 入入入入 类类类类 操操操操 作作作作第22页/共138页ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T,p,LR);删删删删 除除除除 类类类类 操操操操 作作作作第23页/共138页二叉树二叉树的重要特性的重要特性第24页/共138页性质性质1：在二叉树的第在二叉树的第 i 层上至多有层上至多有2i-1 个结个结点。点。(i1)用归纳法证明：归纳基：归纳假设：归纳证明：i=1 层时，只有一个根结点，2i-1=20=1；假设对所有的 j，1 j i，命题成立;二叉树上每个结点至多有两棵子树，则第
9、i 层的结点数=2i-2 2=2i-1。第25页/共138页性质性质 2：深度为深度为 k 的二叉树上至多含的二叉树上至多含 2k-1 个结点（个结点（k1）证明：基于上一条性质，深度为 k 的二叉树上的结点数至多为 20+21+2k-1=2k-1 第26页/共138页性质性质 3：对任何一棵二叉树，若它含有对任何一棵二叉树，若它含有n0 个个叶子结点、叶子结点、n2 个度为个度为 2 的结点，则的结点，则必存在关系式：必存在关系式：n0=n2+1证明：设 二叉树上结点总数 n=n0+n1+n2又 二叉树上分支总数 b=n1+2n2 而 b=n-1=n0+n1+n2-1由此，n0=n2+1第2
10、7页/共138页满二叉树：深度为k且含有2k-1个结点的二叉树。完全二叉树：树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结点一一对应。123456789 10 11 12 13 14 15abcdefghij两类两类特殊特殊的二叉树：的二叉树：第28页/共138页证明：设 完全二叉树的深度为 k 则根据第二条性质得 2k-1 n 2k 即 k-1 log2 n n，则该结点无左孩子，否则，编号为 2i 的结点为其左孩子结点；(3)若 2i+1n，则该结点无右孩子结点，否则，编号为2i+1 的结点为其右孩子结点。性质性质 5：第30页/共138页二.二叉树的链式 存储表示一.二叉树的
11、顺序 存储表示6.3 二叉树的存储结构二叉树的存储结构第31页/共138页#define MAX_TREE_SIZE 100 /二叉树的最大结点数typedef TElemType SqBiTreeMAX_TREE_SIZE;/1号单元存储根结点SqBiTree bt;一一.二叉树的顺序存储表示二叉树的顺序存储表示第32页/共138页 A B D C E FABCDEF 0 1 2 3 4 5 6 7 8 9 10 11 12 13 142511437例如例如:第33页/共138页1.二叉链表2三叉链表3双亲链表4线索链表二二.二叉树的链式存储表示二叉树的链式存储表示第34页/共138页ADE
12、BCFrootlchild data rchild结点结构:1.1.二叉链表二叉链表第35页/共138页typedef struct BiTNode /结点结构 TElemType data;struct BiTNode *lchild,*rchild;/左、右孩子指针 BiTNode,*BiTree;lchild data rchild结点结构:C 语言的类型描述如下语言的类型描述如下:第36页/共138页ADEBCFrootparent lchild data rchild结点结构:2三叉链表三叉链表第37页/共138页 typedef struct TriTNode /结点结构 TEle
13、mType data;struct TriTNode *lchild,*rchild;/左、右孩子指针 struct TriTNode *parent;/双亲指针 TriTNode,*TriTree;parent lchild data rchild结点结构:C 语言的类型描述如下:第38页/共138页LRRRL0123456 data parent结点结构:LRTag3 3双亲链表双亲链表第39页/共138页 typedef struct BPTNode /结点结构 TElemType data;int parent;/指向双亲的指针 char LRTag;/左、右孩子标志域 BPTNode
14、 typedef struct BPTree/树结构 BPTNode nodesMAX_TREE_SIZE;int num_node;/结点数目 int root;/根结点的位置 BPTree第40页/共138页6.4二叉树的遍历第41页/共138页一、问题的提出二、先左后右的遍历算法三、算法的递归描述四、中序遍历算法的非递归描述五、遍历算法的应用举例第42页/共138页 顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。一.问题的提出“访问”的含义可以很广，如：输出结点的信息等。第43页/共138页 “遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路
15、径(因为每个结点均只有一个后继)，故不需要另加讨论。而二叉树是非线性结构，每个结点有两个后继，则存在如何遍历即按什么样的搜索路径遍历的问题。第44页/共138页 对对“二叉树二叉树”而言，可以有三条搜索路径：而言，可以有三条搜索路径：1先上后下先上后下的按层次遍历；的按层次遍历；2先左先左(子树子树)后右后右(子树子树)的遍历；的遍历；3先右先右(子树子树)后左后左(子树子树)的遍历。的遍历。第45页/共138页先（根）序的遍历算法中（根）序的遍历算法后（根）序的遍历算法二二.先左后右的遍历算法先左后右的遍历算法第46页/共138页 若二叉树为空树，则空操作；否则，（1）访问根结点；（2）先序
16、遍历左子树；（3）先序遍历右子树。先（根）序的遍历算法：先（根）序的遍历算法：第47页/共138页 若二叉树为空树，则空操作；否则，（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。中（根）序的遍历算法：中（根）序的遍历算法：第48页/共138页 若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。后（根）序的遍历算法：后（根）序的遍历算法：第49页/共138页void Preorder(BiTree T,void(*visit)(TElemType&e)/先序遍历二叉树 if(T)visit(T-data);/访问结点 Preorder(
17、T-lchild,visit);/遍历左子树 Preorder(T-rchild,visit);/遍历右子树 三三.算法的递归描述算法的递归描述第50页/共138页BiTNode*GoFarLeft(BiTree T,Stack&S)if(!T)return NULL;while(T-lchild)/直到最左端 Push(S,T);T=T-lchild;return T;四四.中序遍历算法的非递归描述中序遍历算法的非递归描述abcdefghij第51页/共138页void Inorder_I(BiTree T,void(*visit)(TelemType&e)Stack S;InitStack
18、(S);t=GoFarLeft(T,S);/找到最左下的结点 while(t)visit(t-data);if(t-rchild)t=GoFarLeft(t-rchild,S);else if(!StackEmpty(S)/栈不空时退栈 t=Pop(S);else t=NULL;/栈空表明遍历结束 第52页/共138页1.统计二叉树中叶子结点的个数 (先序遍历，习题6.42）2.求二叉树的深度 (后序遍历，参见习题6.44）3.复制二叉树 (后序遍历，参见习题6.46）4.建立二叉树的存储结构五五.遍历算法的应用举例遍历算法的应用举例第53页/共138页算法基本思想:先序(或中序或后序)遍历二
19、叉树，在遍历过程中查找叶子结点，并计数。因此，需在遍历算法中增添一个“计数”的参数，并将算法中“访问结点”的操作改为:若是叶子，则计数器增1。1.统计二叉树中叶子结点的个数统计二叉树中叶子结点的个数（习题习题6.42）第54页/共138页void CountLeaf(BiTree T,int&count)if(T)/初值为0 if(!T-lchild&!T-rchild)count+;/对叶子结点计数 CountLeaf(T-lchild,count);CountLeaf(T-rchild,count);调用：num0；CountLeaf（T，num）；第55页/共138页算法基本思想:从二叉
20、树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为:求得左、右子树深度的最大值，然后加 1。首先分析二叉树的深度和它的左、右子树深度之间的关系。2.求二叉树的深度求二叉树的深度(后序遍历后序遍历)（参见（参见习题习题6.44）第56页/共138页int Depth(BiTree T)/返回二叉树的深度 if(!T)depthval=0;else depthLeft =Depth(T-lchild);depthRight=Depth(T-rchild);depthval=1+(depthLeft depthRight?d
21、epthLeft:depthRight);return depthval;第57页/共138页其基本操作为:生成一个结点。根元素T左子树右子树根元素NEWT左子树右子树左子树右子树(后序遍历)3.复制二叉树复制二叉树（参见（参见习题习题6.46）第58页/共138页BiTNode*GetTreeNode(TElemType item,BiTNode*lptr,BiTNode*rptr)if(!(T=(BiTNode*)malloc(sizeof(BiTNode)exit(1);T-data=item;T-lchild=lptr;T-rchild=rptr;return T;生成二叉树的一个结点
22、(其数据域为item,左指针域为lptr,右指针域为rptr)第59页/共138页BiTNode*CopyTree(BiTNode*T)if(!T)return NULL;if(T-lchild)newlptr=CopyTree(T-lchild);/复制左子树 else newlptr=NULL;if(T-rchild)newrptr=CopyTree(T-rchild);/复制右子树 else newrptr=NULL;newT=GetTreeNode(T-data,newlptr,newrptr);return newT;问题：若用先序框架，应如何修改？第60页/共138页ABCDEFG
23、HK D C B H K G F E A例如:下列二叉树的复制过程如下:newT第61页/共138页4.4.建立二叉树的建立二叉树的 存储结构存储结构不同的定义方法相应有不同的存储结构的建立算法第62页/共138页 以字符串的形式 根 左子树 右子树 定义一棵二叉树例如:ABCD以空白字符“”表示A(B(,C(,),D(,)空树只含一个根结点的二叉树A以字符串“A ”表示以下列字符串表示第63页/共138页Status CreateBiTree(BiTree&T)scanf(&ch);if(ch=)T=NULL;else if(!(T=(BiTNode*)malloc(sizeof(BiTNo
24、de)exit(OVERFLOW);T-data=ch;/生成根结点 CreateBiTree(T-lchild);/构造左子树 CreateBiTree(T-rchild);/构造右子树 return OK;第64页/共138页A B C D A BCD上页算法执行过程举例如下:ATBCD第65页/共138页 按给定的表达式建相应二叉树 由先缀表示式建树例如：已知表达式的先缀表示式 -+a b c/d e 由原表达式建树例如：已知表达式(a+b)c d/e第66页/共138页对应先缀表达式 -+a b c/d e的二叉树abcde-+/特点：操作数为叶子结点，运算符为分支结点第67页/共13
25、8页scanf(&ch);if(In(ch,字母集)建叶子结点;else 建根结点;递归建左子树;递归建右子树;由先缀表示式建树的算法的基本操作：第68页/共138页a+b(a+b)c d/ea+bc 分析表达式和二叉树的关系:ab+abc+abc+(a+b)cabcde-+/第69页/共138页基本操作:scanf(&ch);if(In(ch,字母集)建叶子结点;暂存;else if (In(ch,运算符集)和前一个运算符比较优先数;若当前的优先数“高”，则暂存;否则建子树;第70页/共138页void CrtExptree(BiTree&T,char exp)InitStack(S);Pu
26、sh(S,#);InitStack(PTR);p=exp;ch=*p;while(!(GetTop(S)=#&ch=#)if(!IN(ch,OP)CrtNode(t,ch);/建叶子结点并入栈 else if(ch!=#)p+;ch=*p;Pop(PTR,T);第71页/共138页switch(ch)case(:Push(S,ch);break;case):Pop(S,c);while(c!=()CrtSubtree(t,c);/建二叉树并入栈 Pop(S,c);break;defult:/switch 第72页/共138页while(!Gettop(S,c)&(precede(c,ch)Cr
27、tSubtree(t,c);Pop(S,c);if(ch!=#)Push(S,ch);break;第73页/共138页建叶子结点的算法为：void CrtNode(BiTree&T,char ch)T=(BiTNode*)malloc(sizeof(BiTNode);T-data=char;T-lchild=T-rchild=NULL;Push(PTR,T);第74页/共138页建子树的算法为：void CrtSubtree(Bitree&T,char c)T=(BiTNode*)malloc(sizeof(BiTNode);T-data=c;Pop(PTR,rc);T-rchild=rc;P
28、op(PTR,lc);T-lchild=lc;Push(PTR,T);第75页/共138页 仅知二叉树的先序序列“abcdefg”不能唯一确定一棵二叉树，由二叉树的先序和中序序列建树 如果同时已知二叉树的中序序列“cbdaegf”,则会如何？二叉树的先序序列二叉树的中序序列左子树左子树右子树右子树根根第76页/共138页a b c d e f gc b d a e g f例如:aab bccddeeffggabcdefg先序序列中序序列第77页/共138页void CrtBT(BiTree&T,char pre,char ino,int ps,int is,int n)/已知preps.ps+
29、n-1为二叉树的先序序列,/insis.is+n-1为二叉树的中序序列,/本算法由此两个序列构造二叉链表 if(n=0)T=NULL;else k=Search(ino,preps);/在中序序列中查询 if(k=-1)T=NULL;else 第78页/共138页T=(BiTNode*)malloc(sizeof(BiTNode);T-data=preps;if(k=is)T-Lchild=NULL;else CrtBT(T-Lchild,pre,ino,ps+1,is,k-is);if(k=is+n-1)T-Rchild=NULL;else CrtBT(T-Rchild,pre,ino,ps
30、+1+(k-is),k+1,n-(k-is)-1);第79页/共138页6.5 线索二叉树线索二叉树 何谓线索二叉树？何谓线索二叉树？线索链表的遍历算法线索链表的遍历算法 如何建立线索链表？如何建立线索链表？第80页/共138页遍历二叉树的结果是，求得结点的一个线性序列。ABCDEFGHK例如:先序序列:A B C D E F G H K中序序列:B D C A H G K F E后序序列:D C B H K G F E A一一.何谓线索二叉树？何谓线索二叉树？第81页/共138页指向该线性序列中的“前驱”和 “后继”的指针，称作“线索”与其相应的二叉树，称作“线索二叉树”包含“线索”的存储结
31、构，称作“线索链表”A B C D E F G H K D C B E 第82页/共138页对线索链表中结点的约定：在二叉链表的结点中增加两个标志域，并作如下规定：若该结点的左子树不空，则Lchild域的指针指向其左子树，且左标志域的值为“指针 Link”；否则，Lchild域的指针指向其“前驱”，且左标志的值为“线索 Thread”。第83页/共138页若该结点的右子树不空，则rchild域的指针指向其右子树，且右标志域的值为“指针 Link”；否则，rchild域的指针指向其“后继”，且右标志的值为“线索 Thread”。如此定义的二叉树的存储结构称作“线索链表”第84页/共138页typ
32、edef struct BiThrNod TElemType data;struct BiThrNode *lchild,*rchild;/左右指针 PointerThr LTag,RTag;/左右标志 BiThrNode,*BiThrTree;线索链表的类型描述：typedef enum Link,Thread PointerThr;/Link=0:指针，Thread=1:线索第85页/共138页 for(p=firstNode(T);p;p=Succ(p)Visit(p);由于在线索链表中添加了遍历中得到的“前驱”和“后继”的信息，从而简化了遍历的算法。二二.线索链表的遍历算法线索链表的遍
33、历算法第86页/共138页例如:对中序线索化链表的遍历算法 中序遍历的第一个结点？在中序线索化链表中结点的后继？左子树上处于“最左下”（没有左子树）的结点若无右子树，则为后继线索所指结点否则为对其右子树进行中序遍历时访问的第一个结点第87页/共138页void InOrderTraverse_Thr(BiThrTree T,void(*Visit)(TElemType e)p=T-lchild;/p指向根结点 while(p!=T)/空树或遍历结束时，p=T while(p-LTag=Link)p=p-lchild;/第一个结点 Visit(p-data);/访问结点 while(p-RTag
34、=Thread&p-rchild!=T)p=p-rchild;Visit(p-data);/访问后继结点 p=p-rchild;/p进至其右子树根 第88页/共138页 在中序遍历过程中修改结点的左、右指针域，以保存当前访问结点的“前驱”和“后继”信息。遍历过程中，附设指针pre,并始终保持指针pre指向当前访问的、指针p所指结点的前驱。三三.如何建立线索链表？如何建立线索链表？第89页/共138页void InThreading(BiThrTree p)if(p)/对以p为根的非空二叉树进行线索化 InThreading(p-lchild);/左子树线索化 if(!p-lchild)/建前驱
35、线索 p-LTag=Thread;p-lchild=pre;if(!pre-rchild)/建后继线索 pre-RTag=Thread;pre-rchild=p;pre=p;/保持 pre 指向 p 的前驱 InThreading(p-rchild);/右子树线索化 /if第90页/共138页Status InOrderThreading(BiThrTree&Thrt,BiThrTree T)/构建中序线索链表 if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode)exit(OVERFLOW);Thrt-LTag=Link;Thrt-RTag=Thread;
36、Thrt-rchild=Thrt;/添加头结点 return OK;/InOrderThreading 第91页/共138页if(!T)Thrt-lchild=Thrt;else Thrt-lchild=T;pre=Thrt;InThreading(T);pre-rchild=Thrt;/处理最后一个结点 pre-RTag=Thread;Thrt-rchild=pre;第92页/共138页 6.6 树和森林的 表示方法第93页/共138页一.双亲表示法二.孩子链表表示法三.树的二叉链表(孩子-兄弟）存储表示法树的三种存储结构树的三种存储结构第94页/共138页ABCDEFG0 A -11 B
37、02 C 03 D 04 E 2 5 F 26 G 5r=0n=7data parent一一.双亲表示法双亲表示法第95页/共138页 typedef struct PTNode Elem data;int parent;/双亲位置域 PTNode;data parent#define MAX_TREE_SIZE 100结点结构:C语言的类型描述:第96页/共138页typedef struct PTNode nodesMAX_TREE_SIZE;int r,n;/根结点的位置和结点个数 PTree;树结构:第97页/共138页ABCDEFG0 A -11 B 02 C 03 D 04 E 2
38、5 F 26 G 5r=0n=7 data firstchild 1 2 34 56-1 0 0 0 2 2 4二二.孩子链表表示法孩子链表表示法第98页/共138页typedef struct CTNode int child;struct CTNode*next;*ChildPtr;孩子结点结构:child nextC语言的类型描述:第99页/共138页 typedef struct Elem data;ChildPtr firstchild;/孩子链的头指针 CTBox;双亲结点结构 data firstchild第100页/共138页typedef struct CTBox nodes
39、MAX_TREE_SIZE;int n,r;/结点数和根结点的位置 CTree;树结构:第101页/共138页ABCDEFG AB C E D F Groot AB C E D F G 三三.树的二叉链表树的二叉链表(孩子孩子-兄弟兄弟)存储表示存储表示法法第102页/共138页typedef struct CSNode Elem data;struct CSNode *firstchild,*nextsibling;CSNode,*CSTree;C语言的类型描述:结点结构:firstchild data nextsibling第103页/共138页设森林 F=(T1,T2,Tn);T1=(r
40、oot，t11,t12,t1m);二叉树 B=(LBT,Node(root),RBT);森林和二叉树的对应关系森林和二叉树的对应关系第104页/共138页由森林转换成二叉树的转换规则为:若 F=，则 B=;否则，由 ROOT(T1)对应得到 Node(root);由(t11,t12,t1m)对应得到 LBT;由(T2,T3,Tn)对应得到 RBT。第105页/共138页由二叉树转换为森林的转换规则为:若 B=,则 F=;否则，由 Node(root)对应得到 ROOT(T1);由LBT 对应得到(t11,t12,，t1m);由RBT 对应得到(T2,T3,Tn)。第106页/共138页 由此，
41、树的各种操作均可对应二叉树的操作来完成。应当注意的是，和树对应的二叉树，其左、右子树的概念已改变为：左是孩子，右是兄弟第107页/共138页6.7 树和森林的遍历树和森林的遍历第108页/共138页一.树的遍历二.森林的遍历三.树的遍历的应用第109页/共138页树的遍历可有三条搜索路径:按层次遍历:先根(次序)遍历:后根(次序)遍历:若树不空，则先访问根结点，然后依次先根遍历各棵子树。若树不空，则先依次后根遍历各棵子树，然后访问根结点。若树不空，则自上而下自左至右访问树中每个结点。第110页/共138页 A B C DE F G H I J K 先根遍历时顶点的访问次序：A B E F C
42、D G H I J K 后根遍历时顶点的访问次序：E F B C I J K H G D A 层次遍历时顶点的访问次序：A B C D E F G H I J K第111页/共138页 B C DE F G H I J K1.森林中第一棵树的根结点；2.森林中第一棵树的子树森林；3.森林中其它树构成的森林。森林由三部分构成：第112页/共138页1.先序遍历 若森林不空，则访问森林中第一棵树的根结点;先序遍历森林中第一棵树的子树森林;先序遍历森林中(除第一棵树之外)其 余树构成的森林。即：依次从左至右对森林中的每一棵树进行先根遍历。森林的遍历森林的遍历第113页/共138页中序遍历 若森林不空
43、，则中序遍历森林中第一棵树的子树森林;访问森林中第一棵树的根结点;中序遍历森林中(除第一棵树之外)其 余树构成的森林。即：依次从左至右对森林中的每一棵树进行后根遍历。第114页/共138页先根遍历后根遍历树二叉树森林先序遍历先序遍历中序遍历中序遍历 树的遍历和二叉树遍历的树的遍历和二叉树遍历的对应关系对应关系？第115页/共138页设树的存储结构为孩子兄弟链表typedef struct CSNode Elem data;struct CSNode*firstchild,*nextsibling;CSNode,*CSTree;一、求树的深度二、输出树中所有从根到叶子的路径三、建树的存储结构第1
44、16页/共138页int TreeDepth(CSTree T)if(!T)return 0;else h1=TreeDepth(T-firstchild);h2=TreeDepth(T-nextsibling);/TreeDepthreturn(max(h1+1,h2);一一.求树的深度的算法求树的深度的算法第117页/共138页 A B C DE F G H I J K例如：对左图所示的树，其输出结果应为：A B EA B FA CA D G H IA D G H JA D G H K二二.输出树中所有从根到叶子的路径的算输出树中所有从根到叶子的路径的算法法第118页/共138页void
45、AllPath(Bitree T,Stack&S)if(T)Push(S,T-data);if(!T-lchild&!T-rchild)PrintStack(S);else AllPath(T-lchild,S);AllPath(T-rchild,S);Pop(S);/if(T)/输出二叉树上从根到所有叶子结点的路径第119页/共138页void OutPath(CSTree T,Stack&S)while(T)Push(S,T-data);if(!T-firstchild)Printstack(s);else OutPath(T-firstchild,s);Pop(S);T=T-nextsi
46、bling;/while/OutPath/输出森林中所有从根到叶的路径第120页/共138页 和二叉树类似，不同的定义相应有不同的算法。假设以二元组(F,C)的形式自上而下、自左而右依次输入树的各边，建立树的孩子-兄弟链表。三三三三.建树的存储结构的算法建树的存储结构的算法建树的存储结构的算法建树的存储结构的算法第121页/共138页ABCDEFG例如:对下列所示树的输入序列应为:(#,A)(A,B)(A,C)(A,D)(C,E)(C,F)(E,G)ABCD(#,A)(A,B)(A,C)(A,D)(C,E)可见，算法中需要一个队列保存已建好的结点的指针第122页/共138页void Creat
47、eTree(CSTree&T)T=NULL;for(scanf(&fa,&ch);ch!=;scanf(&fa,&ch)p=GetTreeNode(ch);/创建结点EnQueue(Q,p);/指针入队列if(fa=)T=p;/所建为根结点 else /非根结点的情况 /for/CreateTree 第123页/共138页GetHead(Q,s);/取队列头元素(指针值)while(s-data!=fa)/查询双亲结点 DeQueue(Q,s);GetHead(Q,s);if(!(s-firstchild)s-firstchild=p;r=p;/链接第一个孩子结点else r-nextsibl
48、ing=p;r=p;/链接其它孩子结点 第124页/共138页6.8 哈夫曼树与哈夫曼树与 哈夫曼编码哈夫曼编码 最优树的定义 如何构造最优树 前缀编码 第125页/共138页树的路径长度定义为：树中每个结点的路径长度之和。结点的路径长度定义为：从根结点到该结点的路径上 分支的数目。一一.最优树的定义最优树的定义第126页/共138页 树的带权路径长度定义为：树中所有叶子结点的带权路径长度之和 WPL(T)=wklk(对所有叶子结点)在所有含 n 个叶子结点、并带相同权值的 m 叉树中，必存在一棵其带权路径长度取最小值的树，称为“最优树”。例如：第127页/共138页27 9 75492WPL
49、(T)=72+52+23+43+92 =60WPL(T)=74+94+53+42+21 =89 54第128页/共138页 根据给定的 n 个权值 w1,w2,wn，构造 n 棵二叉树的集合 F=T1,T2,Tn，其中每棵二叉树中均只含一个带权值 为 wi 的根结点,其左、右子树为空树;(1)(哈夫曼算法)以二叉树为例:二二二二.如何构造最优树如何构造最优树如何构造最优树如何构造最优树第129页/共138页 在 F 中选取其根结点的权值为最 小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并 置这棵新的二叉树根结点的权值 为其左、右子树根结点的权值之 和;(2)第130页/共138页 从
50、F中删去这两棵树，同时加入 刚生成的新树;重复(2)和(3)两步，直至 F 中只 含一棵树为止。(3)(4)第131页/共138页9例如:已知权值 W=5,6,2,9,7 562752769767139527第132页/共138页6713952795271667132900001111000110110111第133页/共138页 指的是，任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。利用哈夫曼树可以构造一种不等长的二进制编码，并且构造所得的哈夫曼编码是一种最优前缀编码，即使所传电文的总长度最短。三三三三.前缀编码前缀编码前缀编码前缀编码第134页/共138页1.熟练掌握二叉树的