数据结构-清华大学-殷人昆-04

第4章树与二叉树清华大学计算机系殷人昆数据结构课件第四章树与二叉树层层叠叠纵向展开化复杂为简单的参天大树202-2树的定义与基本概念二叉树二叉树遍历二叉树的计数线索二叉树树与树的遍历树的应用第4章树与二叉树202-3树和森林的概念树的定义树是由n(n＞0)个结点组成的有限集合：有一个特定的称之为根(root)的结点；除根以外的其它结点划分为m(m≥0)个互不相交的有限集合T1,T2,…,Tm，每个集合又是一棵树，并且称之为根的子树。此定义是离散数学和图论中给出的。它们把树视为图的一个极小连通子图。有n个结点的树有n-1条边，而且不能有回路。202-4这种观点的典型代表是Knuth。他认为图至少有一个顶点，树也必须至少有一个顶点。树不能是空树，但N叉树可以是空树。N叉树是限制根的子树最多不能超过N棵的树。随着对树讨论的深入，人们放宽了对树结构的限制。若把树当作层次结构单独对待，树中允许结点个数为0。这样，树与N叉树就没有不可逾越的鸿沟了。从面向对象观点，N叉树是树的特殊实现：树是父类，N叉树是子类。N叉树继承了树的特性，它还有自己增加的特性，例如202-5理论上树不可是空树，N叉树可以是空树；树的子树可以有序，也可以不要求有序，而N叉树的子树必须有序。N叉树的定义也是递归的，递归到空树终止；树则递归到只有一个结点的子树。树的子树棵数不限，而N叉树中根的子树最多N棵。树可以区分为外向树和内向树，而N叉树一般是外向树，即边是有向的，从父指向子。树可以用N叉树实现。二叉树、B树等又都是N叉树的特殊情形。202-6树的特点树是分层结构，又是递归结构。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。1层2层4层3层depth=4height=4ACGBDEFKLHMIJ前驱后继202-71层2层4层3层depth=4height=4ACGBDEFKLHMIJ结点结点的度分支结点叶结点子女双亲兄弟祖先树的度树深度树高度森林子孙结点层次结点深度结点高度202-8注意，结点的深度和结点的高度是不同的。结点的深度即结点所处层次，是从根向下逐层计算的；结点的高度是从下向上逐层计算的：叶结点的高度为1,其他结点的高度是取它的所有子女结点最大高度加一。树的深度与高度相等。树的深度按离根最远的叶结点算，树的高度按根结点算，都是6。叶结点也称为终端结点，非叶结点也称为非终端结点。ABCDEFGHILKJ高度=4深度=3202-9二叉树的五种不同形态LLRR二叉树(BinaryTree)二叉树的定义一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。这个定义是递归的。202-10二叉树的性质性质1若二叉树的层次从1开始,则在二叉树的第i层最多有2i-1个结点。(i≥1)[证明用数学归纳法]i=1时，根结点只有1个，21-1=20=1；若设i=k时性质成立，即该层最多有2k-1个结点，则当i=k+1时，由于第k层每个结点最多可有2个子女，第k+1层最多结点个数可有2*2k-1=2k个，故性质成立。202-11性质2高度为h的二叉树最多有2h-1个结点。(h≥1)[证明用求等比级数前k项和的公式]高度为h的二叉树有h层，各层最多结点个数相加，得到等比级数，求和得：20+21+22+…+2h-1=2h-1空树的高度为0，只有根结点的树的高度为1。202-12性质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引申：可用于判断二叉树各类结点个数。202-13定义1满二叉树(FullBinaryTree)定义2完全二叉树(CompleteBinaryTree)若设二叉树的高度为h，则共有h层。除第h层外，其它各层(1～h-1)的结点数都达到最大个数，第h层从右向左连续缺若干结点，这就是完全二叉树。202-14性质4具有n(n≥0)个结点的完全二叉树的高度为log2(n+1)证明：设完全二叉树的高度为h，则有2h-1-1＜n≤2h-1上面h-1层结点数包括第h层的最大结点数变形2h-1＜n+1≤2h取对数h-1＜log2(n+1)≤h有h=log2(n+1)23-124-1202-1523-124-1注意：求高度的另一公式为log2n+1,此公式对于n=0不适用。若设完全二叉树中叶结点有n0个,则该二叉树总的结点数为n=2n0,或n=2n0–1。若完全二叉树的结点数为奇数，没有度为1的结点；为偶数，有一个度为1的结点。右图为理想平衡树，上层都是满的，第h层结点分布在各处。202-16性质5如将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号:0,1,2,…,n-1，则有以下关系：若i=0,则i无双亲；若i0,则i的双亲为(i-1)/2。若2*i+1n,则i的左子女为2*i+1；若2*i+2n,则i的右子女为2*i+2。若i为偶数,且i!=0,则其左兄弟为i-1；若i为奇数,且i!=n-1,则其右兄弟为i+1。0123745689202-17注意：如果完全二叉树各层次结点从1开始编号：1,2,3,…,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+1。12348567910202-18完全二叉树一般二叉树的顺序表示的顺序表示00123456789130123567811131378945620126537811491012二叉树的顺序表示202-1902614300261430极端情形:只有右单支的二叉树对于完全二叉树，因结点编号连续，数据存储密集，适于用顺序表示；对于一般二叉树，用链表表示较好；202-20lchilddatarchilddatalchildrchild左子女指针右子女指针二叉树的二叉链表表示使用二叉链表，找子女的时间复杂度为O(1)，找双亲的时间复杂度为O(log2i)～O(i)，其中，i是该结点编号。202-21lchilddataparentrchildparentdatalchildrchild左子女指针双亲指针右子女指针二叉树的三叉链表表示使用三叉链表，找子女、双亲的时间都是O(1)。202-22AAABBBCCCDDDFFFEEErootrootroot二叉树二叉链表三叉链表二叉树链表表示的示例202-23二叉树的定义typedefcharTElemType;//树结点数据类型typedefstructnode{//树结点定义TElemTypedata;//结点数据域structnode*lchild,*rchild;//子女指针域}BiTNode;typedefBiTNode*BinTree;//树定义，代表树的根指针202-24二叉树遍历树的遍历就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。设访问根结点记作V，遍历根的左子树记作L，遍历根的右子树记作R，则可能的遍历次序有前序VLR镜像VRL中序LVR镜像RVL后序LRV镜像RLV202-25中序遍历二叉树算法的框架是：若二叉树为空，则空操作；否则中序遍历左子树(L)；访问根结点(V)；中序遍历右子树(R)。遍历结果a+b*c-d-e/f中序遍历(InorderTraversal)--/+*abcdef202-26二叉树递归的中序遍历算法voidInOrder(BiTNode*T){if(T!=NULL){InOrder(T-lchild);visit(T-data);InOrder(T-rchild);}}visit()是输出数据值的操作，在实际使用时可用相应的操作来替换。202-27前序遍历二叉树算法的框架是：若二叉树为空，则空操作；否则访问根结点(V)；前序遍历左子树(L)；前序遍历右子树(R)。遍历结果-+a*b-cd/ef前序遍历(PreorderTraversal)--/+*abcdef202-28二叉树递归的前序遍历算法voidPreOrder(BiTNode*T){if(T!=NULL){visit(T-data);PreOrder(T-lchild);PreOrder(T-rchild);}}与中序遍历算法相比，visit()操作放在两个子树递归前序遍历的最前面。202-29后序遍历二叉树算法的框架是：若二叉树为空，则空操作；否则后序遍历左子树(L)；后序遍历右子树(R)；访问根结点(V)。遍历结果abcd-*+ef/-后序遍历(PostorderTraversal)d--/+*abcdef202-30二叉树递归的后序遍历算法voidPostOrder(BiTNode*T){if(T!=NULL){PostOrder(T-lchild);PostOrder(T-rchild);visit(T-data);}}与中序遍历算法相比，visit()操作放在两个子树递归前序遍历的最后面。202-31计算二叉树结点个数的递归算法应用二叉树遍历的事例intCount(BiTNode*T){if(T==NULL)return0;elsereturn1+Count(T-lchild)+Count(T-rchild);}空二叉树的结点个数为0，可直接计算；否则可分别计算左、右子树的结点个数，再相加得到总结点个数。202-32求二叉树高度的递归算法intHeight(BiTNode*T){if(T==NULL)return0;else{intm=Height(T-lchild);intn=Height(T-rchild));return(mn)?m+1:n+1;}空树的高度为0；非空树情形，先计算根结点左右子树的高度，取大者再加一得到二叉树高度。202-33abcecdcc访问a进栈c左进b访问b进栈d左进空退栈d访问d左进空退栈c访问c左进e访问e左进空退栈结束利用栈的前序遍历的非递归算法ddc202-34voidPreOrder(BinTreeT){stackS;InitStack(S);//递归工作栈BiTNode*p=T;Push(S,NULL);while(p!=NULL){visit(p-data);if(p-rchild!=NULL)Push(S,p-rchild);if(p-lchild!=NULL)p=p-lchild;//进左子树elsePop(S,p);//左子树空,进右子树}}202-35abcdebaadaa左空退栈访问左空退栈访问退栈访问左空ec退栈访问cc右空退栈访问栈空结束利用栈的中序遍历的非递归算法202-36voidInOrder(BinTreeT){stackS;InitStack(S);//递归工作栈BiTNode*p=T;//初始化do{while(p!=NULL)//子树非空找中序第一个{Push(S,p);p=p-lchild;}//边找边进栈if(!StackEmpty(S)){//栈非空Pop(S,p);//子树中序第一个退栈visit(p-data);//访问之p=p-rchild;//向右子树走}}while(p!=NULL||!StackEmpty(S));}202-37后序遍历时使用的栈的结点定义typedefstruct{BiTNode*ptr;//结点指针enumtag{L,R};//该结点退栈标记}Stac