数据结构树和二叉树实用课件.ppt

《数据结构树和二叉树实用课件.ppt》由会员分享，可在线阅读，更多相关《数据结构树和二叉树实用课件.ppt（101页珍藏版）》请在三一办公上搜索。

1、数据结构PPT树和二叉树,数据结构PPT树和二叉树,6.1 树的定义和基本术语,什么是树？树是由 n(n 0)个结点的有限集合。如果 n=0，称为空树；如果 n 0，则 有且仅有一个特定的称之为根(Root)的结点，它只有直接后继，但没有直接前驱；当n 1，除根以外的其它结点划分为 m(m 0)个互不相交的有限集 T1,T2,Tm，其中每个集合本身又是一棵树，并且称为根的子树(SubTree)。,T=A，B，C，D，E，F，G，H，I，J，K，L，MA是根，其余结点可以划分为3个互不相交的集合：T1=B，E，F，K，L T2=C，G T3=D，H，I，J，M 这些集合中的每一集合都本身又是一棵

2、树，它们是A的子树。对于T1，B是根，其余结点可以划分为2个互不相交的集合：T11=E，K，L T12=F T11，T12是B的子树。,树的示例,1.树中只有根结点没有前趋；2.除根外，其余结点都有且仅一个前趋；3.树的结点，可以有零个或多个后继；4.除根外的其它结点，都存在唯一条从根到该结点的路径；5.树是一种分支结构。,树的逻辑结构特点,树可表示具有分支结构关系的对象例1.家族族谱 设某家庭有13个成员A、B、C、D、E、F、G、H、I、J、K、L、M，他们之间的关系可如图所示的树表示。例2.单位行政机构的组织关系,树的应用,树是常用的数据组织形式 有些应用中数据元素之间并不存在分支结构关

3、系，但是为了便于管理和使用数据，将它们用树的形式来组织。例3.计算机的文件系统 不论是DOS文件系统还是window文件系统，所有的文件是用树的形式来组织的。,文件夹1,文件夹2,文件1,文件2,文件夹11,文件夹11,文件11,文件12,C,树的应用,树的结点：包含一个数据元素的内容及若干指向子树的分支。孩子结点：结点的子树的根称为该结点的孩子；如E是B的孩子。双亲结点：B结点是A结点的孩子，则A结点是B结点的双亲；如B是E的双亲。兄弟结点：同一双亲的孩子结点；如H、I、J互为兄弟。堂兄结点：同一层上结点；如G与E、F、H、I、J互为堂兄。祖先结点：结点的祖先是从根到该结点所经分支上的所有结

4、点；如H的祖先为A、D。子孙结点：以某结点为根的子树中的任一结点称为该结点的子孙；如A的子孙为B、C、D、E、F、G、H、I、J、K、L、M。,基本术语,结点的度：结点子树的个数；如D的度为3。叶子结点：也叫终端结点，是度为0的结点；如K、L、F、G、M、I、J。分支结点：度不为0的结点；如A、B、C、D结点层次：根结点的层定义为1，根的孩子为第二层结点，依此类推。树的高度：树中结点的最大层次；如图所示树的高度为4。树的度：树中各结点的度的最大值；如图所示树的度为3。森林：m(m=0)棵互不相交的树的集合；,基本术语,EnQueue(Q,p-lchild);/入队列结点层次：根结点的层定义为1

5、，根的孩子为第二层结点，依此类推。例 w=5,29,7,8,14,23,3,11计算机的文件系统 不论是DOS文件系统还是window文件系统，所有的文件是用树的形式来组织的。pre(T L);访问：C B E G D F AB森林转变为二叉树实现过程访问：C B E G D F A一般二叉树也按完全二叉树形式存储，只有增添一些并不存在的空结点(用表示，表示该处没有元素存在，仅仅为了好理解)，使之成为一棵完全二叉树的形式，然后再用一维数组顺序存储。(a)空树(b)只含根结点(c)右子树为空树遍历一个线性结构很简单，只须从开始结点出发，顺序扫描每个结点即可。即有(2k-1)-k个单元被浪费。访问

