数据结构-第六章-树和二叉树

第六章树和二叉树树的概念和基本术语二叉树二叉树遍历二叉树的计数树与森林霍夫曼树树的概念和基本术语树的定义树是由n(n0)个结点的有限集合。如果n=0，称为空树；如果n0，则有且仅有一个特定的称之为根(Root)的结点，它只有直接后继，但没有直接前驱；当n1，除根以外的其它结点划分为m(m0)个互不相交的有限集T1,T2,…,Tm，其中每个集合本身又是一棵树，并且称为根的子树(SubTree)。ACGBDEFKLHMIJ例如A只有根结点的树有13个结点的树其中：A是根；其余结点分成三个互不相交的子集，T1={B,E,F,K,L}；T2={C,G}；T3={D,H,I,J,M},T1,T2,T3都是根A的子树，且本身也是一棵树树的基本术语1层2层4层3层height=4ACGBDEFKLHMIJ结点结点的度叶结点分支结点子女双亲兄弟祖先子孙结点层次树的深度树的度有序树无序树森林结点：一个数据元素及指向其子树的分支。结点的度：结点拥有的子树个数。叶结点：度为零的结点。子女：结点子树的根。兄弟：同一结点子女。祖先：根到该结点路径上的所有结点。子孙：某结点为根的子树上的任意结点。结点层次：从根开始，根为第一层，根的子女为第二层，以此类推。树的深度（高度）：树中结点的最大层次数。有序树：树中结点的子树由左向右有序。森林：m(m0)棵互不相交的树。二叉树(BinaryTree)定义五种形态一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。LLRR特点每个结点至多只有两棵子树（二叉树中不存在度大于2的结点）性质1在二叉树的第i层上至多有2i－1个结点。(i1)[证明用归纳法]证明：当i=1时，只有根结点，2i-1=20=1。假设对所有j，ij1，命题成立，即第j层上至多有2j-1个结点。由归纳假设第i-1层上至多有2i－2个结点。由于二叉树的每个结点的度至多为2，故在第i层上的最大结点数为第i-1层上的最大结点数的2倍，即2*2i－2=2i-1。性质性质2深度为k的二叉树至多有2k-1个结点(k1)。证明：由性质1可见，深度为k的二叉树的最大结点数为kii112＝20+21+…+2k-1=2k-1kii1(层上的最大结点数）第＝性质3对任何一棵二叉树T,如果其叶结点数为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定义1满二叉树(FullBinaryTree)一棵深度为k且有2k-1个结点的二叉树称为满二叉树。两种特殊形态的二叉树621754389101113141512满二叉树2154367216543非完全二叉树定义2完全二叉树(CompleteBinaryTree)若设二叉树的高度为h，则共有h层。除第h层外，其它各层(0h-1)的结点数都达到最大个数，第h层从右向左连续缺若干结点，这就是完全二叉树。621754389101112完全二叉树性质4具有n(n0)个结点的完全二叉树的深度为log2(n)＋1证明：设完全二叉树的深度为h，则根据性质2和完全二叉树的定义有2h－1-1n2h-1或2h－1n2h取对数h－1log2nh，又h是整数，因此有h=log2(n)＋1性质5如将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号0,1,2,…,n-1，则有以下关系：若i=1,则i无双亲若i1,则i的双亲为i/2若2*in,则i的左子女为2*i，若2*i+1n,则i的右子女为2*i+1若结点编号i为奇数，且i!=1,则左兄弟结点i-1.若结点编号i为偶数，且i!=n,则右兄弟结点为i+1.结点i所在层次为log2i+1如果2in，则结点i没有左孩子；如果2i+1n，则结点i没有右孩子；18234567910我们首先证明（2）和（3）。当i=1时，若n≥3，则根的左、右孩子的编号分别是2，3；若n3，则根没有右孩子；若n2，则根将没有左、右孩子；以上对于（2）和（3）均成立。假设：对于所有的1≤j≤i结论成立。即：结点j的左孩子编号为2j；右孩子编号为2j+1。下面我们利用数学归纳法证明这个性质由完全二叉树的结构可以看出：结点i+1或者与结点i同层且紧邻i结点的右侧，或者i位于某层的最右端，i+1位于下一层的最左端。可以看出，i+1的左、右孩子紧邻在结点i的孩子后面，由于结点i的左、右孩子编号分别为2i和2i+1，所以，结点i+1的左、右孩子编号分别为2i+2和2i+3，经提取公因式可以得到：2(i+1)和2(i+1)+1，即结点i+1的左孩子编号为2(i+1)；右孩子编号为2(i+1)+1。又因为二叉树由n个结点组成，所以，当2(i+1)+1n，且2(i+1)=n时，结点i+1只有左孩子，而没有右孩子；当2(i+1)n，结点i+1既没有左孩子也没有右孩子。以上证明得到（2）和（3）成立。下面利用上面的结论证明（1）。对于任意一个结点i，若2i≤n，则左孩子的编号为2i，反过来结点2i的双亲就是i，而2i/2=i；若2i+1≤n，则右孩子的编号为2i+1，反过来结点2i+1的双亲就是i，而(2i+1)/2=i，由此可以得出（1）成立。完全二叉树一般二叉树的顺序表示的顺序表示二叉树的存储结构112345678910912340567800910248910567312365478顺序表示910在C语言中，这种存储形式的类型定义如下所示：#defineMAX_TREE_LINKLIST_SIZE100typedefstruct{Elemtypeelem[MAX_TREE_LINKLIST_SIZE];//根存储在下标为1的数组单元中intn;//当前完全二叉树的结点个数}QBTree;这种存储结构的特点是空间利用率高、寻找孩子和双亲比较容易。下面我们给出完全二叉树在这种存储形式下的操作算法。（1）构造一棵完全二叉树voidCreateBTree(QBTree*BT,Elemtypeelem[],intn){if(n=MAX_TREE_LINKLIST_SIZE)n=MAX_TREE_LINKLIST_SIZE-1;for(i=1;i=n;i++)BT-elem[i]=elem[i];BT-n=n;}（2）获取给定结点的左孩子intLeftCHild(QBTreeBT,intlinklist){if(2*linklistBT.n)return0;elsereturn2*linklist;}RightChild(BT,linklist)与这个操作类似，读者可试着自行完成。（3）获取给定结点的双亲intParent(QBTreeBT,intlinklist){if(1=linklist&&linklist=BT.n)returni/2;elsereturn-1;}链表表示lChilddatarChilddatalChildrChild二叉链表含两个指针域的结点结构lChilddataparentrChild含三个指针域的结点结构parentdatalChildrChild三叉链表性质：含有n个结点的二叉链表中有n+1个空链域。证明：对于叶结点n0有两个空链域，n1有1个空链域，n2没有空链域。所以空链域数＝2n0+n1将n0=n2+1代入得(根据性质3)2n0+n1=n0+n1+n2+1=n+1二叉树链表表示的示例AAABBBCCCDDDFFFEEErootrootroot二叉树二叉链表三叉链表Lchild和Rchild是分别指向该结点左孩子和右孩子的指针，elem是数据元素的内容。在C语言中的类型定义为：typedefstructBTLinklist{Elemtypeelem;structBTLinklist*Lchild,*Rchlid;}BTLinklist,*BTree;三叉链表的静态结构ABCDFErootdataparentleftChildrightChild012345A-11-1B023C1-1-1D145E3-1-1F3-1-1typedefcharTreeData;//结点数据类型typedefstructnode{//结点定义TreeDatadata;structnode*leftChild,*rightchild;}BinTreeNode;typedefBinTreeNode*BinTree;//根指针二叉链表的定义二叉树遍历树的遍历就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。设访问根结点记作V遍历根的左子树记作L遍历根的右子树记作R则可能的遍历次序有前序VLR中序LVR后序LRVVLR中序遍历二叉树算法的定义：若二叉树为空，则空操作；否则中序遍历左子树(L)；访问根结点(V)；中序遍历右子树(R)。遍历结果a+b*c-d-e/f中序遍历(InorderTraversal)--/+*abcdefvoidInOrder(BinTreeNode*T){if(T!=NULL){InOrder(T-leftChild);Visit(T-data);InOrder(T-rightChild);}}中序遍历二叉树的递归算法前序遍历二叉树算法的定义：若二叉树为空，则空操作；否则访问根结点(V)；前序遍历左子树(L)；前序遍历右子树(R)。遍历结果-+a*b-cd/ef前序遍历(PreorderTraversal)--/+*abcdef前序遍历二叉树的递归算法voidPreOrder(BinTreeNode*T){if(T!=NULL){Visit(T-data);PreOrder(T-leftChild);PreOrder(T-rightChild);}}后序遍历二叉树算法的定义：若二叉树为空，则空操作；否则后序遍历左子树(L)；后序遍历右子树(R)；访问根结点(V)。遍历结果abcd-*+ef/-后序遍历(PostorderTraversal)--/+*abcdef后序遍历二叉树的递归算法：voidPostOrder(BinTreeNode*T){if(T!=NULL){PostOrder(T-leftChild);PostOrder(T-rightChild);Visit(T-data);}}二叉树遍历应用以递归方式建立二叉树。输入结点值的顺序必须对应二叉树结点前序遍历的顺序。并约定以输入序列中不可能出现的值作为空结点的值以结束递归,此值在RefValue中。例如用“@”或用“-1”表示字符序列或正整数序列空结点。1.按前序建立二叉树(递归算法)如图所示的二叉树的前序遍历顺序为ABC@@DE@G@@F@@@ABCDEGF@@@@@@@@StatusCreateBiTree(BiTree&T){scanf(&ch);if(ch==‘’)T=NULL;//读入根结点的值else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);//建立根结点T-data=ch;CreateBiTree(T-leftChild);CreateBiTree(T-rightChild);}returnOK;}//CreateBiTreeintCount(BinTreeNode*T){if(T==NULL)return0;elsereturn1+Count(T-leftChild)+Count(T-rightChild);}2.计算二叉树结点个数(递归算法)intLeaf_Count(BitreeT){//求二叉树中叶子结点的数目if(!T)return0;//空树没有叶子elseif(!T-lchild&&!T-