第六章树和二叉树2.ppt

《第六章树和二叉树2.ppt》由会员分享，可在线阅读，更多相关《第六章树和二叉树2.ppt（137页珍藏版）》请在三一办公上搜索。

1、1,第六章 树和二叉树,2,树是常用的数据结构,家族各种组织结构操作系统中的文件管理编译原理中的源程序语法结构信息系统管理。,3,树(tree)是n(n=0)个结点的有限集T，其中：有且仅有一个特定的结点，称为树的根(root)。当n1时，其余结点可分为m(m0)个互不相交的有限集T1,T2,Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree)特点：非空树中至少有一个结点根树中各子树是互不相交的集合,树的定义,4,根,子树,空树,n=0,n=1,n1,5,树的表示法主要有5种,图形表示法嵌套集合表示法广义表表示法凹入表示法左孩子右兄弟表示法,6,7,树的其它表示方式,凹入表示,嵌

2、套集合,广义表,8,线性结构,树型结构,第一个数据元素(无前驱),根结点(无前驱),最后一个数据元素(无后继),多个叶子结点(无后继),其它数据元素(一个前驱、一个后继),其它数据元素(一个前驱、多个后继),对比树型结构和线性结构的结构特点,9,数据对象 D：,D是具有相同特性的数据元素的集合。,若D为空集，则称为空树。否则:(1)在D中存在唯一的称为根的数据元素root；(2)当n1时，其余结点可分为m(m0)个互 不相交的有限集T1,T2,Tm，其中每一 棵子集本身又是一棵符合本定义的树，称为根root的子树。,数据关系 R：,树的抽象数据类型定义,10,基本操作：,查 找 类,插 入 类

