文档2.5树与二叉树

2.5树与二叉树树型结构是一类很重要的非线性数据结构，在这类结构中，元素结点之间存在明显的分支和层次关系。2.5.1树的定义及其存储结构树的定义和术语树是由n个(n≥0)结点组成的有限集合T，其中有且仅有一个结点称为根结点(root)，其余结点可以分为m(m≥0)个互不相交的有限集合T1，T2，…，Tm,其中每个集合Ti本身又是一棵树，称为根结点root的子树。当n=0时称为空树。这是一个递归的描述，即在买偶数树时又用到树本身这个术语。图2.33所示为一棵树，A为根结点，期于结点分为三个不相交的子集T1，T2，T3，它们均为根结点A下的三棵树，而这三棵树本身也是树。用二元组关系来定义树为Tree=(T,R)数据结构树(Tree)由数据元素集合T及各种R组成，其中T是具有相同类型的数据元素集合T={x1，x2，…，xn}。若T为空集(T=Ø),则R=Ø，称为空树，否则R是T上某个二元关系H的集合，即R={H}。H的描述如下：(1)在T中存在唯一的称为根的元素root，它在H关系下无前趋。(2)若T-{root}≠Ø，则存在m个子集T1，T2，…，Tm(m>0),对任意的j≠k(1≤j,k≤m)，有Tj∩Tk=Ø，则存在唯一的数据元素xi∈Ti(1≤i≤m)，满足<root,xi>∈H。(3)对应于T1，T2，…，Tm，H-{<root，x1>，…，<root，xm>}，满足<root，xi>∈H1，H2，…，Hm(m>0)，对任意的j≠k(1≤j,k≤m)有Hj∩Hk=Ø，Hj满足在Ti上的二元关系。因此(Ti，{Hi})也是一棵符合本定义的树，称为根root的子树。树结构中常用的术语有.结点(node):表示树中的元素。.结点的度(degree)：结点拥有的子树数，如图2.33中结点A的度为3，C的度为1。一棵树中最大的结点度数为这棵数的度，图2.33中树的度为3。.叶子(leaf):度为零的结点，又称为端结点。.孩子(child)：除根结点外，每个结点都是其前趋结点的孩子。.双亲(parents)：对应上述孩子结点的上层结点称为这些结点的双亲。例如图2.33中，D是A的孩子，A是D，C，B的双亲。.兄弟(sibling):同一双亲的孩子。.结点的层次(level)：从根结点开始算起，根为第一层，根的直接后继结点为第二层，其余个层次依次类推。例如图2.33中共分为4层。.深度(depth)：树中结点的最大层次数。图2.33中树的深度为4。.森林(forest)：是m(m≥0)棵互不相交的树的集合。.有序树：树中结点在同层中按从左至右有序排列、不能互换的称为有序树，反之称为无序树。树的存储结构仅讨论链式存储结构。异构型：节省存储空间，运算不便。同构型：运算方便，浪费空间。假设有一棵具有n个结点的k叉树，则有nk个指针域，其中有用的指针域为n-1个，因此空链域个数为nk-(n-1)=n(k-1)+1个。不同的k值进行比较:完全二叉树如果一棵n个结点的二叉树，按与满二叉树相同的编号方式对结点进行编号，若树中n个结点和满二叉树1～n编号完全一致，则称该树为完全二叉树，如图2.37(a)所示；而图2.37(b)就不是完全二叉树。平衡二叉树平衡二叉树或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。图2.38(a)为平衡二叉树，(b)为不平衡二叉树。一般树转换为二叉树在兄弟结点之间加一连线；对每个结点，除了与它的第一个孩子保持联系外，去除与其它孩子的联系；以树根为轴心，将整棵树顺时针旋转45°。2.5.3二叉树的遍历遍历是指遵循某条搜索路线，依次访问某数据结构中的全部结点，而且每个结点只被访问一次。遍历二叉树的定义DLR，LDR，LRD，DRL，RDL，RLD六种遍历形式。若规定先左后右，则归并成下述三种形式：DLR：先序遍历LDR：中序遍历LRD：后序遍历以图2.40中的二叉树为例，三种遍历结果为：先序：ABCDEFG中序：CBDAEGF后序：CDBGFEA遍历算法PROORDER(p)//先序遍历//1.if(p<>nil)then2.{whrit(data(p));//访问根结点//3.PROORDER(Lchild(p));//遍历左子树//4.PROORDER(Rchild(p));//遍历右子树//5.returnBRBRARARARARARERFRABCDEFGINORDER(p)//中序遍历//1.if(p<>nil)then2.{INORDER(L,child(p));//遍历左子树//3.while(data(p));//访问根结点//4.INORDER(R,child(p));//遍历右子树//5．ReturnBRBRARARARARARERFRCBDAEGFPOSTORDER(p)//后序遍历//1.if(p<>nil)then2.{POSTORDER(L,child(p));//遍历左子树//3.POSTORDER(R,child(p));//遍历右子树//4.while(data(p));//访问根结点//5．ReturnCOUNTLEFT(p,count)//p指向根结点,count为计数器，初值为01.if(p<>nil)then2.{if(Lchild(p))=nil}and(Rchild=nil)3.thencount←count+14.COUNTLEFT(L,child(p));5.COUNTLEFT(R,child(p));6.return4二叉树的应用二叉排序树(1)定义二叉排序树或是空树，或是具有下述性质的二叉树：其左子树上所有结点的数据均小于根结点的数据值；右子树上所有结点的数据值均大于或等于根结点的数据值。左子树和右子树又各是一棵二叉排序树。图2.41所示就是一棵二叉排序树。在二叉排序树中，若按中序遍历就可以得到由小到大的有序序列，如图2.41中的二叉排序树，中序遍历可得到有序序列{2,3,4,8,9,9,10,13,15,18,21}。(2)二叉排序树的生成二叉排序树是一种动态表结构，即二叉排序树的生成过程是不断地向二叉排序树中插入新的结点。对任意的一组数据元素序列{R1，R2，…，Rn}，要生成一棵二叉排序树的过程为：<1>令R1为二叉排序树的根结点。<2>若R2<R1，令R2为R1的左子树的根结点；否则R2为R1的右子树的根结点。<3>R3，…，Rn结点的插入方法同上。二叉排序树插入算法如下：INSERBET(t,b)//将数值b插入根结点指针为t的二叉排序树中,此函数返回值为指向根结点t的指针//1.if(t=nil)then//生成一个新结点,其数值域为b//2.{GETNODE(t);data(t)←;Lchild(t)←nil;Rchild(t)←nil}3.elseif(b<data(t)then{Lchild(t)←INSERTBET(Lchild(t),b)}//插入左子树//5.else6.{Rchild(t)←INSERTBET(Rchild(t),b)}//插入右子树//7.return(t)图2.42所示为序列{10，18，3，8，12，2，7，3}构成一棵二叉排序树的过程。(3)删除二叉排序树上的结点删除二叉排序树上的一个结点，也就是要在已排好序的序列中删除一个元素，因此要求删除一个结点后二叉树仍然是一棵二叉排序树。删除二叉排序树上结点过程较插入过程复杂，按照被删除结点在二叉排序树中的位置，可以有以下几种情况：<1>被删除结点是叶子结点，则删除后不会影响整个二叉排序树的结构，因此只需修改它双亲结点的指针即可。<2>被删除结点P只有左子树PL或右子树PR，此时只要将左子树或右子树直接成为其双亲结点F的左或右子树即可，见图2.43(a)所示。<3>若被删除结点P的左右子树均为非空。这是要循着P的左子树的根结点C，向右一直找到结点S，要求S的右子树为空。然后将S的左子树改为结点Q的右子树，将S结点的数据域值取代P结点的数据域值，删除前后如图2.43(b)(c)所示。<4>若被删除的结点为二叉排序树的根结点，则删除后应修改根结点指针。算法如下：DELNODE(t,p,f)//t为根结点指针,p指向被删除结点,f指向其双亲,当p=t时f=nil//1.fag←0//fag=0需要修改F结点指针,fag=1不需修改//2.if(Lchild(p)=nil)thens←Rchild(p)//p为叶子或左子树为空//3.elseif(Rchild(p)=nil)thens←Lchild(p)//p的右子树为空//4.else{q←p;s←Lchild(p)//p的左右子树均为空//5.while(Rchild(s)<>nil)do6.{q←s;s←Rchild(p)}寻找s结点//7.if(q=p)thenLchild(q)←Lchild(s)elseRchild(q)←Lchild(s).data(p)←datea(s)//s值代替p值//10.RET(s);fag←1//释放s结点//}11.if(fag=0)then//修改F结点指针//{if(f=nil)thent←s//被删除结点为根结点//13.elseif(Lchild(f)=p)thenLchild(f)←s14.elseRchild(f)←s15.RET(p)//释放结点p//16.return哈夫曼树哈夫曼树又称最优树，是一类带权路径最短的树。(1)树的路径长度从树中一个结点到另一个结点之间的分支数目称为这对结点之间的路径长度。树的路径长度是从树根到每个结点的路径长度之和。路径长度用PL表示，图2.44中(a)(b)两棵树的路径长度分别为：PL=0+1+2+2+3+4+5=17；PL=0+1+1+2×4+3=13。在任何二叉树中，都存在如下情况：路径为0的结点至多只有1个；路径为1的结点至多只有2个；……路径为k的结点至多只有2k个。因此，n个结点的二叉树路径长度满足log21+log22+log23+log214+log215+log216+log217+log28+…………=0+1+1+2+2+2+2+3+…………从上述关系可知，具有最小路径长度的二叉树为完全二叉树。(2)树的带权路径长度结点带权路径长度为该结点到树根之间的路径长度与结点上权值的乘积。树的带权路径长度为树中叶子结点的带权路径长度之和，记作其中wk为树中每个叶子结点的权值，lk为每个叶子结点到根结点的路径长度。WPL最小的二叉树称作最优二叉树或哈夫曼树。例如图2.45中的三棵二叉树，都有4个叶子结点a，b，c，d，分别具有权值7，5，2，4，它们带权路径长度分别为：(a)WPL=7*2+5*2+2*2+4*2=36(b)WPL=7*3+5*3+2*1+4*2=46(c)WPL=7*1+5*2+2*3+4*3=35其中以(c)为最小，可以验证(c)为哈夫曼树。(3)哈夫曼树的构造原则：权值越大的叶子离根结点的距离越近。<1>由给定的n个权值{w1，w2，…，wn}构成n棵二叉树的集合F={T1，T2，…，Tn}，其中每棵二叉树只有一个权值为wi的根结点，如图2.46(a)所示。<2>在F中选取两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和，如图2.46(b)所示。<3>将新的二叉树假如F中，去除原两棵根结点权值最小的树。<4>重复<2>,<3>两步骤，直到F中只含一棵树为止。这棵树就是哈夫曼树，如图2.46(d)所示。在计算机上实现上述算法，首先要确定存储结构，由于哈夫曼树中没有度为1的结点，因此一棵有n个叶子结点的哈夫曼树共有2n-1个结点。结点采用数组型链表结构每个结点由4个数据域组成，即date:存放结点权值Lchild:左指针Rchild:右指针Prnt:双亲指针算法如下：HUFFMAN(n,Lchild,Rchild,data,Prnt,w)//w[1:n]存放n个权值,Lchild[1:m],Rchild[1:m],data[1:m],Prnt[1:m],m=2n-1//1.fori=1tondata[i]←w[i];Lchild(i)←0;Rchild(i)←0//初始化//3.end(i)4.fori=1to(2*n-1)Prnt[i]←0//初始化//5.end(i)6．fork