【正文】 A D E B C F ? ? ? ? ? ? ? root lchild data rchild 結(jié)點結(jié)構(gòu) : （ 1） 二叉鏈表 typedef struct BiTNode { // 結(jié)點結(jié)構(gòu) TElemType data。 // 左右孩子指針 } BiTNode, *BiTree。 struct TriTNode *lchild, *rchild。 //雙親指針 } TriTNode, *TriTree。 一、問題的提出 “訪問 ”的含義可以很廣，如：輸出結(jié) 點的信息等。 而二叉樹是非線性結(jié)構(gòu)，每個結(jié)點 有兩個后繼，則存在如何遍歷即按什么 樣的 搜索路徑 遍歷的問題。 二、先左后右的遍歷算法 先 （根）序的遍歷算法 中 （根）序的遍歷算法 后 （根）序的遍歷算法 若二叉樹為空樹，則空操作；否則， （ 1）訪問根結(jié)點； （ 2）先序遍歷左子樹； （ 3）先序遍歷右子樹。 中（根）序的遍歷算法： 若二叉樹為空樹，則空操作；否則， （ 1）后序遍歷左子樹； （ 2）后序遍歷右子樹； （ 3）訪問根結(jié)點。 e)) { // 先序遍歷二叉樹 if (T) { visit(Tdata)。 // 遍歷左子樹 Preorder(Trchild, visit)。 push(S,T)。amp。 pop(S,p)。 if(!visit(pdata)) return ERROR。} return OK。 p=T。p=plchild。 if(!visit(pdata) ) return ERROR。 } 五 、 遍歷算法的應(yīng)用舉例 統(tǒng)計二叉樹中葉子結(jié)點的個數(shù) (先序遍歷 ) 求二叉樹的深度 (后序遍歷 ) 建立二叉樹 統(tǒng)計二叉樹中葉子結(jié)點的個數(shù) 算法基本思想 : 先序 (或中序或后序 )遍歷二叉樹，在遍歷過程中查找葉子結(jié)點，并計數(shù)。 void CountLeaf (BiTree T, intamp。amp。 // 對葉子結(jié)點計數(shù) CountLeaf( Tlchild, count)。 } // if } // CountLeaf 求二叉樹的深度 (后序遍歷 ) 算法基本思想 : 從二叉樹深度的定義可知， 二叉樹的深度應(yīng)為其左、右子樹深度的最大值加 1。 首先分析 二叉樹的深度 和它的 左 、 右子樹深度 之間的關(guān)系。 else { depthLeft = Depth( Tlchild )。 depthval = 1 + (depthLeft depthRight ? depthLeft : depthRight)。 } 不同的定義方法相應(yīng)有不同的存儲結(jié)構(gòu)的建立算法 建立二叉樹 （ 1） 以字符串的形式 根 左子樹 右子樹 定義一棵二叉樹 例如 : A B C D 以空白字符“ ”表示 A(B( ,C( , )),D( , )) 空樹 只含一個根結(jié)點的二叉樹 A 以字符串“ A ” 表示 以下列字符串表示 Status CreateBiTree(BiTree amp。ch)。 39。 else { if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) exit(OVERFLOW)。 // 生成根結(jié)點 CreateBiTree(Tlchild)。 // 構(gòu)造右子樹 } return OK。ch)。 else { 建根結(jié)點 。 遞歸建右子樹 。ch)。 暫存 。 若當(dāng)前的優(yōu)先數(shù)“高”，則暫存 。 } void CrtExptree(BiTree amp。 Push(S, ??)。 p = exp。 while (!(GetTop(S)==?? amp。 ch==??)) { if (!IN(ch, OP)) CrtNode( t, ch )。 ch = *p。 } // CrtExptree … … switch (ch) { case ?(? : Push(S, ch)。 case ?)? : Pop(S, c)。 // 建二叉樹并入棧 Pop(S, c) } break。amp。 Pop(S, c)。 break。 T,char ch) { T=(BiTNode*)malloc(sizeof(BiTNode))。 Tlchild = Trchild = NULL。 } 建子樹的算法為： void CrtSubtree (Bitreeamp。 Tdata = c。 Trchild = rc。 Tlchild = lc。 } 僅知二叉樹的先序序列“ abcdefg” 不能唯一 確定一棵二叉樹， （ 3）由二叉樹的先序和中序序列建樹 如果同時已知二叉樹的中序序列“ cbdaegf”， 則會如何？ 二叉樹的先序序列 二叉樹的中序序列 左子樹 左子樹 右子樹 右子樹 根 根 a b c d e f g c b d a e g f 例如 : a a b b c c d d e e f fg a b c d e f g ^ ^ ^ ^ ^ ^ ^ ^ 先序序列中序序列 void CrtBT(BiTreeamp。 else { k=Search(ino, pre[ps])。 else { } } // } // CrtBT … … T=(BiTNode*)malloc(sizeof(BiTNode))。 if (k==is) TLchild = NULL。 if (k=is+n1) TRchild = NULL。 遍歷二叉樹的結(jié)果是， 求得結(jié)點的一個線性序列。 若該結(jié)點的右子樹不空， 則 rchild域的指針指向其右子樹， 且右標(biāo)志域的值為 “ 指針 Link”； 否則， rchild域的指針指向其“后繼”， 且右標(biāo)志的值為“ 線索 Thread”。 樹的三種存儲結(jié)構(gòu) 一、 雙親表示法 二、 孩子鏈表表示法 三、 樹的二叉鏈表 (孩子 兄弟） 存儲表示法 樹和森林 A B C D E F G 0 A 1 1 B 0 2 C 0 3 D 0 4 E 2 5 F 2 6 G 5 r=0 n=6 data parent 一、雙親表示法 : typedef struct PTNode { Elem data。 // 雙親位置域 } PTNode。 int r, n。 樹結(jié)構(gòu) : A B C D E F G 0 A 1 1 B 0 2 C 0 3 D 0 4 E 2 5 F 2 6 G 5 r=0 n=6 data firstchild 1 2 3 4 5 6 二、孩子鏈表表示法 : 4 typedef struct CTNode { int child。 } *ChildPtr。 ChildPtr firstchild。 雙親結(jié)點結(jié)構(gòu) data firstchild typedef struct { CTBox nodes[MAX_TREE_SIZE]。 // 結(jié)點數(shù)和根結(jié)點的位置 } CTree。 struct CSNode *firstchild, *nextsibling。 C語言的類型描述 : 結(jié)點結(jié)構(gòu) : firstchild data nextsibling 森林和二叉樹的