3、,删 除 类,11,Root(T)/求树的根结点,查找类：,Value(T,cur_e)/求当前结点的元素值,Parent(T,cur_e)/求当前结点的双亲结点,LeftChild(T,cur_e)/求当前结点的最左孩子,RightSibling(T,cur_e)/求当前结点的右兄弟,TreeEmpty(T)/判定树是否为空树,TreeDepth(T)/求树的深度,TraverseTree(T,Visit()/遍历,12,InitTree(&T)/初始化置空树,插入类：,CreateTree(&T,definition)/按定义构造树,Assign(T,cur_e,value)/给当前结点赋

4、值,InsertChild(&T,&p,i,c)/将以c为根的树插入为结点p的第i棵子树,13,ClearTree(&T)/将树清空,删除类：,DestroyTree(&T)/销毁树的结构,DeleteChild(&T,&p,i)/删除结点p的第i棵子树,14,结点:,结点的度:,树的度:,叶子结点:,分支结点:,数据元素+若干指向子树的分支,分支的个数,度为零的结点,度大于零的结点,基 本 术 语,树中所有结点的度的最大值,15,路径：,孩子结点、双亲结点兄弟结点、堂兄弟结点祖先结点、子孙结点,结点的层次:,树的深度：,由从根到该结点所经分支和结点构成,根结点的层次为1，根的孩子为第二层，第

5、l 层的结点的子树根结点的层次为l+1,树中叶子结点所在的最大层次,16,任何一棵非空树是一个二元组 Tree=（root，F）其中：root 被称为根结点 F 被称为子树森林,森林：,是m（m0）棵互不相交的树的集合,B,C,D,E,F,G,H,I,J,M,K,L,17,()有确定的根；()树根和子树根之间为有向关系。,有向树：,有序树：,子树之间存在确定的次序关系。,无序树：,子树之间不存在确定的次序关系。,分隔符,19,一对多（1:n），有多个直接后继（如家谱树、目录树等等），但只有一个根结点，且子树之间互不相交。,树的存储结构,讨论1：树是非线性结构，该怎样存储？,特点：,仍然有顺序存

6、储、链式存储等方式。,树的逻辑结构,20,讨论3：树的链式存储方案应该怎样制定？,复原困难,讨论2：树的顺序存储方案应该怎样制定？,可用多重链表：一个前趋指针，n个后继指针。细节问题：树中结点的结构类型样式该如何设计？即应该设计成“等长”还是“不等长”？缺点：等长结构太浪费（每个结点的度不一定相同）；不等长结构太复杂（要定义好多种结构类型）。,先研究最简单、最有规律的树，然后设法把一般的树转化为简单树(二叉树)。,可规定为：,从上至下、从左至右将树的结点依次存入内存。,重大缺陷：,解决思路：,21,树的运算,要明确：1.普通树（即多叉树）若不转化为二叉树，则运算很难实现。2.二叉树的运算仍然是

7、插入、删除、修改、查找、排序等，但这些操作必须建立在对树结点能够“遍历”的基础上！,遍历指每个结点都被访问且仅访问一次，不遗漏不重复,本章重点：二叉树的表示和实现,22,6.2 二叉树,为何要重点研究每结点最多只有两个“叉”的树？二叉树的结构最简单，规律性最强；可以证明，所有树都能转为唯一对应的二叉树，不失一般性。,1.二叉树的定义2.二叉树的性质 二叉树的存储结构 二叉树的运算（6.3节）,23,二叉树是n(n0)个结点的有限集,它或为空树(n=0),或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成。特点 每个结点至多有二棵子树(即不存在度大于2的结点)二叉树的子树有左、右之

8、分，且其次序不能颠倒,二叉树,根结点,左子树,右子树,24,五种基本形态,问：具有3个结点的二叉树可能有几种不同形态？,有5种,25,二叉树的抽象数据类型定义,ADT BinaryTree数据对象D:数据关系R:,D是具有相同特性的数据元素的集合。若D=，则R=；若D，则R=H；存在二元关系：root 唯一/关于根的说明 DlDr=/关于子树不相交的说明,26,基本操作 P：20个ADT BinaryTree,27,性质 1：在二叉树的第 i 层上至多有2i-1 个结点。(i1),用归纳法证明：归纳基：归纳假设：归纳证明：,i=1 层时，只有一个根结点：2i-1=20=1；,设i=k-1时成立

9、，最多有2k-2个结点,二叉树上每个结点至多有两棵子树，则第 i=k时，结点数=2k-2 2=2k-1,二叉树的性质,=2i-1,28,性质2：深度为k的二叉树至多有2k-1个结点(k1)证明：由性质1，可得深度为k 的二叉树最大结点数是：,29,证明：二叉树中全部结点数nn0+n1+n2(叶子数1度结点数2度结点数)又二叉树中全部结点数nB+1(总分支数根结点)（除根结点外，每个结点必有一个直接前趋，即一个分支）而 总分支数B=n1+2n2(1度结点必有1个直接后继，2度结点必有2个)三式联立可得：n0+n1+n2=n1+2n2+1,即n0=n2+1,物理意义：叶子数2度结点数1,性质3:对

10、于任何一棵二叉树，若2度的结点数有n2个，则叶子数（n0）必定为n21（即n0=n2+1）,30,2.深度为的二叉树的结点总数，最多为 个。)k-1)log2k)k)k,1.树中各结点的度的最大值称为树的。)高度)层次)深度)度,D,C,C,3.深度为9的二叉树中至少有 个结点。)9)8)91,练习：,31,1、满二叉树定义：一棵深度为k且有2k-1个结点的二叉树。特点：每一层上的结点数都是最大结点数,几种特殊形式的二叉树,32,2、完全二叉树定义：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为完全二叉树。特点：（1）叶子结点只可能在