6、结点时统计叶子结点的个数按不同的方式遍历二叉树所得到的线索二叉树是不相同的。pre(T L);性质1 在二叉树的第 i 层上至多有 2i-1个结点。五、遍历线索二叉树(续)当i1时，结点i可能是其双亲x的左孩子，也可能是右孩子，若是左孩子，由结论2知，x的左孩子应为2x，即2x=i，x=i/2；,线性结构 第一个数据元素（无前驱）；最后一个数据元素（无后继）；其它数据元素（一个前驱、一个后继）。树型结构 根结点（无前驱）；多个叶子结点（无后继）；其它数据元素（一个前驱、多个后继）。,树型结构和线性结构的结构特点对比,6.2.1 二叉树的定义 或为空树，或由根及至多两棵互不相交的左子树、右子树构

7、成(即不存在度大于2的结点)，并且左、右子树本身也是二叉树。说明：1.二叉树中每个结点最多有两棵子树，二叉树每个结点度小于等于2；2.左、右子树不能颠倒有序树；3.二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念。,6.2 二叉树,(a)(b)(c)(d)(e)(a)空树(b)只含根结点(c)右子树为空树(d)左右子树均不为空树(e)左子树为空树,L,L,R,R,二叉树的形态,性质1 在二叉树的第 i 层上至多有 2i-1个结点。(i 1)证明用归纳法证明：当i=1时，只有根结点，2 i-1=2 0=1。假设对所有j，1ji，命题成立，即第j层上至多有2 j-1 个结点。由归纳假设第i-

8、1 层上至多有 2i-2个结点。由于二叉树的每个结点的度至多为2，故在第i层上的最大结点数为第i-1层上的最大结点数的2倍，即22i-2=2 i-1。,6.2.2 二叉树的性质,性质2 深度为 k 的二叉树至多有 2 k-1个结点(k 1)。证明：由性质1可见，深度为k的二叉树的最大结点数为,6.2.2 二叉树的性质,性质3 对任何一棵二叉树T，如果其叶结点数为 n0，度为2的结点数为 n2，则n0n21。证明：设二叉树中度为1的结点数为n1，二叉树中总结点数为：nn0n1n2 二叉树中的分支数，除根结点外，其余结点都有一个进入分支，设B为二叉树中的分支总数，则有：nB1。由于这些分支都是由度

9、为1和2的结点射出的，所以有：Bn1+2 n2;nB1n12n21得到：n0n21,6.2.2 二叉树的性质,满二叉树：深度为k的二叉树，有2k-1个结点则称为满二叉树；完全二叉树：如果深度为k、由n个结点的二叉树中个结点能够与深度为k的顺序编号的满二叉树从1到n标号的结点相对应，则称为完全二叉树。完全二叉树的特点是：1.所有的叶结点都出现在第k层或k1层。2.对任一结点，如果其右子树的最大层次为l，则其左子树的最大层次为 l 或 l 1。,两种特殊的二叉树,非完全二叉树,完全二叉树,满二叉树,两种特殊的二叉树,性质 4：具有 n 个结点的完全二叉树的深度为 log2n+1。证明：设完全二叉树

10、的深度为 k，则根据性质2和完全二叉树的定义有2k-1-1 n 2k-1或 2k-1 n 2k取对数 k-1 log2n k，又k是整数，因此有 k=log2n 1,6.2.2 二叉树的性质,性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号(从第1层到第 log2n+1层，每层从左到右)，则对任一结点i(1 i n)，有：1.如果i1，则结点i无双亲，是二叉树的根；如果i1，则其双亲是结点 i/2。2.如果2in，则结点i为叶子结点，无左孩子；否则，其左孩子是结点2i。3.如果2i1n，则结点i无右孩子；否则，其右孩子是结点2i1。,6.2.2 二叉树的性质,证明：此性质可采用数学归纳

11、法证明。因为1与2、3是相对应的，所以只需证明2和3。当 i=1时，根据结点编号方法可知，根的左、右孩子编号分别是2和3，结论成立。假定i-1时结论成立，即结点i-1的左右孩子编号满足：LCHILD(i-1)=2(i-1)；RCHILD(i-1)=2(i-1)+1 通过完全二叉树可知，结点 i 或者与结点i-1同层且紧靠其右，或者结点i-1在某层最右端，而结点i在其下一层最左端。但是，无论如何，结点i的左孩子的编号都是紧接着结点i-1的右孩子的编号，故：LCHILD(i)=RCHILD(i-1)+1=2i；RCHILD(i)=LCHILD(i)+1=2i+1命题成立。,6.2.2 二叉树的性质

