数据结构与算法.ppt课件

4.1基本术语4.2二元树4.3树4.4森林与二元树间的转换4.5树的应用,第四章树（Tree）,线性表元素之间的线性关系树元素之间的层次关系,4.1基本术语,定义一,1、一个结点x组成的集x是一株树，这个结点x也是这株树的根。2、假设x是一个结点，T1，T2，Tk是k株互不相交的树，我们可以构造一株新树：令x为根，并有k条边由x指向树T1，T2，Tk。这些边也叫做分支，T1，T2，Tk称作根x的树之子树（SubTree）。,树是n（0）个结点的有限集。在任意一棵非空树中：1、有且仅有特定的称为根（Root）的结点；2、当n1时，其余结点可分为m（0）个互不相交的有限集T1，T2，Tm，其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）。,定义二,4.1基本术语,定义三,T=（D，R）D：具有相同类型的数据元素的集合。R：若D为空集，则称为空树；若D仅含一个数据元素，则R为空集，否则R=H，H是如下的二元关系：1、在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；2、若D-root，则存在D-root的一个划分D1，D2，Dm（m0），对任意jk（1j，km）有DjDk=，且对任意的i（1im），唯一存在数据元素xiDi，有H;3、对应于D-root的划分，H-,有唯一的一个划分H1，H2，Hm（m0）,对任意jk（1j，km）有HjHk,且对任意的i（1im），Hi是Di上的二元关系，（Di，Hi）是一棵符合本定义的树，称为根root的子树。,4.1基本术语,常用术语：,分支路长,父亲双亲儿子兄弟子孙祖先,层结点的高树的高（深度）,有序树ISEMPTY(BT);CREATEBT(V,LT,RT);LCHILD(BT);RCHILD(BT);DATA(BT);,例1-1：写一个递归函数，按先根顺序列出二元树中每个结点的DATA域之值。,VoidPREORDER(BT)BTREEBT;if(!ISEMPTY(BT)visit(DATA(BT);PREORDER(LCHILD(BT);PREORDER(RCHILD(BT);,例1-2：写一个递归函数，按中根顺序列出二元树中每个结点的DATA域之值。,VoidINORDER(BT)BTREEBT;if(!ISEMPTY(BT)INORDER(LCHILD(BT);visit(DATA(BT);INORDER(RCHILD(BT);,例1-3：写一个递归函数，按后根顺序列出二元树中每个结点的DATA域之值。,VoidPOSTORDER(BT)BTREEBT;if(!ISEMPTY(BT)POSTORDER(LCHILD(BT);POSTORDER(RCHILD(BT);visit(DATA(BT);,例,二元树的遍历的非递归过程,先序：ABDJHECFIGKLM中序：JDHBEAFICGLKM后序：JHDEBIFLMKGCA,VoidINORDER(BT)BTREEBT;if(!ISEMPTY(BT)INORDER(LCHILD(BT);visit(DATA(BT);INORDER(RCHILD(BT);,算法:Loop:if(BT非空)进栈;左一步;else退栈;右一步;,数据结构:设栈S:用以保留当前结点;,二元树的遍历的非递归过程,VoidNINORDER(BT)BTREEBT;STACKS;BTREET;MAKENULL(S);T=BT;while(!ISEMPTY(T)|EMPTY(S)if(!ISEMPTY(T)PUSH(T,S);T=TLCHILD(T);elseT=TOP(S);POP(S);visit(DATA(T);T=TRCHILD(T);,进栈;左走一步,退栈;右走一步,先序遍历非递归算法,算法:Loop:if(BT非空)输出;进栈;左一步;else退栈;右一步;,中序遍历非递归算法,算法:Loop:if(BT非空)进栈;左一步;else退栈;输出;右一步;,先序遍历非递归算法,算法:Loop:if(BT非空)进栈;左一步;else当栈顶指针所指结点的右子树不存在或已访问,退栈并访问;否则右一步;,4.2.3二元树的表示,1、顺序存储a、完全（或满）二元树,根据性质5，如已知某结点的层序编号i,则可求得该结点的双亲结点、左孩子结点和右孩子结点。,采用一维数组，按层序顺序依次存储二元树的每一个结点。如下图所示：,b、一般二元树,根据性质5，如已知某结点的层序编号i,则可求得该结点的双亲结点、左孩子结点和右孩子结点，然后检测其值是否为虚设的特殊结点$。,通过虚设部分结点，使其变成相应的完全二元树。,StructnodeStructnode*lchild;Structnode*rchild;datatypedata;Typedefstructnode*BTREE;,2、二元树的左右链表示,例:(P102)BTREECREATEBT(v,ltree,rtree)datatypev;BTREEltree,rtree;BTREEroot;root=newnode;rootdata=v;rootlchild=ltree;rootrchild=rtree;returnroot;,2、二元树的左右链表示,证明：n个结点的二元树中，共有n+1个空链接域。,证：设其空链域数为x分支数B入=n1B出=2nxB入=B出n1=2nx得出x=n1,结点总数：13空链域的个数：14,例:按先序序列建立二元树的左右链结构.如由图所示二元树,输入:ABDH#I#E#CF#J#G#其中:#表示空,StatusCreateBtree(BTREE,一棵二元树的先序、中序和后序序列分别如下，其中一部分未显示出来，试求出空格处的内容，并画出该二元树。先序：_B_F_ICEH_G中序：D_KFIA_EJC_后序：_K_FBHJ_G_A,二元树中序序列为：ABCEFGHD，后序序列为：ABFHGEDC画出此二元树,完全二元树的某结点若无左孩子结点，则它必是叶结点？,一棵有124个叶子结点的完全二元树，最多有？个结点。,证明任一棵满二元树T中的分支数B满足:B=2(n0-1)，其中n0为叶子结点数,证明：满二元树中不存在度为1的节点，设度为2的结点数为n2则：n=n0+n2又：n=B+1所以有：B=n0+n2-1,而n0=n2+1,n2=n0-1B=n0+n0-1-1=2(n0-1),具有n个结点的满二元树，其叶子结点的个数为多少？,具有n个结点的完全二元树，其叶子结点的个数为多少？,方法一：设满二元树的高度为，则根据二元树的性质，叶子结点数为2h-1二元树总结点数n=2h-1可导出:h-1=(n+1)/2,方法二：结点总数：n=n0+n1+n2但对满二元树，除有n0=n2+1外，还有n1=0故有：n=n0+n0-1n0=(n+1)/2,设高为h的二元树只有度为0和度为2的结点，则此类二元树的结点树至少为，至多为。,答案：2h-1和2h-1,线索二元树,问题的提出：,1、在n个结点的二元树左右链表示中，有n+1个空链域。如何利用n+1个空链域，使二元树的操作更加方便。2、在二元树左右链表示中，为求某个结点的（中序）前驱$P或（中序）后继p$，每次都要从树根开始进行查找，很不方便。,定义：,若结点p有左孩子，则p-lchild指向其左孩子结点，否则令其指向其（中序）前驱。若结点p有右孩子，则p-rchild指向其右孩子结点，否则令其指向其（中序）后继。,结点类型Node,StructLNodeElementtypedata;StructLNode*lchild,*rchild;intltag,rtag;,讨论：为方便操作利用了n+1个结点，但为实现操作却多用了2n个标志位。,TypdefStructLNode*THTREE;,THTREEINNEXT(THTREEp)THTREEp;THTREEQ;Q=p-rchild;if(p-rtag=1)while(Q-ltag=1)Q=Q-lchild;return(Q);,例一：求p$（中序后继）：,分析：(1)当p-rtag=0时，p-rchild既为所求（线索）。(2)当p-rtag=1时，p$为p的右子树的最左结点。,THTREEINPRE(THTREEp)THTREEp;THTREEQ;Q=p-lchild;if(p-ltag=1)while(Q-rtag=1)Q=Q-rchild;return(Q);,例二：求$p（中序前驱）：,分析：(1)当p-ltag=0时，p-lchild既为所求（线索）。(2)当p-ltag=1时，$p为p的左子树的最右结点。,例三：利用INNEXT算法，中序遍历线索二元树。,VoidTHINORDER(THTREEHEAD)THTREEtemp;temp=HEAD;dotemp=INNEXT(temp);if(temp!=HEAD)visit(temp-data);while(temp!=HEAD);,而在线索树中结点的插入与删除则不同，因为要同时考虑修正线索的操作。,在二元树中一般不讨论结点的插入与删除，原因是其插入与删除的操作与线性表相同，所不同的是需要详细说明操作的具体要求。,例：将结点p插入作为结点S的右孩子结点。（1）若S的右子树为空，插入比较简单;（2）若S的右子树非空，则p插入后原来S的右子树作为p的右子树,操作：VoidRINSERT(THTREES,THTREER)THTREEW;R-rchild=S-rchild;R-rtag=S-rtag;R-lchild=S;R-ltag=0;S-rchild=R;S-rtag=1;if(R-rtag=1)w=INNEXT(R);w-lchild=R;,4.2.4二元树的复制,二元树的相似与等价,两株二元树具有相同结构指：（1）它们都是空的；（2）它们都是非空的，且左右子树分别具有相同结构。,定义具有相同结构的二元树为相似二元树。,相似且相应结点包含相同信息的二元树称为等价二元树。,“形状”相同,判断两株二元树是否等价,intEQUAL(firstbt,secondbt)BTREEfirstbt,secondbt;intx;x=0;if(ISEMPTY(firstbt)/*EQUAL*/,二元树的复制,BTREECOPY(BTREEoldtree)BTREEtemp;if(oldtree!=NULL)temp=newNode;temp-lchild=COPY(oldtree-lchild);temp-rchild=COPY(oldtree-rchild);temp-data=oldtree-data;return(temp);return(NULL);/*COPY*/,4.3树,4.3.1抽象数据型树,PARENT(n,T)求结点n的双亲LEFTMOST-CHILD(n,T)返回结点n的最左儿子RIGHT-SIBLING(n,T)返回结点n的右兄弟DATA(n,T)返回结点n的信息CREATEk(v,T1,T2,Tk),k=1,2,建立data域v的根结点r,有k株子树T1,T2,Tk且自左至右排列；返回r。ROOT(T)返回树T的根结点,树的三种遍历,先根顺序访问根结点；先根顺序遍历T1;先根顺序遍历T2;先跟顺序遍历Tk;,中根顺序中根顺序遍历T1;访问根结点；中根顺序遍历T2;中根顺序遍历Tk;,后根顺序后根顺序遍历T1;后根顺序遍历T2;后根顺序遍历Tk;访问根结点；,例：假设树的类型为TREE，结点的类型为node，数据项的类型为elementtype，用递归方法给出树的先根遍历如下：,VoidPREORDER(n,T)Noden;TREET;nodec;visit(DATA(T);c=LEFTMOST-CHILD(n,T);while(c!=NULL)PREORDER(c,T);c=RIGHT-SIBLING(c,T);,4.3.2树的存储结构,1、树的双亲表示法（数组实现方法）,树的结点依次编号为1，2，3，n；设数组Ai,一般有：PARENT(i)=Ai,Structnodeintparent;chardata;,TypdefnodeTREE11;TREET;,T7.parent=5;T7.data=1;,面向特定的操作，设计合适的存储结构,树的双亲表示法的改进方案,Typedefintnode;TypedefnodeTREEmaxnodes;,nodeLEFTMOST-CHILD(n,T)noden;TREET;nodeI;for(i=n+1;i=maxnodes1;i+)if(Ti=n)return(i);i为最左孩子return(0);n是叶子,算法LEFTMOST-CHILD,2、树的孩子表示法（邻接表表示法）,typedefstructCTNodeintchild;structCTNode*next;*ChildPtr;typedefstructTelementtypedata;ChildPtrfirstchild;CTBox;typedefstructCTBoxnodesMAX_TREE_SIZE;intn,r;Ctree;,3、树的孩子兄弟表示法（二元树表示法）,类型：typedefstructCSNodeElemTypedata;structCSNode*firstchild,*nextsibling;,4.4森林与二元树,森林转换为二元树：,1、先将森林中每棵树转换成二元树,2、二元树的树根连接起来,4.5树的应用,如内结点数为n，则外结点S=n+1,内结点路径长度I=21+32+13=11外结点路径长度E=12+53+24=25,如内结点路径长度为I，则外结点路径长度E=I2n,设：wi=2,3,4,11,求：wjlj（加权路长）,（a）111422333=34（b）213243113=53（c）2211232