11、层次最大的两层上出现。（2）对任一结点，若其右分支下子孙的最大层次为L，则其左分支下子孙的最大层次必为L或L+1。,33,34,具有 n 个结点的完全二叉树的深度为 log2n+1。,证明：,设完全二叉树的深度为 k 则根据第二条性质得 2k-1-1 n 2k-1 或 2k-1 n 2k 即 k-1 log2 n k 因为 k 只能是整数，因此，k=log2n+1。,性质 4（完全二叉树的特性）,35,一棵含有n个结点的二叉树，可能达到的最大深度和最小深度各是多少？,问题：,答：最大n,最小log2n+1,36,性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i(1i n

12、)，有：(1)如果i=1，则结点i是二叉树的根，无双亲；如果i1，则其双亲是i/2。(2)如果2in，则结点i无左孩子；如果2i n，则其左孩子是2i。(3)如果2i+1n，则结点i无右孩子；如果2i+1 n，则其右孩子是2i+1。,37,1、顺序存储结构实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素。特点：结点间关系蕴含在其存储位置中 浪费空间，适于存满二叉树和完全二叉树,二叉树的存储结构,38,#define MAX_TREE_SIZE 100/二叉树的最大结点数typedef TElemType SqBiTreeMAX _ TREE_SIZE;SqBiTree bt;,二叉树

13、的顺序存储表示,显然，这种存储表示方法只适合于完全二叉树，对于一般的二叉树将造成存储空间的很大浪费。因此二叉树的常用存储结构是链表。,思考：一个深度为 k 且只有 k 个结点的右单支树需要的数组存储空间为多少？,39,二叉树的遍历,40,二叉树的链式存储表示,1.二叉链表,2三叉链表,3线索链表,在n个结点的二叉链表中，有n+1个空指针域,（1）二叉链表typedef struct BiTNode TElemType data;struct BiTNode*lchild,*rchild;BiTNode，*Bitree;,（2）三叉链表typedef struct BiTNode TElemTy

14、pe data;struct BiTNode*lchild,*rchild,*parent;BiTNode,*Bitree;,43,顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。,问题的提出,“访问”的含义可以很广，如：输出结点的信息等。,“遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论。,而二叉树是非线性结构，每个结点有两个后继，则存在如何遍历即按什么样的搜索路径遍历的问题。,遍历的用途：它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。,44,先序遍历：先访问根结

15、点,然后分别先序遍历左子树、右子树。中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树。后序遍历：先后序遍历左、右子树，然后访问根结点。按层次遍历：从上到下、从左到右访问各结点。,二叉树的遍历,45,D L R,先序遍历序列：A B D C,先序遍历:,46,L D R,中序遍历序列：B D A C,中序遍历:,47,L R D,后序遍历序列：D B C A,后序遍历:,分隔符,49,先序遍历：,中序遍历：,后序遍历：,层次遍历：,用二叉树表示算术表达式,-+a*b-cd/ef 前缀表达式,a+b*c-d-e/f 中缀表达式,abcd-*+ef/-后缀表达式,-+/a*efb-cd