12、,Thrt-rchild=pre;一般二叉树也按完全二叉树形式存储，只有增添一些并不存在的空结点(用表示，表示该处没有元素存在，仅仅为了好理解)，使之成为一棵完全二叉树的形式，然后再用一维数组顺序存储。void InThreading(BiThrTree p)InThreading(p-lchild);/左子树线索化取对数 k-1 log2n k，又k是整数，pre(T L);RCHILD(i)=LCHILD(i)+1=2i+1查找任意结点的后继结点查找二叉树某个结点，可通过遍历实现；若树非空，则先访问根结点，然后加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩 子的右孩子，沿分支找到的

13、所有右孩子，都与p 的双亲用线连起来；在F 中删去这两棵树，同时将新得到的二叉树加入 F中。义中又用到了二叉树的概念。struct BiThrNode*lchild,*rchild;/左右指针结点不同构：结点指针个数不等，为该结点的度d。例4 由二叉树先序和中序序列建立一个唯一二叉树遍历结果：BCDAFEHJIG否则，令右指针指示其后继(RTag=1)。树的带权路径长度：树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为,分析：根据完全二叉树的结构和编号规则，在i的左孩子前面的两个结点是结点i-1的左、右孩子，由归纳假设有：结点i-1的左孩子为2(i-1)，右孩子为2(i-1)+1。,

14、.,.,i与i+1同层,.,.,i-1,2(i-1),2(i-1)+1,i,2i,2i+1,.,.,.,.,i与i+1不同层,6.2.2 二叉树的性质,i,2i,2i+1,i-1,2i-2,2i-1,最后证明结论1。当i=1时，显然根结点无双亲；当i1时，结点i可能是其双亲x的左孩子，也可能是右孩子，若是左孩子，由结论2知，x的左孩子应为2x，即2x=i，x=i/2；若是右孩子，由结论3知，x的右孩子应为2x+1，即2x+1=i，x=(i-1)/2。故 i的双亲为i/2 证毕。,6.2.2 二叉树的性质,顺序存储结构 所谓顺序存储结构，就是用一组连续的存储单元存储二叉树的数据元素，结点在这个序

15、列中的相互位置能反映出结点之间的逻辑关系。二叉树中结点之间的关系就是双亲结点与左右孩子结点间的关系。因此，必须把二叉树的所有结点安排成为一个恰当的序列。具体定义如下：#define MAX-TREE-SIZE 100 TElemType SqBiTreeMAX-TREE-SIZE;,6.2.3 二叉树的存储结构,通常是按照二叉树结点从上至下、从左到右的顺序存储，但这样结点在存储位置上的前驱后继关系并不一定就是它们在逻辑上的邻接关系。依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映出结点之间的逻辑关系，这样既能够最大可能地节省存储空间，又可以利用数组元素的

16、下标值确定结点在二叉树中的位置，以及结点之间的关系。,二叉树的顺序存储结构,例如：bt3的双亲为3/2=1，即在bt1中；其左孩子在bt2i=bt6中；其右孩子在bt2i+1=bt7中。,完全二叉树的顺序表示,一般二叉树也按完全二叉树形式存储，只有增添一些并不存在的空结点(用表示，表示该处没有元素存在，仅仅为了好理解)，使之成为一棵完全二叉树的形式，然后再用一维数组顺序存储。,例如对于B结点而言：bt2的双亲为1/2=1，即在bt1中(为A)；其左孩子在bt2i=bt4中(为D)；其右孩子在bt2i+1=bt5中(为)。,一般二叉树的顺序表示,这种存储结构适合于完全二叉树，既不浪费存储空间，又

17、能很快确定结点的存放位置、以及结点的双亲和左右孩子的存放位置，但对一般二叉树，可能造成存储空间的浪费。例如，深度为k，且只有k个结点的右单支树(每个非叶结点只有右孩子)，也需2k-1个单元，即有(2k-1)-k个单元被浪费。,顺序存储的优缺点,所谓链式存储是指，用链表来表示一棵二叉树，即用链来指示着元素的逻辑关系。通常采用二叉链表来存储。链表中每个结点由三个域组成，除了数据域外，还有两个指针域，分别用来给出该结点左右孩子所在的结点的存储地址。其定义如下：typedef struct BiTNode TElemType data;struct BiTNode*lchild,*rchild;BiT

