【正文】 K， L） ， F） ， C（ G） ， D（ H（ M） ， I））） 167。 樹的邏輯表示 ４、凹式表示法 層次表示 。 對森林加上一個結(jié)點，并從該結(jié)點引邊到各樹的根結(jié)點就變成了森林。我們所講的樹都是有向的 。 ● 結(jié)點的度 : 結(jié)點擁有子樹的數(shù)目 ● 葉結(jié)點 : 度為零的結(jié)點 ● 分枝結(jié)點 : 度非零的結(jié)點 ● 樹的度 : 樹中各結(jié)點度的最大值 ● 孩子 : 樹中某個結(jié)點的子樹的根 ● 雙親 : 結(jié)點的直接前驅(qū) ● 兄弟 : 同一雙親的孩子互稱兄弟 ● 祖先 : 從根結(jié)點到某結(jié)點 j 路徑上的所有結(jié)點 （不包括指定結(jié)點）。T,amp。T,amp。T,F) 按 F的定義生成樹 ClearTree(amp。T) 初始化 DestroyTree(amp。 Ｔ 1={B,E,F,K,L} Ｔ 2={C,G} Ｔ 3={D,H,I,J,K} T1,T2,T3都是根 A的子樹，它們本身又是一棵樹。即非空樹是由若干棵子樹組成，而子樹又可以由若干棵更小的子樹組成。 ⑵當 n1時，其余結(jié)點分為ｍ（ｍ ≥ 0）個互不相交的子集 T1， T2， … ， Tm。 b. 樹是 n(n≥0) 個結(jié)點組成的有限集合。 ⑵當 n1時，其余結(jié)點有且僅有一個直接前驅(qū)。 { } (樹是 n(n≥1) 個結(jié)點組成的有限集合。 樹是一種以分支關(guān)系定義的層次結(jié)構(gòu)。第六章 樹和二叉樹 樹是計算機算法最重要的非線性結(jié)構(gòu)。 樹中每個數(shù)據(jù)元素至多有一個直接前驅(qū)，但可以有多個直接后繼。 樹的基本概念 一、樹（ Tree）的定義 n(≥0) 結(jié)點組成的有限集合。 {}) 在任意一棵非空樹中： ⑴有且僅有一個沒有前驅(qū)的結(jié)點 根 (root)。 ⑶所有結(jié)點都可以有０個或多個后繼。 在任意一棵非空樹中： ⑴有一個特定的稱為根（ root）的結(jié)點。 每個集合本身又是一棵樹，并且稱為根的子樹（ subtree） 樹的固有特性 遞歸性。 樹的基本概念 （ 3）中有 13個結(jié)點， 其中Ａ是樹根，其余結(jié)點分成三個互不相交的子集。 T1:根 B {E,K,L} {F} 根 E {k} {L} T2:根 C {G} T3:根 D {H,M} {I} {J} 根 H {M} T=Null ⑴ A T ⑵ A B C D E F G I J H T ⑶ K L M 樹的基本操作 二、樹的基本操作 InitTree(amp。T) 撤消樹 creatTree(amp。T) 清除 TreeEmpty(T) 判樹空 TreeDepth(T) 求樹的深度 Root(T) 返回根結(jié)點 Parent(T,x) 返回結(jié)點 x 的雙親 Child(T,x,i) 返回結(jié)點 x 的第 i 個孩子 InsertChild(amp。p,i,x) 把 x 插入到 P的第 i棵子樹處 1 DeleteChild(amp。p,i) 刪除結(jié)點 P的第 i棵子樹 1 traverse(T) 遍歷 樹的基本術(shù)語 樹的結(jié)點： 包含一個數(shù)據(jù)元素及若干指向子樹的分支。 ● 子孫 : 某結(jié)點的子樹中的任一結(jié)點稱為該結(jié)點的子孫 ● 結(jié)點層次 : 從根結(jié)點到某結(jié)點 j 路徑上結(jié)點的數(shù)目（包括結(jié)點 j） ● 樹的深度 : 樹中結(jié)點的最大層次 ● 有向樹 ：結(jié)點間的連線是有向的。 ● 有序樹 : 若樹中結(jié)點的各子樹從左到右是有次序的 ,稱該樹為有序樹 ,否則為無序樹 ● 森林 : 由 m 棵互不相交的樹構(gòu)成 F=(T1,T2,.......Tm) 一棵樹去掉根結(jié)點后就表成了森林。 樹的邏輯表示 １、結(jié)點和結(jié)點間的連線表示法 A B C D E F G I J H T K L M A B E K L F C G D H M I J ２、文式圖表示法 集合嵌套。 A B E K L F C G D H M I J ３、廣義表表示法 遞歸表示。 二叉樹 一、二叉樹的定義 二叉樹是ｎ（ｎ ≥ 0）個結(jié)點的有限集合。 結(jié)點的度最大為２。 二叉樹可以有五種基本形態(tài)： A Btree Btree=Null A Btree A Btree A Btree 二叉樹的基本運算 ?initBiTree(amp。T) 生成一棵二叉樹樹 ?InsertLChild(amp。T,y,x) 把 x作為 y的右子樹插入 ?DelLChild(amp。T,y) 刪除結(jié)點 y的右子樹 ?Traverse(T) 遍歷二叉樹 ?clearBiTrr(amp。 【 性質(zhì) 2】 深度為Ｋ的二叉樹至多有２ k1個結(jié)點 (K0)。 特點： 每一層上的結(jié)點數(shù)都達到最大。 葉子結(jié)點只可能在最后一層。 完全二叉樹：深度為Ｋ的ｎ個結(jié)點的二叉樹，當且僅當每個結(jié)點都與深度為Ｋ的滿二叉樹中編號為１至ｎ的結(jié)點一一對應(yīng)。 對任一結(jié)點，若其右分支下的子孫的最大層次為 L，則其左分支下的最大層次為 L或 L+1。 證明：根據(jù)完全二叉樹的性質(zhì)有： （ 2k1 –1） +1 ≤n ≤2k1 即 2k1≤n≤2k1 2k1 ≤ n 2k 有： k= ?log2n?+1 2k1n+1≤2k 有： k= ?log2n+1? 【 性質(zhì) 5】 具有ｎ個結(jié)點的完全二叉樹具有如下特征： ① i=1 根結(jié)點 ， 無雙親