树形结构课件.pptVIP

由於bk是根結點,而在中序遍曆過程中,先遍曆左子樹,再訪問根結點,最後再遍曆右子樹。所以在中序序列中,b0b1…bk-1必是根結點bk(也就是a0)左子樹的中序序列,即bk的左子樹有k個結點(注意,k=0表示結點bk沒有左子樹。)而bk+1…bn-1必是根結點bk(也就是a0)右子樹的中序序列,即bk的右子樹有n-k-1個結點(注意,k=n-1表示結點bk沒有右子樹。)。另外,在先序序列中,緊跟在根結點a0之後的k個結點a1…ak就是左子樹的先序序列,ak+1…an-1這n-k-1就是右子樹的先序序列。根據歸納假設,由於子先序序列a1…ak和子中序序列b0b1…bk-1可以惟一地確定根結點a0的左子樹,而子先序序列ak+1…an-1和子中序序列bk+1…bn-1可以惟一地確定根結點a0的右子樹。綜上所述,這棵二叉樹的根結點己經確定,而且其左、右子樹都惟一地確定了,所以整個二叉樹也就惟一地確定了。例如,已知先序序列為ABDGCEF,中序序列為DGBAECF,則構造二叉樹的過程如下所示。根結點：A左先序:BDG左中序:DGB右先序:CEF右中序:ECF根結點：B左先序:DG左中序:DG右先序:空右中序:空根結點：D左先序:空左中序:空右先序:G右中序:G根結點：G左先序:空左中序:空右先序:空右中序:空根結點：C左先序:E左中序:E右先序:F右中序:F根結點：E左先序:空左中序:空右先序:空右中序:空根結點：F左先序:空左中序:空右先序:空右中序:空由上述定理得到以下構造二叉樹的演算法：BTNode*CreateBT1(char*pre,char*in,intn){BTNode*s;char*p;intk;if(n=0)returnNULL;s=(BTNode*)malloc(sizeof(BTNode));/*創建結點*s*/s-data=*pre;for(p=in;pin+n;p++)/*在中序中找為*ppos的位置k*/ if(*p==*pre) break;k=p-in;s-lchild=CreateBT1(pre+1,in,k); /*遞歸構造左子樹*/s-rchild=CreateBT1(pre+k+1,p+1,n-k-1);/*構造右子樹*/returns;}定理7.2：任何n(n＞0)個不同結點的二又樹,都可由它的中序序列和後序序列惟一地確定。同樣採用數學歸納法證明。實際上,對於根結點ak的左右子樹,在確定左右子樹的子中序序列後,不需要確定左右子樹的整個子後序序列,只需確定子中序序列中全部字元在後序序列中最右邊的那個字元即可,因為這個字元就是子樹的根結點。例如,已知中序序列為DGBAECF,後序序列為GDBEFCA。對應的構造二叉樹的過程如下所示。根結點：A左中序:DGB左根:B右中序:ECF右根:C根結點：B左中序:DG左根:D右中序:空右根:空根結點：D左中序:空左根:空右中序:G右根:G根結點：G左中序:空左根:空右中序:空右根:空根結點：C左中序:E左根:E右中序:F右根:F根結點：E左中序:空左根:空右中序:空右根:空根結點：F左中序:空左根:空右中序:空右根:空2.中序遍曆非遞歸演算法（2）第二種方法（常規方法）由中序遍曆過程可知，採用一個棧保存需要返回的結點指針，先掃描（並非訪問）根結點的所有左結點並將它們一一進棧。然後出棧一個結點，顯然該結點沒有左孩子結點或者左孩子結點已訪問過（進一步說明該結點的左子樹均已訪問），則訪問它。然後掃描該結點的右孩子結點，將其進棧，再掃描該右孩子結點的所有左結點並一一進棧，如此這樣，直到棧空為止。voidInOrder2(BTNode*b){ BTNode*St[MaxSize],*p;inttop=-1; p=b; while(top-1||p!=NULL) {while(p!=NULL)//掃描*p的所有左結點並進棧 {top++;St[top]=p; p=p-lchild; } if(top-1)