18、Node,*BiTree;,链式存储结构,B,T,lchild,data,rchild,结点结构,二叉链表,A,B,D,G,三叉链表图示,三叉链表,6.3 遍历二叉树和线索二叉树,6.3.1 遍历二叉树定义：所谓遍历二叉树，就是遵从某种次序，访问二叉树中的所有结点，使得每个结点仅被访问一次。这里所提的“访问”的含义很广，可以是查询、修改、输出某元素的值，以及对元素作某种运算等等。但要求这种访问不破坏它原来的数据结构。遍历一个线性结构很简单，只须从开始结点出发，顺序扫描每个结点即可。但对二叉树这样的非线性结构，每个结点可能有两个后继结点，因此需要寻找一种规律来系统访问树中的各结点。,由于二叉树的

19、定义是递归的，它是由三个基本单元组成，即根结点、左子树和右子树。因此，遍历一棵非空二叉树的问题可以分解为三个子问题：访问根结点、遍历左子树、遍历右子树，只要依次遍历这三部分，就可以遍历整个二叉树。由于实际问题一般都是要求左子树较右子树先遍历，分别称为先序遍历、中序遍历和后序遍历。令L，R，D分别代表二叉树的左子树、右子树、根结点，则有DLR、LDR、LRD三种遍历规则。,递归实现方法,若二叉树非空，则：1.访问根结点 2.先序遍历左子树 3.先序遍历右子树,D L R,得到的序列为：A B D C,先序遍历二叉树,Status PreOrderTraverse(BiTree T)/采用二叉链表

20、存贮二叉树 if(T)/若二叉树不为空 Visit(T-data)；/访问根结点 PreOrderTraverse(T-lchild);/先序遍历T的左子树 PreOrderTraverse(T-rchild);/先序遍历T的右子树/PreOrderTraverse,先序遍历二叉树算法实现,viod pre(bint T)if(T)visite(T-data);pre(T-lchild);pre(T-rchild);,先序遍历二叉树算法实现,先序序列：A B D C,若二叉树非空，则：1.中序遍历左子树 2.访问根结点 3.中序遍历右子树,L D R,得到的序列为：B D A C,中序遍历二叉

21、树,若二叉树非空，则：1.后序遍历左子树 2.访问根结点 3.后序遍历右子树,L R D,得到的序列为：D B C A,后序遍历二叉树,这一路线正是从根结点开始沿左子树深入下去，当深入到最左端，无法再深入下去时，则返回，再逐一进入刚才深入时遇到结点的右子树，再进行如此的深入和返回，直到最后从根结点的右子树返回到根结点为止。先序遍历是在深入时遇到结点就访问，中序遍历是在从左子树返回时遇到结点访问，后序遍历是在从右子树返回时遇到结点访问。在这一过程中，返回结点的顺序与深入结点的顺序相反，即后深入先返回，正好符合栈结构后进先出的特点。因此，可以用栈来帮助实现这一遍历路线。,三种遍历过程示意图例,先序

