【正文】 H J M = 雙親在同一層的結(jié)點(diǎn) A B C D E F G H I J K L M 結(jié)點(diǎn) A的度： 結(jié)點(diǎn) B的度： 結(jié)點(diǎn) M的度： 葉子： 結(jié)點(diǎn) A的孩子： 結(jié)點(diǎn) B的孩子： 結(jié)點(diǎn) I的雙親： 結(jié)點(diǎn) L的雙親： 結(jié)點(diǎn) B， C， D為兄弟 結(jié)點(diǎn) K， L為兄弟 樹的度： 結(jié)點(diǎn) A的層次： 結(jié)點(diǎn) M的層次： 樹的深度： 結(jié)點(diǎn) F， G為堂兄弟 結(jié)點(diǎn) A是結(jié)點(diǎn) F， G的祖先 結(jié)點(diǎn) B的子孫： 3 2 0 B， C， D E， F 3 K， L， F， G， M， I ， J D E 1 4 例 E， K， L， F 4 對比 樹形結(jié)構(gòu) 和 線性結(jié)構(gòu) 的結(jié)構(gòu)特點(diǎn) 線性結(jié)構(gòu) 樹形結(jié)構(gòu) 第一個(gè)數(shù)據(jù)元素 (無前驅(qū) ) 根結(jié)點(diǎn) (無前驅(qū) ) 最后一個(gè)數(shù)據(jù)元素 (無后繼 ) 多個(gè)葉子結(jié)點(diǎn) (無后繼 ) 其它數(shù)據(jù)元素 (一個(gè)前驅(qū)、一個(gè)后繼 ) 其它數(shù)據(jù)元素 (一個(gè)前驅(qū)、多個(gè)后繼 ) 二叉樹的類型定義及性質(zhì) 二叉樹 或?yàn)?空樹 ；或是由一個(gè) 根結(jié)點(diǎn)加上 兩棵 分別稱為 左子樹 和 右子樹 的、互不相交的 二叉樹 組成。 森林： 是 m（ m≥ 0）棵互 不相交的樹的集合。 兄弟 結(jié)點(diǎn)：同一雙親的孩子結(jié)點(diǎn)。 A B C D E F G H I J M K L 定義根結(jié)點(diǎn)的層次為 1,第 t層結(jié)點(diǎn)子樹的根結(jié)點(diǎn)的層次為 t+1。 (結(jié)點(diǎn)擁有子樹數(shù)目 ) 樹中所有結(jié)點(diǎn)的度的最大值。T) // 銷毀樹結(jié)構(gòu) DeleteChild(amp。T, definition) // 按定義構(gòu)造樹 Assign(T, cur_e, value) // 給當(dāng)前結(jié)點(diǎn)賦值 InsertChild(amp。 ?A 只有根結(jié)點(diǎn)的 樹 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ù)元素的集合。 樹的類型定義和基本術(shù)語 二叉樹的類型定義及性質(zhì) 二叉樹的存儲結(jié)構(gòu) 二叉樹的遍歷 線索二叉樹 樹和森林 哈夫曼樹與哈夫曼編碼 樹的類型定義和基本術(shù)語 ? 樹的定義 ? 定義：樹 (Tree)是 n(n≥0)個(gè)結(jié)點(diǎn)的有限集 T， 其中： – 當(dāng) n≥1時(shí)，有且僅有一個(gè)特定的結(jié)點(diǎn)，稱為樹的 根 (Root)， – 當(dāng) n 1時(shí)，其余結(jié)點(diǎn)可分為 m(m0)個(gè) 互不相交 的有限集 T1,T2,…… Tm，其中每一個(gè)集合本身又是一棵樹，稱為根的 子樹 (SubTree)。 (1) 在 D中存在唯一的稱為根的數(shù)據(jù)元素 root, (2) 當(dāng) n1時(shí)，其余結(jié)點(diǎn)可分為 m (m0)個(gè)互 不相交的有限集 T1, T2, … , Tm, 其中每一 個(gè)子集本身又是一棵樹 ,稱為根 root的子樹。T, amp。T, amp。 度為零的結(jié)點(diǎn)。 樹中葉子結(jié)點(diǎn)所在的最大層次。 祖先 結(jié)點(diǎn)：從根結(jié)點(diǎn)到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)。 A root B E F K L C G D H I J M F 子樹之間不存在確定的次序關(guān)系 （ 能互換 ） 。 A B C D E F G H K 根結(jié)點(diǎn) 左子樹 右子樹 二叉樹的五種基本形態(tài)： 空樹 只含根結(jié)點(diǎn) L R 右子樹為空樹 左子樹為空樹 左右子樹均不為空樹 二叉樹特點(diǎn)： ?每個(gè)結(jié)點(diǎn)至多有二棵子樹 (即不存在度大于 2的結(jié)點(diǎn) )。 Value(T, e)。 LeftSibling(T, e)。 PreOrderTraverse(T, Visit()) // 先序遍歷 。 InitBiTree(amp。 CreateBiTree(amp。 ClearBiTree(amp。 DeleteChild(T, p, LR)。 ?性質(zhì) 2 ： 深度為 k 的二叉樹上至多含 2k1 個(gè)結(jié)點(diǎn) . (k≥ 1) 證明： 基于上一條性質(zhì)，深度為 k 的二叉樹上的結(jié)點(diǎn)數(shù)至多為 20+21+ ? ? ? ? ? ? +2k1 = 2k1 ? 性質(zhì) 3 ： 對任何一棵二叉樹，若它含有 n0 個(gè)葉子結(jié)點(diǎn)、n2 個(gè)度為 2 的結(jié)點(diǎn)，則必存在關(guān)系式： n0 = n2+1 證明： 設(shè) 二叉樹上結(jié)點(diǎn)總數(shù) n = n0 + n1 + n2 又 二叉樹上分支總數(shù) b = n1 + 2n2 而 b = n 1 由此， n1 + 2n2 = n0 + n1 + n2 1 即 n0 = n2 + 1 兩類 特殊 的二叉樹： 滿二叉樹 ： 指的是深度為 k且含有 2k1個(gè)結(jié)點(diǎn)的二叉樹。 二叉樹的存儲結(jié)構(gòu) 二、 二叉樹的鏈?zhǔn)酱鎯Ρ硎? 一、 二叉樹的順序存儲表示 define MAX_TREE_SIZE 100 // 二叉樹的最大結(jié)點(diǎn)數(shù) typedef TElemType SqBiTree[MAX_TREE_SIZE]。 a b c d e f g a b c d e 0 0 0 0 f g 1 2 3 4 5 6 7 8 9 10 11 二、二叉樹的鏈?zhǔn)酱鎯Ρ硎? 1. 二叉鏈表 2．三叉鏈表 3．線索鏈表 typedef struct BiTNode { // 結(jié)點(diǎn)結(jié)構(gòu) TElemType data。 struct TriTNode *lchild, *rchild, *parent。 即找一個(gè)完整而有規(guī)律的走法，得到樹中所有結(jié)點(diǎn)的一個(gè)線性排列。 對 “ 二叉樹 ” 而言 ， 可以有三條搜索路徑： ?1． 先上后下 的按層次遍歷； ?2． 先左 （ 子樹 ） 后右 （ 子樹 ） 的遍歷； ?3． 先右 （ 子樹 ） 后左 （ 子樹 ） 的遍歷 。 后 （根） 序的遍歷算法： A D B C L R D L R D L R D A D C L R D 后序遍歷序列： D B C A 后序遍歷 : B A B C D E F G H K 分 析 ： 先序序列： 中序序列： 后序序列： A B C D E F G H K B D C A E H G K F D C B H K G F E A 作業(yè) 三、算法的遞歸描述 void PreOrder (BiTree T, void( *visit)(TElemTypeamp。// 遍歷右子樹 } } void pre(BiTree t) { if (t!=NULL) { printf (%d\t,tdata)。 返回 返回 pre(T R)。 pre(T L)。 pre(T L)。 e)) { InitStack(S)。 } // 根指針進(jìn)棧，遍歷左子樹 else { //根指針退棧，訪問根結(jié)點(diǎn)，遍歷右子樹 Pop(S,p)。 }// 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é)點(diǎn) if (p) { Push(S,p)。 p=prchild。 遍歷左子樹 if( !visit(pdata) ) return ERROR。 } // 根指針進(jìn)棧，遍歷左子樹 else { //根指針退棧，訪問根結(jié)點(diǎn)， Pop(S,p)。 p=plchild。 } //else } // while void PreOrderTraverse (BiTree T, void (*visit) (TelemTypeamp。 // 訪問根結(jié)點(diǎn) Push(S,p)。 } //else } // while return OK。 else return(Preorder_Seek (Trchild, x, p)) 。 void CountLeaf (BiTree T, intamp。 // 對葉子結(jié)點(diǎn)計(jì)數(shù) CountLeaf( Tlchild, count)。amp。 return (m+n)。 int TreeDepth (BiTree T ){ // 返回二叉樹的深度 if ( !T ) depth = 0。 } return depth。 if (ch==39。 Tdata = ch。 } // CreateBiTree A B C D B 上頁算法執(zhí)行過程舉例如下 : A T B C D ^ ^ ^ ^ ^ A B C ? ? D E ? G ? ? F ? ? ? 練習(xí)：按先序遍歷序列建立二叉樹的二叉鏈表， 已知先序序列為： A B C D E F G 按給定的表達(dá)式建相應(yīng)二叉樹 ? 由前綴表示式建樹 例如：已知表達(dá)式的前綴表示式 + a b c / d e ? 由原表達(dá)式建樹 例如：已知表達(dá)式 (a+b) c – d/e 對應(yīng)前綴表達(dá)式 + a b c / d e的二叉樹 a b c d e + / 特點(diǎn) ： 操作數(shù) 為 葉子 結(jié)點(diǎn)， 運(yùn)算符 為 分支 結(jié)點(diǎn) scanf(amp。 遞歸建左子樹 。 if (In(ch, 字母集 )) { 建葉子結(jié)點(diǎn) 。 否則建子樹 。 InitStack(PND)。amp。} } // while Pop(PND, T)。 while (c!= ?(? ) { CrtSubtree( t, c)。 ( precede(c,ch))) { CrtSubtree( t, c)。 //棧頂元素 c優(yōu)先級 高于 當(dāng)前運(yùn)算符 ch 建葉子結(jié)點(diǎn)的算法為： void CrtNode(BiTreeamp。 Push( PND, T )。 Pop(PND, rc)。 Push(PND, T)。 ： abc， 問有幾種形態(tài)的二叉樹可得到此遍歷結(jié)果？ 。 與其相應(yīng)的二叉樹，稱作 “ 線索二叉樹 ” 包含