16、,void PreOrder(BiTree T)if(T)printf(%s,T-data);PreOrder(T-lchild);PreOrder(T-rchild);,先序遍历程序：,void InOrder(BiTree T)if(T)InOrder(T-lchild);printf(%s,T-data);InOrder(T-rchild);,中序遍历程序：,void PostOrder(BiTree T)if(T)PostOrder(T-lchild);printf(%s,T-data);PostOrder(T-rchild);,后序遍历程序：,53,编写按层次顺序遍历二叉树的算法(同

17、一层自左至右),分析:按层次遍历的定义:若树不空，则首先访问根结点，然后，依照其双亲结点访问的顺序，依次访问它们的左、右孩子结点;因此，需要一个“队列”保存已被访问的结点,54,void BFSTraverse(BiTree T)InitQueue(Q);/置空的辅助队列Q if(T)EnQueue(Q,T);/根结点入队列 while(!QueueEmpty(Q)DeQueue(Q,p);/队头元素出队并置为p Visit(p-data);if(p-Lchild)EnQueue(Q,p-Lchild);/左子树根入队列 if(p-Rchild)EnQueue(Q,p-Rchild);/右子树

18、根入队列/while,55,层次遍历算法(需要利用队列),void LayerOrder(Bitree T)/层序遍历二叉树 InitQueue(Q);/建队（初始化队列）EnQueue(Q,T);/结点T入队 while(!QueueEmpty(Q)DeQueue(Q,p);/队首结点出队(送入p)printf(%s,p-data);/访问根节点 if(p-lchild)EnQueue(Q,p-lchild);/p的左孩子入队 if(p-rchild)EnQueue(Q,p-rchild);/p的右孩子入队/LayerOrder,56,递归算法void pre(Bitree*T)/先序遍历二

19、叉树 if(T)printf(%dt,T-data);pre(T-lchild);pre(T-rchild);,返回,返回,返回,返回,A,C,B,D,返回,先序序列：A B D C,57,递归算法void in(Bitree*T)/中序遍历二叉树 if(T)in(T-lchild);printf(%dt,T-data);in(T-rchild);,A,C,B,D,A,中序序列：B D A C,返回,printf(B);,printf(D);,返回,返回,printf(A);,printf(C);,返回,返回,58,对遍历的分析：,1.从前面的三种遍历算法可以知道：如果将printf语句抹去，

20、从递归的角度看，这三种算法是完全相同的，或者说这三种遍历算法的访问路径是相同的，只是访问结点的时机不同。,从虚线的出发点到终点的路径上，每个结点经过3次。,第1次经过时访问，是先序遍历第2次经过时访问，是中序遍历第3次经过时访问，是后序遍历,2.二叉树遍历的时间效率和空间效率时间效率:O(n)/每个结点只访问一次空间效率:O(n)/栈占用的最大辅助空间,59,二叉树的建立（P131）,用空格字符表示无孩子或指针为空,例：将下面的二叉树以二叉链表形式存入计算机内。,考虑1：输入结点时怎样表示“无孩子”？考虑2：以何种遍历方式来输入和建树？,将二叉树按先序遍历次序输入：A B C D E G F,

21、以先序遍历最为合适，让每个结点都能及时被连接到位。,60,Status CreateBiTree(BiTree/CreateBiTree,输入序列：A B C D E G F,61,A B C D,A,B,C,D,上页算法执行过程举例如下：,A,T,B,C,D,62,1、统计二叉树中叶子结点的个数,遍历算法的应用举例,void CountLeaf(BiTree T,int/if/CountLeaf,63,2、求二叉树的深度,算法基本思想:,从二叉树深度的定义可知:二叉树的深度应为其左、右子树深度的最大值加1。,int Depth(BiTree T)/返回二叉树的深度 if(!T)depthva

22、l=0;else m=Depth(T-lchild);n=Depth(T-rchild);depthval=1+(m n?m:n);return depthval;,64,仅知二叉树的先序序列“abcdefg”能唯一确定一棵二叉树?,由二叉树的先序和中序序列建树,如果同时已知二叉树的中序序“cbdaegf”，则会如何？,二叉树的先序序列,二叉树的中序序列,左子树,左子树,右子树,右子树,根,根,65,a b c d e f g,c b d a e g f,例如:,a,a,b,b,c,c,d,d,e,e,f,f,g,g,a,b,c,d,e,f,g,先序序列中序序列,66,已知一棵二叉树的中序序列

23、和后序序列分别是BDCEAFHG 和 DECBHGFA，请画出这棵二叉树。分析：由后序遍历特征，根结点必在后序序列尾部（即A）；由中序遍历特征，根结点必在其中间，而且其左部必全部是左子树的子孙（即BDCE），其右部必全部是右子树的子孙（即FHG）；继而，根据后序中的DECB子树可确定B为A的左孩子，根据HGF子串可确定F为A的右孩子；以此类推。,67,已知中序遍历：B D C E A F H G已知后序遍历：D E C B H G F A,（B D C E）,（F H G）,A,（D C E）,A,B,B,已知中序遍历和后序遍历结果，画出二叉树(或给出先序遍历结果),A,C,C,D C E,S

24、tatus InorderTraverse(bitree T)Initstack(S);push(S,T);While(!stackempty(S)while(GetTop(S,p),中序遍历的非递归算法描述,69,什么是线索二叉树？线索链表的遍历算法 如何建立线索链表？,线索二叉树,70,什么是线索二叉树？,n个结点二叉树，有n+1个空指针，这些空指针如果用来指向其前驱或者后继，就可提高遍历的效率,先序遍历：,中序遍历：,后序遍历：,-+a*b-cd/ef,a+b*c-d-e/f,abcd-*+ef/-,71,指向该线性序列中的“前驱”和“后继”的指针，称作“线索”,与其相应的二叉树，称作“

25、线索二叉树”,包含“线索”的存储结构，称作“线索链表”,-+a*b-cd/ef,72,二叉树中容易找到结点的左右孩子信息，但该结点的直接前驱和直接后继只能在某种遍历过程中动态获得。先依遍历规则把每个结点对应的前驱和后继线索预存起来，这叫做“线索化”。意义：从任一结点出发都能快速找到其前驱和后继，且不必借助堆栈。,对二叉树进行某种遍历之后，将得到一个线性有序的序列。例如对某二叉树的中序遍历结果是B D C E A F H G，意味着已将该树转为线性排列，显然其中结点具有唯一前驱和唯一后继。在此前提下，那n+1个空链域才可能装得下“线索”。,讨论1：二叉树是1:2的非线性结构，其直接后继可能不止一

26、个，如何存放？,讨论2.如何获得这种“直接前驱”或“直接后继”？有何意义？,73,线索二叉树定义：线索：指向前驱或后继结点的指针线索二叉树：加上线索的二叉链表表示的二叉树线索化：对二叉树按某种遍历次序使其变为线索二叉树的过程实现在有n个结点的二叉链表中必定有n+1个空链域在线索二叉树的结点中增加两个标志域ltag:若 ltag=0,lchild 域指向左孩子；若 ltag=1,lchild域指向其前驱rtag:若 rtag=0,rchild 域指向右孩子；若 rtag=1,rchild域指向其后继结点定义：,74,typedef struct BiThrNode TElemType data;

27、struct BiThrNode*lchild,*rchild;/左右指针 PointerTag LTag,RTag;/左右标志 BiThrNode,*BiThrTree;,线索链表的类型描述：,typedef enum PointerTag Link,Thread;/Link=0:指针，Thread=1:线索,75,0,0,0,0,1,1,1,1,1,1,例：先序线索二叉树,为避免悬空态，应增设一个头结点,76,0,0,0,0,1,1,1,1,1,1,例：中序线索二叉树,为避免悬空态，应增设一个头结点,为避免悬空态，应增设一个头结点,77,0,0,0,0,1,1,1,1,1,1,例：后序线索

28、二叉树,78,头结点：lt=0,lc指向根结点rt=1,rc指向遍历序列中最后一个结点遍历序列中第一个结点的lc域和最后一个结点的rc域都指向头结点,79,中序线索化的结果：,80,加上头结点：,81,给定如图所示二叉树T，请画出与其对应的中序线索二叉树。,解:因为中序遍历序列是：55 40 25 60 28 08 33 54对应线索树应当按此规律连线，即在原二叉树中添加虚线。,82,线索链表的遍历算法,由于在线索链表中添加了遍历中得到的“前驱”和“后继”的信息，从而简化了遍历的算法。,解决方案：在中序线索链表上进行遍历，关键问题有二：一是如何找到访问的第一个结点？二是如何找到每个结点在中序序

29、列中的后继？,83,在中序线索二叉树中找结点后继的方法：（1）若RTag=Thread,则rchild域直接指向其后继（2）若RTag=Link,则结点的后继应是其右子树的左链尾（LTag=Thread)的结点,在中序线索二叉树中找结点前驱的方法：（1）若LTag=Thread,则lchild域直接指向其前驱（2）若LTag=Link,则结点的前驱应是其左子树的右链尾（RTag=1)的结点,84,void InPreSucc(BiThrTree p,BiThrTree pre,BiThrTree succ)BiThrTree q;if(p-LTag=Thread)pre=p-lchild;/*

30、直接利用线索*/else/*在p的左子树中查找“最右下端”结点*/for(q=p-lchild;q-RTag=Thread;q=q-rchild);pre=q;if(p-RTag=Thread)succ=p-rchild;/*直接利用线索*/else/*在p的右子树中查找“最左下端”结点*/for(q=p-rchild;q-LTag=Thread;q=q-lchild);succ=q;,例：查找某结点的中序前驱结点和后继结点,85,中序遍历二叉线索树Status InOrderTraverse_Thr(BiThrTree T)BiThrTree p;p=T-lchild;/*p指向根结点*/w

31、hile(p!=T)/*空树或遍历结束时,p=T*/while(p-LTag=Link)p=p-lchild;Printf(%s,p-data);while(p-RTag=Thread,86,在中序遍历过程中修改结点的左、右指针域，以保存当前访问结点的“前驱”和“后继”信息。,三、如何建立线索链表,（线索化）,87,若结点没有左子树，则令其左指针指向它的“前驱”并将左指针类型标志改为“Thread”若结点没有右子树，则令它的右指针指向它的后继并将右指针类型标志改为Thread,算法基本思想：,实质：在遍历二叉树的过程中修改空指针，添加前驱或后继的线索，使之成为线索二叉树。,88,设计技巧：依某

32、种顺序遍历二叉树，对每个结点p，判断其左指针是否为空，以及其前驱结点的右指针是否为空。,若p-lchildNULL,则p-Ltag=Thread;p-lchildpre;/p的前驱线索应存p结点的左边若pre-rchildNULL,则pre-RtagThread;pre-rchild=p;/pre的后继线索应存pre结点的右边,遍历过程中，附设指针pre,并始终保持指针pre指向当前访问的、指针p所指结点的前驱。,每次只修改前驱结点的右指针（后继）和本结点的左指针（前驱）,89,void InThreading(BiThrTree p)if(p)InThreading(p-lchild);if

33、(!p-lchild)p-LTag=Thread;p-lchild=pre;if(!pre-rchild)pre-RTag=Thread;pre-rchild=p;pre=p;InThreading(p-rchild);,90,Status InOrderThreating(BiThrTree,T,pre,91,1.找出所有满足下列条件的二叉树:(a)它们在先序遍历和中序遍历时，得到的结点访问序列相同;(b)它们在后序遍历和中序遍历时，得到的结点访问序列相同;(c)它们在先序遍历和后序遍历时，得到的结点访问序列相同;,答案(a)为右单支二叉树（b)为左单支二叉树（c)为只有一个根结点的二叉树,

34、92,2.假设一棵二叉树的前序序列为 EBADCFHGIKJ 和中序序列为 ABCDEFGHIJK。请画出该二叉树。2.假设一棵二叉树的中序序列为 DCBGEAHFIJK 和后序序列为 DCEGBFHKJIA。请画出该二叉树。,93,6.4 树和森林,一、双亲表示法,二、孩子表示法,三、树的二叉链表(孩子-兄弟）存储表示法,树的表示方法,94,一、双亲表示法（顺序存储）,95,二、孩子表示法,第一种结点格式,第二种结点格式,第一种格式所有节点结构相同，操作方便，但是浪费空间n个结点度为k的树，有n(k-1)+1个空链,第二种格式节点结构不同，节省空间，操作不方便方便,96,孩子链表：,特点：,

35、顺序+链式存储结构；,找孩子容易，找双亲难,97,孩子双亲表示法,98,三、树的二叉链表存储表示法,定义结点 除放数据元素外，放两个指针，一个指向该结点的第一个孩子，另一个指向该结点的下一个兄弟（左孩子右兄弟）,转换方法,100,将树转换成二叉树,将二叉树转换成树,101,森林和二叉树的对应关系,由森林转换成二叉树,树的各种操作均可对应二叉树的操作来完成。,应当注意的是：和树对应的二叉树，其左、右子树的概念已改变为：左是孩子，右是兄弟。,102,森林与二叉树的转换森林的孩子兄弟链二叉树的二叉链,103,树和森林的遍历,一、树的遍历,二、森林的遍历,104,树的遍历,先根遍历树的规则为：若树非空

36、，则：（1）访问树的根结点；（2）依次前序遍历树的第一棵子树、第二棵子树，,后根遍历树的规则为：若树非空，则：（1）依次后序遍历树的第一棵子树、第二棵子树，（2）访问树的根结点；,105,先根遍历时顶点的访问次序：,A B E FG C D H I,后根遍历时顶点的访问次序：,E F GB C H I D A,层次遍历时顶点的访问次序：,A B C D E F G H I,106,1.森林中第一棵树的根结点；,2.森林中第一棵树的子树森林；,3.森林中其它树构成的森林。,森林由三部分构成：,森林的遍历,先序：ABCDEFGHIKJ中序：BCEDAGFKIJH,107,先序遍历时顶点的访问次序：

37、,A B E FG C D H I,后序遍历时顶点的访问次序：,E F GB C H I D A,层次遍历时顶点的访问次序：,A B C D E F G H I,108,先序：ABCDEFGHIKJ中序：BCEDAGFKIJH,先序：ABCDEFGHIKJ中序：BCEDAGFKIJH,109,树的遍历和二叉树遍历的对应关系？,先根遍历,后根遍历,树,二叉树,森林,先序遍历,先序遍历,中序遍历,中序遍历,110,若要编写按层次顺序(同一层自左至右)遍历树的算法，则应如何？,分析:因两者层次遍历的定义相同，则算法相同差别仅在于:二叉树至多只有左、右两棵子树，而树的子树个数不定，因此，当以孩子-兄弟

38、链表表示树时，需要顺第一个孩子结点的右指针一直往右找到所有孩子结点。,111,void BFSTraverse(CSTree T)InitQueue(Q);/置空的辅助队列Q if(T)EnQueue(Q,T);/根结点入队列 while(!QueueEmpty(Q)DeQueue(Q,p);/队头元素出队并置为p Visit(p-data);for(q=p-firstchild;!q;q=q-nextsibling;)EnQueue(Q,q);/子树根入队列/while,112,二叉树的典型应用,平衡树排序树字典树判定树带权树最优树,由字符串构成的二叉排序树特点：分支查找树特点：路径带权值是

39、带权路径长度最短的树，又称 Huffman树，用途之一是通信中的压缩编码。,特点：所有结点左右子树深度差1,特点：所有结点“左小右大”,6.5 Huffman树及其应用,一、什么是Huffman树二、如何构造Huffman树三、Huffman树用途四、什么是Huffman编码五、了解Huffman树及编码的程序实现方法,一、基本概念1、路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的路径。2、路径长度：路径上的分支数3、树的路径长度：从树根到每一个结点的路径长度之和4、树的带权路径长度：树中所有带权结点的路径长度之和,115,例 有4个结点，权值分别为7,5,2,4,构造有4个叶子

40、结点的二叉树。并计算其WPL,WPL=7*2+5*2+2*2+4*2=36,WPL=4*2+7*3+5*3+2*1=46,WPL=7*1+5*2+2*3+4*3=35,同样权重的叶子节点，随着树的构造不同，WPL也不相同,116,二、Huffman树的概念设有n个权值w1,w2,wn，构造一棵有n个叶子结点的二叉树，每个叶子的权值为wi,则wpl最小的二叉树叫Huffman树。,Huffman树的作用是什么？,117,赫夫曼树的应用最佳判定算法,WPL=2.2,WPL=3.15,118,比较次数：22000,比较次数：31500,设总数为10000人,119,构造Huffman树步骤：（1）根

41、据给定的n个权值w1,w2,wn，构造n棵只有根结点的二叉树，令初始权值为wj；（2）在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和；（3）在森林中删除这两棵树，同时将新得到的二叉树加入森林中；（4）重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树,三、构造Huffman树的方法Huffman算法,120,例1：W=7，5，2，4,121,例2：w=5,29,7,8,14,23,3,11,122,四、Huffman编码：数据通信用的二进制编码,定长的编码方法：,A B C D000 001 010 011,编码要求1、电文的总

42、长度最短2、任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀（前缀编码）3、事实上，可以用二叉树对字符进行编码,不定长的编码方法：,A B C D0 00 1 01,但：0000AAAA ABA BB,a:00 010 0b:01 011 01 c:10 1 110,123,Huffman编码：,10001100111=？,BAACAD,Huffman编码利用Huffman树构造的一种不等长的二进制编码。这是一种最优前缀编码，可使所传电文的总长度最短。,124,例 要传输的字符集 D=C,A,S,T,;字符出现频率 w=2,4,2,3,3,T:00;:01A:10C:110S:111

43、,编码方法：根据字符出现频率构造Huffman树，然后将树中结点引向其左孩子的分支标“0”，引向其右孩子的分支标“1”；每个字符的编码即为从根到每个叶子的路径上得到的0、1序列,125,译码方法：从Huffman树根开始，从待译码电文中逐位取码。若编码是“0”，则向左走；若编码是“1”，则向右走，一旦到达叶子结点，则译出一个字符；再重新从根出发，直到电文结束,例 电文是CAS;CAT;SAT;AT 其编码“11010111011101000011111000011000”电文为“1101000”译文只能是“CAT”,126,typedef struct int weight;int paren

44、t,lchild,rchild;HTNode,*HuffmanTree;/动态分配数组存储Huffman树typedef char*HuffmanCode;/动态分配数组存储哈夫曼编码,存储结构由权值数n唯一确定二叉树中的结点数（2n-1）并且哈夫曼树在操作过程中并不修改，所以可以采用顺序存储方式，一次性分配结点空间，含4个域的一维数组编码：从叶子到根的路径快速访问双亲译码：从根到叶子的路径快速访问孩,Huffman算法实现,哈夫曼树生成（例6.26）,8种字符，概率分别为：0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11为简化运算，将权值设为：w=5,29,7,

45、8,14,23,3,11,n=8,则m=2*n-1=15哈夫曼树如图所示：,哈夫曼树生成,原始HT,生成过程,原始HT,生成结果HT,哈夫曼编码HC,132,Void HuffmanCoding(HuffmanTree/初始化,for(i=n+1;i=m;+i)/建Huffman树/在HT1.i-1选择parent为0,且weight最小的两个节点,分别为s1,s2 Select(HT,i-1,s1,s2);HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;/建H

46、uffman树,133,HC=(Huffmancode)malloc(n+1)*sizeof(char*);cd=(char*)malloc(n*(sizeof(char);cdn-1=“0”;for(i=1;i=n;+i)start=n-1;for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)if(HTf.lchild=c）cd-start=“0”;else cd-start=“1”;HCi=(char*)malloc（(n-start)*sizeof(char)）;strcpy(HCi,134,解：先将概率放大100倍，以方便构造哈夫曼树。放大后的权值集合

47、 w=7,19,2,6,32,3,21,10，按哈夫曼树构造规则（合并、删除、替换），可得到哈夫曼树。,例1：假设用于通信的电文仅由8个字母 a,b,c,d,e,f,g,h 构成，它们在电文中出现的概率分别为 0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10，试为这8个字母设计哈夫曼编码。如果用07的二进制编码方案又如何？,135,W=7,19,2,6,32,3,21,10 的huffman树,b,c,a,d,e,g,f,h,哈夫曼树样式不惟一！,136,对应的哈夫曼编码：,Huffman码的WPL2(0.19+0.32+0.21)+4(0.07+0.06+0.1

48、0)+5(0.02+0.03)=1.44+0.92+0.25=2.61,3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3,二进制等长码的WPL,b,c,a,d,e,g,f,h,137,1.熟练掌握二叉树的结构特性，了解相应的证明方法。2.熟悉二叉树的各种存储结构的特点及适用范围。3.遍历二叉树的方法。实现二叉树遍历的的递归算法及应用。,本章学习要点,4.理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系，熟练掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。了解二叉树的线索化过程。,5.熟悉树的各种存储结构及特点，掌握树和森林与二叉树转换方法。7.了解最优树的特性,掌握建立最优树和哈夫曼编码的方法,