22、遍历：从二叉树根结点开始，沿左子树一直走到末端(左子树为空)为止，在走的过程中，访问所遇结点，并依次把所遇结点进栈，当左子树为空时，从栈顶退出某结点，并将指针指向该结点的右子树。如此重复，直到栈为空或指针为空止。中序遍历：从二叉树根结点开始，沿左子树一直走到末端(左子树为空)为止，在走的过程中，把依次遇到的结点进栈，待左子树为空时，从栈中退出结点并访问，然后再转向它的右子树。如此重复，直到栈空或指针为空止。,非递归实现方法,status InOrderTraverse(BiTree T)InitStack(S);Push(S,T);/根结点进栈 while(!StackEmpty(S)whil

23、e(GetTop(S,p),中序遍历的非递归算法,中序遍历的非递归算法演示,中序遍历的非递归算法演示,void InThreading(BiThrTree p)int n;/结点数if(T-lchild=NULLif(!StackEmpty(S)多重链表：每个结点有多个指针域，分别指向其子树的根。,中序遍历的非递归算法演示,中序遍历的非递归算法演示,中序遍历的非递归算法演示,中序遍历的非递归算法演示,中序遍历的非递归算法演示,中序遍历的非递归算法演示,后序遍历：利用栈来实现二叉树的后序遍历要比先序和中序遍历复杂得多，在后序遍历中，当搜索指针指向某一个结点时，不能马上进行访问，而先要遍历左子树，

24、所以此结点应先进栈保存，当遍历完它的左子树后，再次回到该结点，还不能访问它，还需先遍历其右子树，所以该结点还必须再次进栈，只有等它的右子树遍历完后，再次退栈时，才能访问该结点。为了区分同一结点的两次进栈，引入一个栈次数的标志，元素第一次进栈标志为1，第二次进标志为2，当退出的元素标志为2时，访问结点。,非递归实现方法,void leaf(BiTree T)/采用二叉链表存贮二叉树，n为全局变量，用于累加二叉树的叶子结点个数，本算法在先序遍历二叉树的过程中，统计叶子结点的个数，初始化n=0if(T)if(T-lchild=NULL/if/leaf,例1 编写求二叉树的叶子结点个数的算法,void

25、 leaf(BiTree T)If(T)if(T-lchild=NULL/PreOrderTraverse,访问结点时统计叶子结点的个数,访问结点时调用visit(),比较先序遍历和计算叶子结点算法相同点和不同点,分析：本算法要借用队列来完成，其基本思想是，若二叉树非空，先将根结点进队列。然后进入循环：只要队列不空，就出队列，遍历该结点，然后判断出队列的结点是否有左孩子和右孩子，如有就让左、右孩子进队列。,例2 按层次遍历二叉树的算法,void layorder(BiTree T)InitQueue(Q)/队列初始化 if(T!=NULL)EnQueue(Q,T);/入队列 while(not

26、 QueueEmpty(Q)/若队列非空 DeQueue(Q,p);/出队 visite(p-data);if(p-lchild!=NULL)EnQueue(Q,p-lchild);/入队列 if(p-rchild!=NULL)EnQueue(Q,p-rchild);/入队列,例2 按层次遍历二叉树的算法,输入：二叉树的先序序列结果：二叉树的二叉链表问题：遍历操作访问二叉树的每个结点，而且每个结点仅被访问一次。是否可利用遍历，建立二叉链表的所有结点并完成相应结点的链接？基本思想：输入在空子树处添加字符的二叉树的按先序遍历的顺序，建立二叉链表的所有结点并完成相应结点链接。,在空子树处添加的二叉树

27、的先序序列：A B D F E C,例3 建立二叉链表,Status CreateBiTree(BiTree/CreateBiTree,建立二叉链表算法,建立二叉链表算法,A B C D,A,B,C,D,A,T,B,C,D,分析：由先序序列和中序序列的定义可知，先序序列中第一个结点必为根结点，而在中序序列中，根结点刚好是左、右子树的分界点，因此，可按如下方法建立二叉树：1.用先序序列的第一个结点作为根结点;2.在中序序列中查找根结点的位置，并以此为界将中序序列划分为左、右两个序列(左、右子树);3.根据左、右子树的中序序列中的结点个数，将先序序列去掉根结点后的序列划分为左、右两个序列，它们分别

28、是左、右子树的先序序列;4.对左、右子树的先序序列和中序序列递归地实施同样方法，直到所得左、右子树为空。,例4 由二叉树先序和中序序列建立一个唯一二叉树,如一棵二叉树的先序序列为ABDGHCEFI，中序序列为GDHBAECIF，试建立该二叉树。构造过程：由先序可知A为根结点，再根据中序序列知：由GDHB是左子树，ECIF是右子树。A为根结点A BDGH CEFIGDHB A ECIF B为左子树的根结点B DGHGDH B 一直进行下去,示例分析,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,先序序列

29、中序序列,遍历是二叉树最基本最常用的操作。1.对二叉树所有结点做某种处理可在遍历过程中实现；2.查找二叉树某个结点，可通过遍历实现；与线性表相比，对二叉树的遍历存在如下问题：1.遍历算法要复杂的多，费时的多；2.为查找二叉树中某结点在某种遍历下的后继，必须从根开始遍历，直到找到该结点及后继；如果能将二叉树线性化，就可以减化遍历算法，提高遍历速度。,6.3.2 线索二叉树,定义：当以二叉链表作为存储结构时，只能找到结点的左右孩子的信息，而不能直接得到结点的任一序列的前驱与后继信息，这种信息只有在遍历的动态过程中才能得到，为了能保存所需的信息，可增加标志域。0 lchild 域指示结点的左孩子 1

30、 lchild 域指示结点的前驱 0 rchild 域指示结点的右孩子 1 rchild 域指示结点的后继 以这种结构构成的二叉链表作为二叉树的存储结构，叫做线索链表，其中指向结点前驱与后继的指针叫做线索。加上线索的二叉树称之为线索二叉树。,一、线索二叉树定义,利用现有的空指针域，每个n个结点的二叉链表，有n+1个空指针域，故可利用这些的空指针域存放结点的前趋和后继指针。(n个结点共有2n个链域，而每个结点(除根结点外)都有一个分支指向，则共有n-1个分支，其中每个分支占有一个链域，所以空链域为2n-(n-1)=n+1。)若结点有左子树，则左指针lchild指示其左孩子(LTag=0)；否则，

31、令左指针指示其前驱(LTag=1)；若结点有右子树，则右指针rchild指示其右孩子(RTag=0)；否则，令右指针指示其后继(RTag=1)。,二、如何保存遍历过程中得到的信息？,typedef enum PointerTeg Link,Thread;/Link=0:指针，Thread=1:线索typedef struct BiThrNod TElemType data;struct BiThrNode*lchild,*rchild;/左右指针 PointerTeg LTag,RTag;/左右标志 BiThrNode,*BiThrTree;,三、线索链表的类型描述,(以中序遍历为例)查找任意

32、结点的前驱结点 如果该结点的左标志为1，那么其左指针域所指向的结点便是它的前驱结点；如果该结点的左标志为0，表明该结点有左孩子，根据中序遍历的定义，它的前驱结点是以该结点的左孩子为根结点的子树的最右结点，即沿着其左子树的右指针链向下查找，当某结点的右标志为1时，它就是所要找的前驱结点。,中序线索二叉树中序：DBGJEACHLKFI,四、如何找结点的前驱和后继,中序线索二叉树中序：DBGJEACHLKFI,四、如何找结点的前驱和后继(续),(以中序遍历为例)查找任意结点的后继结点 对任意结点p，若右标志为1，则rchild指向该结点的后继；若右标志为0，则rchild指向该结点的右孩子，此时，应

33、从右孩子开始，沿左指针前进，直到找到没有左孩子的结点s(Ltag=1)，则s就是p的后继，即后继是中序遍历右子树时，访问的第一个结点。,按不同的方式遍历二叉树所得到的线索二叉树是不相同的。,五、遍历线索二叉树,五、遍历线索二叉树(续),带头结点的线索二叉树 在存储线索二叉树时往往增设一头结点，其数据域不存放信息，其左指针域指向二叉树的根结点，右指针域指向某种遍历时访问的最后一个结点。而原二叉树在某序遍历下的第一个结点的前驱线索和最后一个结点的后继线索都指向该头结点。注：可从第一个结点起顺后继进行遍历，也可以从最后一个结点起顺前驱进行遍历。,找遍历的第一个结点 左子树上处于“最左下”(没有左子树

34、)的结点。不断地找遍历到的结点的后继结点，直到树中各结点都遍历到为止，结束 若无右子树，则为后继线索所指结点；否则为对其右子树进行中序遍历时访问的第一个结点。,遍历线索二叉树步骤(以中序遍历为例),void InOrderTraverse_Thr(BiThrTree T)p=T-lchild;while(p!=T)while(p-LTag=0)p=p-lchild;Visit(p-data);while(p-RTag=1/InOrderTraverse_Thr,中序线索二叉树中序：DBGJEACHLKFI,中序遍历线索二叉树算法实现,建立线索二叉树，或者说对二叉树线索化，实质上是遍历一棵二叉树

35、。在遍历过程中访问结点操作visit()是检查当前结点的左、右指针域是否为空，如果为空，将空的lchild改为结点的直接前驱，将空的rchild改为结点的直接后继。而对于非空指针，仍然指向孩子结点。为了记下遍历过程中访问结点的先后关系，附设指针pre始终指向刚刚被访问过的结点,若p指针指向当前访问的结点，则pre指向它的前驱。,六、如何建立线索二叉树？,Status InOrderThreading(BiThrTree/InOrderThreading,算法实现(1)：,void leaf(BiTree T)if(T)leaf(T-lchild);if(T-lchild=NULL,算法实现(2

36、)：,void InThreading(BiThrTree p)if(p)InThreading(p-lchild);/左子树线索化 if(!p-lchild)/建前驱线索 p-LTag=1;p-lchild=pre;if(!pre-rchild)/建后继线索 pre-RTag=1;pre-rchild=p;pre=p;/保持 pre 指向 p 的前驱 InThreading(p-rchild);/右子树线索化/if/InThreading,相当于遍历算法中的visit(),算法实现(2)：,6.4.1 树的存贮结构一、双亲表示法：以一组连续的空间存储树的结点，通过保存每个结点的双亲结点的位置

37、，表示树中结点之间的结构关系。其类型定义如下：#define MAX_TREEE_SIZE 100typedef struct PTNode ElemType data;int parent;/双亲位置域 PTNode;typedef struct PTNode nodesMAX_TREE_SIZE;int n;/结点数 Ptree;特点：找双亲容易，找孩子难,6.4 树和森林,通过保存每个结点的孩子结点的位置，表示树中结点之间的结构关系。多重链表：每个结点有多个指针域，分别指向其子树的根。结点同构：结点的指针个数相等，为树的度d。结点不同构：结点指针个数不等，为该结点的度d。,data,ch

38、ild1,child2,childd,data,degree,child1,child2,childd,二、孩子表示法,孩子链表：其主体是一个与结点个数一样大小的一维数组，数组的每一个元素有两个域组成，一个域用来存放结点信息，另一个用来存放指针，该指针指向由该结点孩子组成的单链表的首位置。单链表的结构也由两个域组成，一个存放孩子结点在一维数组中的序号，另一个是指针域，指向下一个孩子。每个结点的孩子结点用单链表存储，再用含n个元素的结构数组指向每个孩子链表。,二、孩子表示法,0123456789,数组下标,特点：找孩子容易，找双亲难,孩子链表表示法图示,typedef struct CTNode

39、/孩子结点 int child;struct CTNode*next;*ChildPtr;typedef struct ElemType data;ChildPtr firstchild;/孩子链表头指针 CTBox;typedef struct CTBox nodesMAX_TREE_SIZE;int n,r;/结点数和根的位置CTree;,孩子链表表示法类型定义,用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点。特点：操作容易，但破坏了树的层次。孩子兄弟表示法类型定义：typedef struct CSNode ElemType data;str

40、uct CSNode*firstchild,*nextsibling;CSNode,*CSTree;,三、孩子兄弟表示法,利用树的孩子兄弟链表这种存储结构便于实现各种树的操作。例如找某结点的第i个孩子，则只要先从左指针域中找到第1个孩子结点上，然后沿着孩子结点的next域连续走i-1步便可找到第i个孩子。如增加一个parent域，则也能方便实现求双亲的操作。,三、孩子兄弟表示法,一.树转变为二叉树 加线：在兄弟之间加一连线；抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系；旋转：以树的根结点为轴心，将整树顺时针转45。,6.4.2 树、森林与二叉树转换,由上面的转换可以看出，在二叉

41、树中，左分支上的各结点在原来的树中是父子关系，而右分支上的各结点在原来的树中是兄弟关系。由于树的根结点没有兄弟，所以变换后的二叉树的根结点的右孩子必为空。,树转变为二叉树实现过程,由森林的概念可知，森林是若干棵树的集合，只要将森林中各棵树的根视为兄弟，每棵树又可以用二叉树表示，这样，森林也同样可以用二叉树表示。具体的方法如下：将各棵树分别转换成二叉树；将每棵树的根结点用线相连；以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构。,二、森林转换成二叉树,森林转变为二叉树实现过程,加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩 子的右孩子，沿分支找到的所有右孩子，

42、都与p 的双亲用线连起来；抹线：抹掉原二叉树中双亲与右孩子之间的连线；调整：将结点按层次排列，形成树结构。,注：该二叉树的右子树为空,三、二叉树转换成树,抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树。还原：将孤立的二叉树还原成树。,注：该二叉树的右子树一定不为空,四、二叉树转换成森林,在树和森林中，一个结点可能有两棵以上的子树，所以不宜讨论它们的中序遍历，即树和森林只有先序遍历和后序遍历。1.树的先序遍历若树非空，则先访问根结点，然后依次先序遍历各子树。,2.树的后序遍历若树非空，则依次后序遍历各子树，最后访问根结点。,6.4.3 树和

43、森林的遍历,3.森林的先序遍历若森林非空，则先访问森林中第一棵树的根结点，再先序遍历第一棵树各子树，接着先序遍历第二棵树、第三棵树、直到最后一棵树。遍历结果：ABCDEFGHIJ,4.森林的后序遍历按顺序后序遍历森林中的每一棵树。遍历结果：BCDAFEHJIG,6.4.3 树和森林的遍历,一、基本概念 路径和路径长度：在一棵树中，从一个结点往下可以达到的孩子或子孙结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。结点的权及带权路径长度：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。从根结点到该结点之间的

44、路径长度与该结点的权的乘积称为结点的带权路径长度。,6.6 赫夫曼树及其应用,一、基本概念(续)树的带权路径长度：树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为其中n 为叶子结点数目，wi为第i 个叶子结点的权值，li 为第i 个叶子结点的路径长度。赫夫曼树：在一棵二叉树中，若树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为赫夫曼树。,6.6 赫夫曼树及其应用,例 有4个结点，权值分别为7，5，2，4，构造有4个叶子结点的二叉树。,WPL=7*2+5*2+2*2+4*2=36,WPL=7*3+5*3+2*1+4*2=46,WPL=7*1+5*2+2*3+4*3=35,例

45、 编制一个将百分制转成五级分制的程序。,二、赫夫曼树的应用,不及格,及格,中,良,优,60?,70?,80?,90?,0.10,0.15,0.25,0.35,0.15,N,N,N,N,Y,Y,Y,Y,WPL=0.10*1+0.15*2+0.25*3+0.35*4+0.15*4=3.15,流程图1：,0.10,0.15,0.25,0.35,0.15,不及格,及格,中,良,优,60?,70?,80?,90?,0.10,0.15,0.25,0.35,0.15,N,N,N,N,Y,Y,Y,Y,WPL=0.10*3+0.15*3+0.25*2+0.35*2+0.15*2=2.25,流程图2：,步骤如下：

46、1.由给定的 n 个权值w1,w2,wn构成n棵二叉树的集合(即森林)F=T1,T2,Tn，其中每棵二叉树 Ti 中只有一个带权为 wi 的根结点，其左右子树均空。2.在F 中选取两棵根结点的权值最小的树做为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。3.在F 中删去这两棵树，同时将新得到的二叉树加入 F中。4.重复2和3，直到 F 只含一棵树为止。这棵树便是赫夫曼树。,三、构造Huffman树的方法,例 w=5,29,7,8,14,23,3,11,例 w=5,29,7,8,14,23,3,11,通信中，可以采用0、1的不同排列来表示不同的字符，称为

47、二进制编码。若每个字符出现的频率不同，可以采用不等长的二进编码，频率较大的采用位数较少的编码，频率较小的字符采用位数较多的编码，这样可以使字符的整体编码长度最小，这就是最小冗余编码的问题。而赫夫曼编码就是一种不等长的二进制编码，且赫夫曼树是一种最优二叉树，它的编码也是一种最优编码。,6.6.2 赫夫曼树编码,设需要编码的字符集合为D=d1，d2，dn，它们在电文中出现的次数或频率集合为w1，w2，wn，以d1，d2，dn作为叶结点，w1，w2，wn作为它们的权值，构造一棵赫夫曼树，规定赫夫曼树中的左分支代表0，右分支代表1，则从根结点到每个叶结点所经过的路径分支组成的0和1的序列便为该结点对应字符的编码，我们称之为赫夫曼编码。,编码方法,例 要传输的字符集 D=C，A，S，T，;，字符出现频率 w=2，4，2，3，3。,每个字符的编码分别为：C：110A：10S：111T：00;：01,如果设计出的A、B、C、D的编码分别是0、00、1和01，假设有一电文为000011010，它译出的电文是怎样的？,在建立不等长编码时，必须使任何一个字符的编码都不是另一个字符编码的前缀，这样才能保证译码的唯一性。在赫夫曼树中，每个字符结点都是叶结点，它们不可能在根结点到其它字符结点的路径上，所以一个字符的赫夫曼编码不可能是另一个字符的赫夫曼编码的前缀，从而保证了译码的非二义性。,存在问题,