【文章內(nèi)容簡介】 } } //while } （ 2） 第二種方法 （ 常規(guī)方法 ） void PreOrder2(BTNode *b) { BTNode *St[MaxSize],*p。 int top=1。 top++。 St[top]=b。 //根結點入棧 while (top1) //棧不為空時循環(huán) { p=St[top]。 top。 //退棧并訪問該結點 printf(%c ,pdata)。 if (prchild!=NULL) //右孩子結點入棧 { top++。 St[top]=prchild。 } if (plchild!=NULL)//左孩子結點入棧 { top++。 St[top]=plchild。 } } } 2. 中序遍歷非遞歸算法 （ 2） 第二種方法 （ 常規(guī)方法 ） 由中序遍歷過程可知 ， 采用一個棧保存需要返回的結點指針 ， 先掃描 （ 并非訪問 ） 根結點的所有左結點并將它們一一進棧 。 然后出棧一個結點 ， 顯然該結點沒有左孩子結點或者左孩子結點已訪問過 （ 進一步說明該結點的左子樹均已訪問 ） ， 則訪問它 。 然后掃描該結點的右孩子結點 ， 將其進棧 ， 再掃描該右孩子結點的所有左結點并一一進棧 ， 如此這樣 ， 直到?？諡橹?。 void InOrder2(BTNode *b) { BTNode *St[MaxSize],*p。 int top=1。 p=b。 while (top1 || p!=NULL) { while (p!=NULL) //掃描 *p的所有左結點并進棧 { top++。 St[top]=p。 p=plchild。 } if (top1) { p=St[top]。top。 //出棧 *p結點 printf(%c ,pdata)。 //訪問之 p=prchild。 //掃描 *p的右孩子結點 } } //end of while(top1 || p!=NULL) } 找 *b的最左下結點 3. 后序遍歷非遞歸算法 （ 2） 第二種方法 （ 常規(guī)方法 ） 由后遍歷過程可知 ， 采用一個棧保存需要返回的結點指針 ，先掃描根結點的所有左結點并一一進棧 ， 出棧一個結點 *b即當前結點 ， 然后掃描該結點的右孩子結點并入棧 ， 再掃描該右孩子結點的所有左結點并入棧 。 當一個結點的左右孩子結點均訪問后再訪問該結點 ， 如此這樣 ， 直到?？諡橹?。 難點： 如何判斷一個結點 *b的右孩子結點已訪問過 ，為此用 p保存剛剛訪問過的結點（初值為 NULL），若 brchild==p成立（ 在后序遍歷中， *b的右孩子結點一定剛好在 *b之前訪問 ），說明 *b的左右子樹均已訪問，現(xiàn)在應訪問 *b。 void PostOrder2(BTNode *b) { BTNode *St[MaxSize]。BTNode *p。 int flag,top=1。 //棧指針置初值 do { while (b!=NULL) //將 *b的所有左結點進棧 { top++。 St[top]=b。 b=blchild。 } p=NULL。 //p指向棧頂結點的前一個已訪問的結點 flag=1。 //設置 b的訪問標記為已訪問過 找最左下結點 while (top!=1 amp。amp。 flag==1) { b=St[top]。 //取出當前的棧頂元素 if (brchild==p) { printf(%c ,bdata)。 //訪問 *b結點 top。p=b。 //p指向則被訪問的結點 } else { b=brchild。 //b指向右孩子結點 flag=0。 //設置未被訪問的標記 } } //end of while (top!=1 amp。amp。 flag==1) } while (top!=1)。 } b的右孩子不存在或已訪問過 從上述過程可知，棧中保存的是當前結點 *b的所有祖先結點（均未訪問過）。 例如，求一個結點的所有祖先結點。 二叉樹的基本運算及其實現(xiàn) 二叉樹的基本運算概述 二叉樹的基本運算算法實現(xiàn) 二叉樹的基本運算概述 歸納起來 ,二叉樹有以下基本運算： (1)創(chuàng)建二叉樹 CreateBTNode(*b,*str)：根據(jù)二叉樹括號表示法的字符串 *str生成對應的鏈式存儲結構 。 (2)查找結點 FindNode(*b,x)：在二叉樹 b中尋找data域值為 x的結點 ,并返回指向該結點的指針 。 (3)找孩子結點 LchildNode(p)和 RchildNode(p)：分別求二叉樹中結點 *p的左孩子結點和右孩子結點 。 (4)求高度 BTNodeDepth(*b)：求二叉樹 b的高度 。若二叉樹為空 ,則其高度為 0；否則 ,其高度等于左子樹與右子樹中的最大高度加 l。 (5)輸出二叉樹 DispBTNode(*b)：以括號表示法輸出一棵二叉樹 。 二叉樹的基本運算算法實現(xiàn) (1) 創(chuàng)建二叉樹 CreateBTNode(*b,*str) 用 ch掃描采用括號表示法表示二叉樹的字符串 。 分以下幾種情況： ① 若 ch=39。(39。：則將前面剛創(chuàng)建的結點作為雙親結點進棧 ,并置 k=1,表示其后創(chuàng)建的結點將作為這個結點的左孩子結點； ② 若 ch=39。)39。：表示棧中結點的左右孩子結點處理完畢 ,退棧； ③ 若 ch=39。,39。：表示其后創(chuàng)建的結點為右孩子結點； ④ 其他情況 ,表示要創(chuàng)建一個結點 ,并根據(jù) k值建立它與棧中結點之間的聯(lián)系 ,當 k=1時 ,表示這個結點作為棧中結點的左孩子結點 ,當 k=2時 ,表示這個結點作為棧中結點的右孩子結點 。 如此循環(huán)直到 str處理完畢 。 算法中使用一個棧 St保存雙親結點 ,top為其棧指針 ,k指定其后處理的結點是雙親結點 (保存在棧中 )的左孩子結點 (k=1)還是右孩子結點 (k=2)。 void CreateBTNode(BTNode * amp。b,char *str) { BTNode *St[MaxSize],*p=NULL。 int top=1,k,j=0。 char ch。 b=NULL。 /*建立的二叉樹初始時為空 */ ch=str[j]。 while (ch!=39。\039。) /*str未掃描完時循環(huán) */ { switch(ch) { case 39。(39。:top++。St[top]=p。k=1。 break。 /*為左孩子結點 */ case 39。)39。:top。break。 case 39。,39。:k=2。 break。 /*為孩子結點右結點 */ default:p=(BTNode *)malloc(sizeof(BTNode))。 pdata=ch。plchild=prchild=NULL。 if (b==NULL) /**p為二叉樹的根結點 */ b=p。 else /*已建立二叉樹根結點 */ { switch(k) { case 1:St[top]lchild=p。break。 case 2:St[top]rchild=p。break。 } } } j++。ch=str[j]。 } } 例如 ,對于括號表示串 A(B(D(,G)),C(E,F)),建立二叉樹鏈式存儲結構的過程如下表所示 。 ch 算法執(zhí)行的操作 St中元素 A 建立 A結點 ,b指向該結點 空 ( A結點進棧 ,k=1 A B 建立 B結點 ,因 k=1,將其作為 A結點的左孩子結點 A ( B結點進棧 ,k=1 AB D 建立 D結點 ,因 k=1,將其作為 B結點的左孩子結點 AB ch 算法執(zhí)行的操作 St中元素 ( D結點進棧 ,k=1 ABD , k=2 ABD G 建立 G結點 ,因 k=2,將其作為 D結點的右孩子結點 ABD ) 退棧一次 AB ) 退棧一次 A , k=2 A C 建立 C結點 ,因 k=2,將其作為 A結點的右孩子結點 A ( C結點進棧 ,k=1 AC E 建立 E結點 ,因 k=1,將其作為 C結點的左孩子結點 AC , k=2 AC ch 算法執(zhí)行的操作 St中元素 F 建立 F結點 ,因 k=2,將其作為 C結點的右孩子結點 AC ) 退棧一次 A ) 退棧一次 空 ch掃描完畢 算法結束 A B ∧ C ∧ D ∧ E ∧ ∧ F ∧ ∧ G ∧ 生成的二叉樹＝＞ (2) 查找結點 FindNode(*b,x) 采用先序遍歷遞歸算法查找值為 x的結點 。 找到后返回其指針 ,否則返回 NULL。 算法如下： BTNode *FindNode(BTNode *b,ElemType x) { BTNode *p。 if (b==NULL) return NULL。 else if (bdata==x) return b。 else { p=FindNode(blchild,x)。 if (p!=NULL) return p。 else return FindNode(brchild,x)。 } } (3) 找孩子結點 LchildNode(p)和 RchildNode(p) 直接返回 *p結點的左孩子結點或右孩子結點的指針 。 算法如下： BTNode *LchildNode(BTNode *p) { return plchild。 } BTNode *RchildNode(BTNode *p) { return prchild。 } (4) 求高度 BTNodeDepth(*b) 求二叉樹的高度的遞歸模型 f()如下： f(NULL)=0 f(b)=MAX{f(blchild),f(brchild)}+1 其他情況 對應的算法如下： int BTNodeDepth(BTNode *b) { int lchilddep,rchilddep。 if (b==NULL) return(0)。 /*空樹的高度為 0*/ else { lchilddep=BTNodeDepth(blchild)。 /*求左子樹的高度為 lchilddep*/ rchilddep=BTNodeDepth(brchild