软件基础1014第五章数据结构树

树

第五章数据结构(BinaryTree)。根(左子树,右子树) 或根(左子树,) 或根(,右子树) 或根A为根的二叉树:A(BD(GHC(EA的后件 A(B,B的后件 B(,C的后件 C(E,D的后件 E的后件 E(,<二叉树根|<根子树<子树> (<左子树>,<右子树>|(<左子树|右子树<左子树左子|<左子子树<右子树右子|<右子子树二叉树的形

<二叉树根|<根>(<子树<子树> <左子树>,<右子树|<左子树|右子树<左子树左子|<左子>(<子树<右子树右子|<右子>(<子树ABΦDGΦΦHΦΦCΦEΦFΦΦAΦBΦDGΦΦHΦΦCΦEΦFΦΦ s#defineBINODE s{ BINODEBINODE结构存放一个结点，根结点由Root指向fatherLeftright分别指向父结点和

#defineBINODEstructbinode----C04-C04-shortfather,Left,-BINODE-D1-D1---每个数组元素Tree[i](i=0,...,n-1)存放一个结点。用数组下标表示结点地址，用-1表示空地址。定义变量Root指向根结点。结点成员fatherLeft-图示树的前序遍历结果：ABDGHCE图示树的后序遍历结果：GHDBFEC图示树的中序遍历结果：BGDHAEFBGDHAEFC【例5-5.1】二叉树标准形式的

DDE HA F(网络课堂：exe5-DE#defineBINODEstructbinodeDE{ shortleft,right;BINODEshort址。定义变量root指向根结点。结点成员leftright分别指向左右子。i0A211B4-2C-33D674E-55F--6G--7H--voidCreateBitree(short*n,short{

{intscanf("%d%d",n,root);for(i=0;i<*n;i++)T[i].s,&T[i].Left,}8A2B4-C-1D6E-1F-1-G-1-H-1- }{if(node==-1)printf(“%s\n”,T[node].s);}输

print printprint

print

print print‘B’ print‘E’ print‘F’ 【例5-5.2】二叉树标准形式 编A(C(,D(G,H),B(E(,F),#defineBINODEstructbinode{

CΦACΦA

BINODE {if}voidCreateBitree(void){ {

BΦ

GΦGΦΦHΦHΦΦDEDEΦFΦFΦΦ /*输入并生成二叉树*/ /*后序遍 }树，或者说不能用直接用数组实现树的，因为k’=k+s(k是k’的前件)，而只一种线性的关系，当结点k是结点k’关于某种遍历的前件时，可以满足k’=k+s。在二叉一定的约定，或者说需要附加某种关系。 修正树的单元定义，例如，将k={k,k,pk}k={k,k,pk,fLag}，即增加一个fLag标志，以说明结点另外一个后件(非遍历后件)的信息。由于二叉树中结点的后件最多是两个，因此可以用pk和fLag来结点的后件。pk

flag kL，则必定是前序遍历的后件。因此若fLag1k有左子kL，即B(1)AB(1)A(3)E(4)G(4)H(4)0A0A511B202D413G-04H-05C-16E707F-0则fLag=1，pk=-1，kL=k+s，如结点C #defineBITREEstructbitree{char*s;shortp,fLag; short{intfor(i=0;i<n;i++)}if(tree[j].fLag==0)printf(“noLeftchiLd\n”);printf(“LeftchiLdis%s\n”,if(tree[j].p==-1)printf(“rightchiLdis%s\n”,printf(“predecessoris%s\n”,tree[j-B(1)A(3)E(4)G(4)HB(1)A(3)E(4)G(4)H(4)#defineABS(x) (x>0)?(x):(-x)#defineBITREEstructbitree{short0A51B2D43G-4H-5C6E7F- short /*结点数 若pk>0， 则结点k有左件，且kL=k+s。若pk<0， 则结点k无左件。若|pk|!=MkkR|pk|。若|pk|==M，则结点k无右件。{intfor(i=0;i<n;i++)}if(tree[j].p<0)printf(“noLeftchiLd\n”);printf(“LeftchiLdis%s\n”,if(ABS(tree[j].p)==M)printf(“norightchiLd\n”);printf(“rightchiLdis%s\n”,printf(“predecessoris%s\n”,tree[j-穿线采用标准形式二叉树的情况。若有n个结点，共2n个指针场分量。因为根结点n-1n+1个n-1 #defineABS(x) (x>0)?(x):(-x)#defineTHstructthread{ num,pL,1262033454--5--6707-88--short /*结点 0表示空地址。穿线指针场的值(中序前件或结点C)，必定有th[te].pR==0。shortgetPre(TH*thshort{if(i<1||i>n) /*地址 if((i=th[i].pL)>0) /*有左子 whiLe(th[i].pR> /*有右 i=}则k’=20(th[2].num)。1262033454--5--6707-88--if(k=getPre(th,printf(“prevnodeof%dis%d\n”,th[i].num,printf(“noprevnodefor%d.\n”,th[1].pL(=2)>0，有左子，令i=2；th[2].pR(=3)>0，有右子，令i=3；th[3].pR(=5)>0，有右子，令i=5；则k’=80(th[5].num)。右右右右1262033454--5--6707-88--if(k=getPre(th,printf(“prevnodeof%dis%d\n”,th[i].num,th[k].num);printf(“noprevnodefor%d.\n”,shortgetSuc(TH*thshort{if(i<1||i>n) /*地址*/if((i=th[i].pR)>0) /*有右子 whiLe(th[i].pL>0)/*有左 i=}th[8].pR(=-60k’|-6|6，则k’=30(th[6].num)。if(k=getSuc(th,printf(“sucnodeof%dis%d\n“,th[i].num,th[k].num);printf(“nosucnodefor%d.\n“,无右子 1262033454--5--6707-88--th[1].pR(=6)>0，有右子，令i=6；th[6].pL(=7)>0，有左子，令i=7；则k’=50(th[7].num)。k=getSuc(th, 左1262033454--5--6707-88--shortgetFirst(TH*{shortif((i=th[0].num)==0) /*空树 whiLe(th[i].pL!=0) /*有左子 i=ABS(th[i].pL);}无左子 无左子 1262033454--5--6707-88--if(k=printf(“firstnodeforthreadtreeis%d.\n”,th[k].num);printf(“nonodeinthe symOrder(TH*{shortif((p=getFirst(th)==0) /*求树根 /*空 while(p=getSuc(th, /*1262033454--5--6707-88--对于根结点k0，Lev(k0)=1；k’kLev(kLev(klev:3 A,B,D,E,H,I,F,J,C,G,K,层号=2：BC层号=3：DEF层号=4：HIJ,K1A,2B,3D,3E,4H,4I,3F,4J,2C,3G,4K,D,H,I,E,J,F,B,K,L,G,C,3D,4H,4I,3E,4J,3F,2B,4K,4L,3G,2C,【例5-6.1】根据后序遍历的层号表示生成树whiLe(输入结点(ck)!=空/*c为层号，k{if(c>(ck)进栈，令ctop=c /*等待父结点 /*必有c==1，k为 }2F3D3G2B2C1栈：(2F)栈：(3D)(2F)栈：(3G3D2

栈：(2C2B2 (3G)出栈，G连接为B的子结点 (2C)出栈，C连接为A的子结点(3D)出栈，D连接为B的子结点 (2B)出栈，B连接为A的子结点 (2F)出栈，F连接为A的子结点，栈：(2B)(2 22332232223 2112ACD112 112 G G D22222232223322333323232222222222222层号层号=2：B,G层号=3：EFK层号=4：HJ1A,2B,3E,4H,3F,2G,3K,4J,4H,3E,3F,2B,4J,4L,3K,2G,3E,4H,2B,3F,1A,4J,3K,4L,示,T2的括号表示,…,TM的括号表示)。ABABC GE的括号表示 F的括号表示 F(I,B的括号表示 B(D,E,=B(D,E(H),F(I,G的括号表示 G(J,C的括号表示: C(G)=C(G(J,L)) A的括号表示: A(B,C)=A(B(D,E(H),F(I,K)),C(G(J,L))) A(B(D,E(H,I),F(J)),C(G(K,1 3 4 41A,2B,3D,3E,4H,4I,3F,4J,2C,3G,4K, 1A,2B,3D,3E,4H,3F,4I,4K,2C,3G,4J,A(B(D,E(H),F(I,K)),C(G(J,R(TL的括号表示TR的括号表示)R(TL的括号表示, 或者R(,TR的括号表示 或R(TL的括号表示,TR的括号表示 或者A(B(E(,H),F),C(,K(L,【例5-6.2】二叉树的生成算法(exe5-A(B(D,E),C(F(,G), #defineEMPTY #defineNODEstructnode{ /*结点字符 Left, /*左右子地 NODE /*二叉 short /*根地 */ /*结点数目*/ /*输入字符串*/ /*字符数组指针EE0A141B232D--3E--4C5-5F-76G--, , String中取一个符号：“(”左括号，“)”右括号，或者“,”逗号成功时返回1,否则返回0 生成并结 按“(左子树右子树)”GetData()GetSymboL()获取结点值和有效符号。CreateSubTree()生成子树。() 成功时返回1,否则返回0。shortGetData(char { /*无字 /*从String中取一个字 *key=Sring[++Ptr];if(isaLpha(*key))/*判字母 /*非字母，回退*/} 生成并结

“(”，“)”，或者1,0{ /*无字 /*从String中取一个符号 if(Sring[++Ptr]==symboL) /*非符号，回退*/}{Tree[++N].key=Tree[N].right=}----0A141B232D--3E-- 按“(左子树右子树)”GetData()GetSymboL()获取结点值和有效符号，并递归调用CreateSubTree()生成子树。{shortkey,Left,/*1.取左括号(可以省略) if(GetSymboL(‘(‘)==0)/*2.取左子(可以省略) if(GetData(&key)!=0){/*2.1.生成并左子 Left=CreateNode(key);/*2.2.连接左子 Tree[root].Left=Left;/*2.3