chap6-1树与二叉树

数据结构（C）愿大家开心学习、学习开心！数字媒体技术教研室乐小燕1第6章树和二叉树第6章主要内容2数字媒体技术教研室乐小燕•树和二叉树的概念及特点•二叉树的存储表示•二叉树的遍历•树与森林•树、森林与二叉树的转换•Huffman树6.1树的定义和基本术语一、树的定义树(tree)是n(n=0)个结点的有限集。当n0时(非空树中),(1)有且仅有一个特定的称为根(root)的结点;(2)当n1时,其余结点可分为m(m0)个互不相交的有限集T1,T2,...,Tm,其中每个集合本身又是一棵树。称为根的子树(subtree)。数字媒体技术教研室乐小燕34r是一个特定的称为根(root)的结点，它只有直接后继，但没有直接前驱；根以外的其他结点划分为m(m0)个互不相交的有限集合T1,T2,…,Tm，每个集合又是一棵树，并且称之为根的子树。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。00n,T,...,T,Tr,n,Tm21}{Φ树的定义是采用递归方法5一、树的定义ACBGFEHIJDMKLA树是n个结点的有限集T1T2T3递归定义树的性质：递归性，层次性。特点：树中至少有一个结点----根f树中各子树是互不相交的集合。(a)一棵树结构(b)一个非树结构(c)一个非树结构一、树的定义ACBGFEDHIACBGFDACBGFDEA（B（D，E（H，I），F），C（G））7树的表示方式ACBGFEHIJDMKLAJIMHDGCFLKEB凹入表示ABFEKLGCDHMIJ嵌套集合(A(B(E(K,L),F),C(G),D(H(M),I,J)))括号表示法树的应用举例——文件结构MyComputerC:D:E:etcWINDOWSProgramFilesPictureMusic…………………………………………结点的度：结点所拥有的子树的棵数。树的度：树中各结点度的最大值。CGBDEFKLHMIJA二、树的基本术语叶子结点：度为0的结点，也称为终端结点。分支结点：度不为0的结点，也称为非终端结点。CGBDEFKLHMIJA二、树的基本术语孩子、双亲：树中某结点子树的根结点称为这个结点的孩子结点，这个结点称为它孩子结点的双亲结点；兄弟结点：具有同一个双亲的孩子结点互称为兄弟。CGBDEFKLHMIJA二、树的基本术语祖先、子孙：在树中，如果有一条路径从结点x到结点y，那么x就称为y的祖先，而y称为x的子孙。CGBDEFKLHMIJA二、树的基本术语路径：如果树的结点序列n1,n2,…,nk有如下关系：结点ni是ni+1的双亲（1=ik），则把n1,n2,…,nk称为一条由n1至nk的路径；路径上经过的边的个数称为路径长度。CGBDEFKLHMIJA二、树的基本术语结点所在层数：也称结点的层次，即从根到该结点所经路径上的分支数。如：根结点的层数为1；其余任何结点，若某结点在第k层，则其孩子结点在第k+1层。1层2层4层3层CGBDEFKLHMIJA二、树的基本术语树的深度：树中距离根结点最远的结点所处的层次即为树的深度。空树的深度为0。树的高度：从下往上定义。叶结点的高度为1，非叶结点的高度=它的子女结点高度的最大值+11层2层4层3层深度=高度＝4CGBDEFKLHMIJA二、树的基本术语CBDEFKLHJA71234568910层序编号：将树中结点按照从上层到下层、同层从左到右的次序依次给他们编以从1开始的连续自然数。二、树的基本术语有序树、无序树：如果一棵树中结点的各子树从左到右是有次序的，称这棵树为有序树；反之，称为无序树。数据结构中讨论的一般都是有序树ACBGFEDACBGFED二、树的基本术语CBDEFKLHJ森林：m(m≥0)棵互不相交的树的集合。A二、树的基本术语同构：对两棵树，若通过对结点适当地重命名，就可以使这两棵树完全相等（结点对应相等，结点对应关系也相等），则称这两棵树同构。ACBGFEDDAECFBG二、树的基本术语二、树的基本术语数字媒体技术教研室乐小燕201层2层4层3层depth=4DACBIJHGFEMLKheight=421例题：已知一棵树边的集合为{B,E,B,F,C,G,D,H,D,I,D,J,F,K,F,L,J,M,A,B,A,C,A,D},画出这棵树，并回答下列问题：1、根结点、叶子结点？2、结点F的双亲、祖先、孩子？3、B的子孙、B的兄弟、F的兄弟？4、结点J和M的层次号？5、树的深度、度数，以结点D为根的子树的深度？ABCDEFGHIJMKL23性质1：树中的结点数等于所有结点的度数加1。三、树的性质ABCDEFGHIJMKL24性质2：度为m的树中第i层上至多有mi-1个结点，这里应有i≥1。证明(采用数学归纳法)AB1BjBmB1C1B1CmBjC1BjCmBmC1BmCmE1D1Dm……………………………………Em…………mmmmmm三、树的性质25性质3：高度为h的m次树至多有个结点。证明：由树的性质2可知,第i层上最多结点数为mi-1(i=1,2,…,h),显然当高度为h的m次树(即度为m的树)上每一层都达到最多结点数时,整个m次树具有最多结点数,因此有：整个树的最多结点数=每一层最多结点数之和=m0+m1+m2+…+mh-1=。11mmh11mmh(等比数列求和公式)三、树的性质26性质4：具有n个结点的m次树的最小高度为logm(n(m-1)+1)证明：设具有n个结点的m次树的高度为h,若在该树中前h-1层都是满的,即每一层的结点数都等于mi-1个(1≤i≤h-1),第h层(即最后一层)的结点数可能满,也可能不满,则该树具有最小的高度。其高度h可计算如下：根据树的性质3可得：＜n≤乘(m-1)后得：mh-1＜n(m-1)+1≤mh以m为底取对数后得：h-1＜logm(n(m-1)+1)≤h即logm(n(m-1)+1)≤h＜logm(n(m-1)+1)+1因h只能取整数,所以h=logm(n(m-1)+1)结论得证。111mmh11mmhlogm(n(m-1))+1logm(n(m-1))+1或或27根据树的性质3可得：＜n≤111mmh11mmh乘(m-1)后得：以m为底取对数后得：即因h只能取整数,所以:h-1≤logm(n(m-1))＜hmh-1-1＜n(m-1)≤mh-1mh-1≤n(m-1)＜mhh=logm(n(m-1))+1=logm(n(m-1))＜h≤logm(n(m-1))+1logm(n(m-1))+1或结论得证。28例1:含10个结点的三次树的最小高度是多少？例2:含14个结点的三次树的最小高度是多少？34三、树的性质29四、树的抽象数据类型数据对象D:ADTTree{D是具有相同特性的数据元素的结合数据关系R:略！基本操作:(1)InitTree(&T)(2)DestroyTree(&T)(3)CreateTree(&T,definition);(4)ClearTree(&T)(5)TreeEmpty(T)30(6)TreeDepth(T);(7)Root(T);(8)Value(T,cur_e);(9)Assign(T,cur_e,value);(10)Parent(T,cur_e);(11)LeftChild(T,cur_e);(12)RightSibling(T,cur_e);(13)InsertChild(&T,&p,i,c);(14)DeleteChild(&T,&p,i);(15)TraverseTree(T,visit())}ADTTree;线性结构树结构第一个数据元素根结点（只有一个）无前驱无双亲最后一个数据元素叶子结点(可以有多个)无后继无孩子其它数据元素其它结点一个前驱,一个后继一个双亲,多个孩子一对一一对多五、树结构和线性结构的比较数字媒体技术教研室乐小燕32一、二叉树的定义•一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。•每个结点最多有两个子女，分别称为左子女和右子女。•二叉树中不存在度大于2的结点。•二叉树的子树有左、右之分，子树的次序不能颠倒。6.2二叉树一、二叉树的定义二叉树是分支数最大不超过2的有根有序树。数字媒体技术教研室乐小燕33二叉树的五种不同形态LLRR34思考题：高度为k的2叉树至多有多少个结点？此情况下树的形状是什么样的？试画出来。k=1，2，3，4……..35•定义1满二叉树(FullBinaryTree)•定义2完全二叉树(CompleteBinaryTree)两种特殊二叉树在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上。满二叉树的特点：1.叶子只能出现在最下一层；2.只有度为0和度为2的结点。A15234678910BCDEFGHIJKLMNO1112131415特殊二叉树——满二叉树不是满二叉树，虽然所有分支结点都有左右子树，但叶子不在同一层上。满二叉树在同样深度的二叉树中结点个数最多满二叉树在同样深度的二叉树中叶子结点个数最多A1523467BCDEFGLM89特殊二叉树——满二叉树对一棵具有n个结点的二叉树按层序编号，如果编号为i（1≤i≤n）的结点与同样深度的满二叉树中编号为i的结点在二叉树中的位置完全相同。A15234678910BCDEFGHIJKLMNO1112131415A15234678910BCDEFGHIJ特殊二叉树——完全二叉树若设二叉树的深度为k，则共有k层。除第k层外，其它各层(1～k-1)的结点数都达到最大个数，第k层从右向左连续缺若干结点，这就是完全二叉树。在满二叉树中，从最后一个结点开始，连续去掉任意个结点，即是一棵完全二叉树。A1523467910BCDEFGHIJK11L12M13N14O158A15234678910BCDEFGHIJ不是完全二叉树，结点10与满二叉树中的结点10不是同一个结点特殊二叉树——完全二叉树1.叶子结点只能出现在最下两层，且最下层的叶子结点都集中在二叉树的左部；2.完全二叉树中如果有度为1的结点，只可能有一个，且该结点只有左孩子。3.深度为k的完全二叉树在k-1层上一定是满二叉树。完全二叉树的特点A15234678910BCDEFGHIJ41正则二叉树理想平衡二叉树满的二、二叉树的性质•性质1：若二叉树结点的层次从1开始,则在二叉树的第i层最多有2i-1个结点。(i≥1)•性质2：深度为k的二叉树最少有k个结点，最多有2k-1个结点。(k≥1)因为每一层最少要有1个结点，因此，最少结点数为k。最多结点个数借助性质1：用求等比级数前k项和的公式：20+21+22+…+2k-1=2k-1数字媒体技术教研室乐小燕4243•性质3：对任何一棵二叉树，如果其叶结点有n0个,度为2的非叶结点有n2个,则有n0＝n2＋1若设度为1的结点有n1个，总结点数为n，总边数为e，则根据二叉树的定义，n=n0+n1+n2e=2n2+n1=n-1因此，有2n2+n1=n0+n1+n2-1n2=n0-1n0=n2+1二、二叉树的性质44•性质4具有n(n≥0)个结点的完全二叉树的深度为设完全二叉树的深度为k，则有2k-1-1n≤2k-1取对数k-1≤log2(n)k有上面k-1层结点数包括第k层的最大结点数23-124-1二、二叉树的性质1log2n1log2n45•性质5如将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号1,2,…,n，则有以下关系：√若i=1,则i无双亲√若i1,则i的双亲为i／2√若2*i=n,则i的左子女为2*i，√若2*i+1=n,则i的右子女为2*i+1√若i为奇数,且i!=1,则其左兄弟为i-1,√若i为偶数,且i!=n,则其右兄弟为i+112348567910二、二叉树的性质具有3个结点的树和具有3个结点的二叉树的形态二叉树和树是两种树结