【正文】 樹的三種存儲結(jié)構(gòu) 樹、森林和二叉樹的對應(yīng)關(guā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 data parent 一、雙親表示法 : (順序存儲結(jié)構(gòu) ) 利用每個結(jié)點至多有一個雙親的性質(zhì)。 樹結(jié)構(gòu) : r=0 n=7 0 A 1 1 B 0 2 C 0 3 D 0 4 E 2 5 F 2 6 G 5 A B C D E F G 二、孩子鏈表表示法 : 樹中每個結(jié)點可能包含多棵子樹， 所以可以采用 多叉鏈表 表示。較實用的方法是 為樹中每個結(jié)點建立一個孩子鏈表 ，而 n個頭指針又組成一個線性表，為了便于查找，可采用順序存儲結(jié)構(gòu)。 // 孩子鏈的頭指針 } CTBox。 練習(xí)： A B C E D F G I H 孩子 兄弟表示法 樹、森林和二叉樹的對應(yīng)關(guān)系 (一 ) 樹與二叉樹之間的轉(zhuǎn)換 二叉樹和樹都可以用二叉鏈表作為存儲結(jié)構(gòu)。 森林轉(zhuǎn)換成二叉樹的規(guī)則 H D G F C I E B J 如： J H D G F C I E B J H D G F I E B C H D G F C I E B J 以上我們給出了：樹和森林轉(zhuǎn)化為二叉樹的規(guī)則， 那么二叉樹如何轉(zhuǎn)化為樹或森林？看下面例子： 二叉樹轉(zhuǎn)換成樹或森林的規(guī)則 若結(jié)點 x是其雙親 p的左孩子，則把 x的右孩子、右孩子的右孩子、 …… 都與 p用線連起來。 否則， 由 ( t11, t12, …, t 1m ) 對應(yīng)得到二叉樹的左子樹 LB。 作業(yè)： 。 先序遍歷 森林中 (除第一棵樹之外 )其 余樹構(gòu)成的森林。 樹、森林的遍歷和二叉樹遍歷的對應(yīng)關(guān)系 ？ 先根遍歷 后根遍歷 樹 二叉樹 森林 先序遍歷 先序遍歷 中序遍歷 中序遍歷 A B C D E F G H I J K L M N O 先序遍歷： 后序遍歷： 層次遍歷： A B E F I G C D H J K L N O M E I F G B C J K N O L M H D A A B C D E F G H I J K L M N O ? 作業(yè)：寫出下面樹的先根、后根及按層次遍歷的遍歷序列。 可以分解成三部分： 森林 若森林不空，則 訪問 森林中第一棵樹的根結(jié)點 。 T1 T11,T12,…,T 1m T2,…,T n LBT root 森林 二叉樹 RBT 由此，樹和森林的各種操作均可與二叉樹的操作相對應(yīng)。 ? 可以給上述轉(zhuǎn)換方法作如下形式定義： 由森林轉(zhuǎn)換成二叉樹 的 轉(zhuǎn)換規(guī)則為 : 若 F = Φ，則 B = Φ。 (因為樹根沒有兄弟 ) (二 ) 森林與二叉樹之間的轉(zhuǎn)換 在把森林轉(zhuǎn)換為二叉樹時，可以把森林中除第一棵樹以外的其它所有樹的根結(jié)點看作第一棵樹根結(jié)點的 兄弟 結(jié)點。 } CSNode, *CSTree。 孩子結(jié)點結(jié)構(gòu) : child nextchild 孩子鏈表 C語言的類型描述 : typedef struct { TElemType data。雖然節(jié)省了空間，但給運算帶來了不便。 int r, n。 線索樹的優(yōu)缺點： 優(yōu)點： 線索樹由于含有其前驅(qū)、后繼的 信息，因此在進行各種操作時顯 得比較方便。 qlchild=p。 // 右子樹線索化 } // if } // InThreading 練習(xí)：中序線索化二叉樹： c d e f + / a b 中序遍歷序列： a+b*cde/f nil nil 提高： 中序線索樹中插入結(jié)點。把中序遞歸遍歷算法中的Visit(pdata)改為 設(shè)置線索 的語句。 //最左下的結(jié)點是中序遍歷的 Visit(pdata)。 //從 *p的右孩子開始查找 while (!qltag) q=qlchild。 例如 : 對中序線索化鏈表的遍歷算法。 struct BiThrNode *lchild, *rchild。 ： abc， 問有幾種形態(tài)的二叉樹可得到此遍歷結(jié)果？ 。 Pop(PND, rc)。 //棧頂元素 c優(yōu)先級 高于 當(dāng)前運算符 ch 建葉子結(jié)點的算法為： void CrtNode(BiTreeamp。 while (c!= ?(? ) { CrtSubtree( t, c)。amp。 否則建子樹 。 遞歸建左子樹 。 Tdata = ch。 } return depth。 return (m+n)。 // 對葉子結(jié)點計數(shù) CountLeaf( Tlchild, count)。 else return(Preorder_Seek (Trchild, x, p)) 。 // 訪問根結(jié)點 Push(S,p)。 p=plchild。 遍歷左子樹 if( !visit(pdata) ) return ERROR。 }// InOrderTraverse 四、中序遍歷算法的非遞歸描述 非遞歸算法的執(zhí)行過程 A B C D E F G p i A (1) A B C D E F G p i A B (2) A B C D E F G p i A B C (3) p=NULL pC p=NULL A B C D E F G i A B 訪問： C (4) while ( p||!StackEmpty(S) ){ // 找到最左下的結(jié)點 if (p) { Push(S,p)。 e)) { InitStack(S)。 pre(T L)。// 遍歷右子樹 } } void pre(BiTree t) { if (t!=NULL) { printf (%d\t,tdata)。 對 “ 二叉樹 ” 而言 ， 可以有三條搜索路徑： ?1． 先上后下 的按層次遍歷； ?2． 先左 （ 子樹 ） 后右 （ 子樹 ） 的遍歷； ?3． 先右 （ 子樹 ） 后左 （ 子樹 ） 的遍歷 。 struct TriTNode *lchild, *rchild, *parent。 二叉樹的存儲結(jié)構(gòu) 二、 二叉樹的鏈?zhǔn)酱鎯Ρ硎? 一、 二叉樹的順序存儲表示 define MAX_TREE_SIZE 100 // 二叉樹的最大結(jié)點數(shù) typedef TElemType SqBiTree[MAX_TREE_SIZE]。 DeleteChild(T, p, LR)。 CreateBiTree(amp。 PreOrderTraverse(T, Visit()) // 先序遍歷 。 Value(T, e)。 A root B E F K L C G D H I J M F 子樹之間不存在確定的次序關(guān)系 （ 能互換 ） 。 樹中葉子結(jié)點所在的最大層次。T, amp。 (1) 在 D中存在唯一的稱為根的數(shù)據(jù)元素 root, (2) 當(dāng) n1時，其余結(jié)點可分為 m (m0)個互 不相交的有限集 T1, T2, … , Tm, 其中每一 個子集本身又是一棵樹 ,稱為根 root的子樹。 ?A 只有根結(jié)點的 樹 A B C D E F G H I J K L M 有子樹的 樹 根 子 樹 A B C D E F G H I J M K L A( ) T1 T3 T2 樹根 B(E, F(K, L)), C(G), D(H, I, J(M)) 數(shù)據(jù)對象 D： D是具有相同特性的數(shù)據(jù)元素的集合。T) // 銷毀樹結(jié)構(gòu) DeleteChild(amp。 A B C D E F G H I J M K L 定義根結(jié)點的層次為 1,第 t層結(jié)點子樹的根結(jié)點的層次為 t+1。 森林： 是 m（ m≥ 0）棵互 不相交的樹的集合。 否 練習(xí)：具有 3個結(jié)點的二叉樹有多少種？ 二叉樹的主要基本操作 ： 查 找 類 插 入 類 刪 除 類 ADT BinaryTree： P121 Root(T)。 BiTreeDepth(T)。e, value)。T)。 (2) 若 2in，則該結(jié)點無左孩子， 否則，編號為 2i 的結(jié)點為其 左孩子 結(jié)點； (3) 若 2i+1n，則該結(jié)點無右孩子結(jié)點， 否則，編號為 2i+1 的結(jié)點為其 右孩子 結(jié)點 。 C 語言的類型描述如下 : 1. 二叉鏈表 lchild data rchild 結(jié)點結(jié)構(gòu) : A D E B C F ? ? ? ? ? ? ? root A B D C F E 在有 n個結(jié)點的二叉鏈表中，有 ？ 個空指針域 n+1 typedef struct TriTNode { // 結(jié)點結(jié)構(gòu) TElemType data。而二叉樹是非 線性結(jié)構(gòu)， 每個結(jié)點有兩個后繼 ， 則存在 如何遍歷 即按什么樣的 搜索 路徑 遍歷的問題。 // 遍歷左子樹 PreOrder(Trchild, Visit)。 T A printf(A)。 先序序列： A B D C 遞歸算法的執(zhí)行過程 T a b c d e + / 如圖二叉樹表示表達式 : ( a + b ) c – d / e 二叉樹的先序遍歷序列為： – + a b c / d e 二叉樹的中序遍歷序列為： a + b c – d / e 二叉樹的后序遍歷序列為： a b + c d e / – 前綴表達式 中綴表達式 后綴表達式 二叉樹與表達式 void InOrderTraverse (BiTree T, void (*visit) (TelemTypeamp。 } //else } // while return OK。 } // 根指針進棧，遍歷左子樹 else { //根指針退棧，訪問根結(jié)點， Pop(S,p)。