【正文】 義成：信息域，左指針域，右指針域。 也可以增加一個指向父親的指針，如下： 圖 6。 5可表示成： Lchild data Rchild Lchild data Parent Rchild A ∧ B ∧ E C ∧ D ∧ ∧ G ∧ ∧ F ∧ 結點定義 ?鏈式存儲結構的結點定義如下： typedef struct BTnode { elementtype data。 struct BTnode *Lchild。 struct BTnode *Rchild。 } BTree。 這里的 elemeenttype可以是任何相應的數(shù)據(jù)類型如 int、 float或 char等。 二叉樹的遍歷 ?二叉樹的遍歷 (Traversal)是指按一定的順序訪問二叉樹的每個結點，且每個結點只被訪問一次的過程。 ?對二叉樹的遍歷過程實際上是將非線性結構的二叉樹中的結點排列成一個線性序列的過程。 ?對于用順序法表示的二叉樹，各結點在數(shù)組中的編號很有規(guī)律，其遍歷較容易進行，但對于用鏈式存儲結構表示的二叉樹，進行遍歷就復雜一些，故本節(jié)僅討論鏈式存儲形式的二叉樹遍歷過程。 ?一個非空的二叉樹由根結點及左、右子樹這三個基本部分組成，因此若能依次遍歷這三部分，便是遍歷了整個二叉樹。 ?在任一給定結點上，可以按某種次序執(zhí)行三個操作：訪問結點本身，遍歷該結點左子樹，遍歷該結點右子樹，操作排列次序： ① 左、根、右；③ 根、左、右；⑤ 左、右、根； ② 右、根、左；④ 根、右、左；⑥ 右、左、根； ?由于實際問題一般都是要求左子樹較右子樹先遍歷，故只采用其中①、③、⑤三種遍歷次序，分別稱為中序遍歷、先序遍歷和后序遍歷。 ?三種遍歷次序以遞歸的形式定義： ? (1) 中序（ Inorder）遍歷 若遍歷的二叉樹為空，執(zhí)行空操作；否則依次執(zhí)行下列操作： 中序遍歷左子樹； 訪問根結點； 中序遍歷右子樹。 ? (2) 先序（ Preorder）遍歷 若遍歷的二叉樹為空，執(zhí)行空操作；否則依次執(zhí)行下列操作： 訪問根結點； 先序遍歷左子樹； 先序遍歷右子樹。 ? (3) 后序（ Postorder）遍歷 若遍歷的二叉樹為空，執(zhí)行空操作；否則依次執(zhí)行下列操作： 后序遍歷左子樹； 后序遍歷右子樹； 訪問根結點。 圖 二叉樹遍歷 ?中序遍歷序列：H， D， I， B， E，A， F， C， G。 ?先序遍歷序列：A， B， D， H， I，E， C， F， G。 ?后序遍歷序列：H， I， D， E， B，F(xiàn)， G， C， A。 ○ B ○C ○ D ○ E ○ F ○ G ○ A ○ H ○ I 先序遍歷遞歸算法 void preorder(btree *BT) { if (BT！ =NULL) { printf(%d,BTdata)。 preorder(BTlchild)。 preorder(BTRchild)。 } } 先序遍歷 非 遞歸算法 ?基本思想 ： 先訪問根結點，并進棧，再訪問左兒子，并進棧 , …… , 直到左兒子為空； 退棧，并訪問其右兒子 , …… ； 重復以上過程，?？諡橹埂? 先序遍歷 非 遞歸算法 define maxsize 二叉樹的結點數(shù) void Nrpreorder(btree *BT) { btree *S[maxsize],*p。 /*定義棧 S[ ]， 中間變量 P */ int top=0。 p=bt。 while ((p!=null)||(top!=0) { while(p!=null) { s[top]=p。 /*若 P非空 ， 則進棧 */ top++。 printf(“ %d” , pdata)。 /*輸出 p=plchild。 /*取其左兒子 */ } 先序遍歷 非 遞歸算法（續(xù)） if (top!=0) { top。 p=s[top]。 /*退棧至 P中 */ p=prchild。 /*取其右兒子 */ } } } 中序遍歷遞歸算法 void inorder(btree *BT) { if (BT！ =NULL) { inorder(BTlchild)。 printf(%d,BTdata)。 inorder(BTRchild)。 } } 中序遍歷 非 遞歸算法 void Nrinorder(btree *BT) { btree *S[maxsize],*p。 /*定義棧 S[ ],中間變量 P */ int top=0。 p=bt。 while ((p!=null) || (top!=0)) { while(p!=null) { s[top]=p。 /*若 P非空 ， 則進棧 */ top++。 p=plchild。 /*取其左兒子 */ } 中序遍歷 非 遞歸算法（續(xù)） if (top!=0) { top。 p=s[top]。 /*退棧至 P中 */ printf(“ %d, pdata)。 p=prchild。 /*取其右兒子 */ } } } 后序遍歷 方法 1: 按照 先根、右子樹、左子樹的順序遍歷二叉樹，得到的結果與后序遍歷的結果相反。 根據(jù)這一事實，可以對二叉樹按以上順序遍歷，之后顛倒過來即可。 ?方法 2： 先序遍歷、中需遍歷時，每個結點只有 1次進棧和 1次出棧。 后序遍歷時，每個結點要 2次進棧，也就是說，每個結點要進 2次，出 2次。 所以，要設一個標志 flag, 以記住是第 1次進棧還是第 2次進棧。該標志與指針同時進出棧。 取左兒子時， flag=0 取右兒子時， flag=1 在第二次出棧時訪問該結點。 例：求二叉樹深度的 遞歸算法 int BTreeheight(Btree *BT) { int hight1。 hight2。 if (BT==null) return(0)。 else { hight1=BTreeheight(btreelchild)。 hight2=BTreeheight(btreerchild)。 if (hight1hight2) return(hight1+1)。 else return(hight2+1)。 } } 求二叉樹深度的 非遞歸 算法 Int depth(btree *BT) { btree *S[ ],*p。 /*定義棧 S[ ],中間變量 P */ p=bt。 /*L[]記錄 S[]中元素對應的層號 int L[ ]。 top=0。 max=0。 level=0。 while ((p!=null) || (top!=0)) { while(p!=null) { level++。 s[top]=p。 L[top]=level。 /*進棧 top++。 p=plchild。 /*取其左兒子 */ } If (levelmax) max=level。 if (top!=0) { top。 p=s[top]。 level=L[top]。 /*退棧 p=prchild。 /*取其右兒子 */ } } return(max)。 } 求二叉樹葉子結點的個數(shù)。 二叉鏈表存儲的二叉樹的層次遍歷算法。 求二叉樹中，每層結點的個數(shù)。 用一維數(shù)組存放一棵完全二叉樹，寫出先序遍歷算法。 線索二叉樹 ?從上節(jié)可知：遍歷二叉