【正文】 雙親在同一層的結(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 對(duì)比 樹形結(jié)構(gòu) 和 線性結(jié)構(gòu) 的結(jié)構(gòu)特點(diǎn) 線性結(jié)構(gòu) 樹形結(jié)構(gòu) 第一個(gè)數(shù)據(jù)元素 (無(wú)前驅(qū) ) 根結(jié)點(diǎn) (無(wú)前驅(qū) ) 最后一個(gè)數(shù)據(jù)元素 (無(wú)后繼 ) 多個(gè)葉子結(jié)點(diǎn) (無(wú)后繼 ) 其它數(shù)據(jù)元素 (一個(gè)前驅(qū)、一個(gè)后繼 ) 其它數(shù)據(jù)元素 (一個(gè)前驅(qū)、多個(gè)后繼 ) 二叉樹的類型定義及性質(zhì) 二叉樹 或?yàn)?空樹 ；或是由一個(gè) 根結(jié)點(diǎn)加上 兩棵 分別稱為 左子樹 和 右子樹 的、互不相交的 二叉樹 組成。 ?二叉樹的子樹有左、右之分，其次序不能任意顛倒。 否 練習(xí)：具有 3個(gè)結(jié)點(diǎn)的二叉樹有多少種？ 二叉樹的主要基本操作 ： 查 找 類 插 入 類 刪 除 類 ADT BinaryTree： P121 Root(T)。 Parent(T, e)。 RightChild(T, e)。 RightSibling(T, e)。 BiTreeDepth(T)。 InOrderTraverse(T, Visit()) // 中序遍歷 。 LevelOrderTraverse(T, Visit()) // 層序遍歷 。T)。e, value)。T, definition)。 p所指結(jié)點(diǎn)的原右或左子樹成為 c的右子樹。T)。T)。 二叉樹 的重要特性 ? 性質(zhì) 1 ： 在二叉樹的第 i 層上至多有 2i1 個(gè)結(jié)點(diǎn)。 二叉樹上每個(gè)結(jié)點(diǎn)至多有兩棵子樹， 則第 i 層的結(jié)點(diǎn)數(shù) = 2i2? 2 = 2i1 。特點(diǎn)： 每一層上的結(jié)點(diǎn)數(shù)都是最 大結(jié)點(diǎn)數(shù) . 完全二叉樹 ： 樹中所含的 n 個(gè)結(jié)點(diǎn)和滿二叉樹中 編號(hào)為 1 至 n 的結(jié)點(diǎn) 一一對(duì)應(yīng)。 (2) 若 2in，則該結(jié)點(diǎn)無(wú)左孩子， 否則，編號(hào)為 2i 的結(jié)點(diǎn)為其 左孩子 結(jié)點(diǎn)； (3) 若 2i+1n，則該結(jié)點(diǎn)無(wú)右孩子結(jié)點(diǎn)， 否則，編號(hào)為 2i+1 的結(jié)點(diǎn)為其 右孩子 結(jié)點(diǎn) 。 // 0號(hào)單元存儲(chǔ)根結(jié)點(diǎn) SqBiTree bt。 特點(diǎn)： 結(jié)點(diǎn)間關(guān)系蘊(yùn)含在其存儲(chǔ)位置中； 浪費(fèi)空間，適于存滿二叉樹和完全二叉樹。 struct BiTNode *lchild, *rchild。 C 語(yǔ)言的類型描述如下 : 1. 二叉鏈表 lchild data rchild 結(jié)點(diǎn)結(jié)構(gòu) : A D E B C F ? ? ? ? ? ? ? root A B D C F E 在有 n個(gè)結(jié)點(diǎn)的二叉鏈表中，有 ？ 個(gè)空指針域 n+1 typedef struct TriTNode { // 結(jié)點(diǎn)結(jié)構(gòu) TElemType data。 // 左右孩子指針、 雙親指針 } TriTNode, *TriTree。 a b c d e f g h 二叉樹的遍歷 一、問題的提出 二、先左后右的遍歷算法 三、算法的遞歸描述 四、中序遍歷算法的非遞歸描述 五、遍歷算法的應(yīng)用舉例 遍歷 ： 順著某一條搜索路徑 巡訪 二叉樹中的結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn) 均被訪問一次 ，而且 僅被訪問一次 。 一、問題的提出 “訪問 ”的含義可以很廣， 如：輸出結(jié)點(diǎn)的信息等。而二叉樹是非 線性結(jié)構(gòu)， 每個(gè)結(jié)點(diǎn)有兩個(gè)后繼 ， 則存在 如何遍歷 即按什么樣的 搜索 路徑 遍歷的問題。 D L R LDR、 LRD、 DLR RDL、 RLD、 DRL 二、先左后右的遍歷算法 先 （根） 序的遍歷算法 中 （根） 序的遍歷算法 后 （根） 序的遍歷算法 根 左 子 樹 右 子 樹 若二叉樹為空樹，則空操作；否則， （ 1）訪問根結(jié)點(diǎn)； （ 2）先序遍歷左子樹； （ 3）先序遍歷右子樹。 中 （根） 序的遍歷算法： A D B C L D R B L D R L D R A D C L D R 中序遍歷序列： B D A C 中序遍歷 : 若二叉樹為空樹，則空操作；否則， （ 1）后序遍歷左子樹； （ 2）后序遍歷右子樹； （ 3）訪問根結(jié)點(diǎn)。 e)) { // 先序遍歷二叉樹 if (T) { Visit(Tdata) 。 // 遍歷左子樹 PreOrder(Trchild, Visit)。 pre(tlchild)。 } } 主程序 Pre( T ) 返回 返回 pre(T R)。 A C B D T B printf(B)。 T A printf(A)。 T D printf(D)。 T C printf(C)。 返回 T 左是空返回 pre(T R)。 先序序列： A B D C 遞歸算法的執(zhí)行過程 T a b c d e + / 如圖二叉樹表示表達(dá)式 : ( a + b ) c – d / e 二叉樹的先序遍歷序列為： – + a b c / d e 二叉樹的中序遍歷序列為： a + b c – d / e 二叉樹的后序遍歷序列為： a b + c d e / – 前綴表達(dá)式 中綴表達(dá)式 后綴表達(dá)式 二叉樹與表達(dá)式 void InOrderTraverse (BiTree T, void (*visit) (TelemTypeamp。 p=T。 p=plchild。 if ( !visit(pdata) ) return ERROR。 } //else } // while return OK。 p=plchild。 遍歷左子樹 if( !visit(pdata) ) return ERROR。 } //else } // while while ( p||!StackEmpty(S) ){ // 找到最左下的結(jié)點(diǎn) if (p) { Push(S,p)。 } // 根指針進(jìn)棧，遍歷左子樹 else { //根指針退棧，訪問根結(jié)點(diǎn)， Pop(S,p)。 p=prchild。 p=plchild。 遍歷左子樹 if( !visit(pdata) ) return ERROR。 } //else } // while P=NULL P=NULL A B C D E F G i A 訪問： C B E G D F pF p=NULL (13) A B C D E F G i 訪問： C B E G D F A p (14) A B C D E F G i 訪問： C B E G D F A p=NULL (15) while ( p||!StackEmpty(S) ){ // 找到最左下的結(jié)點(diǎn) if (p) { Push(S,p)。 } // 根指針進(jìn)棧，遍歷左子樹 else { //根指針退棧，訪問根結(jié)點(diǎn)， Pop(S,p)。 p=prchild。 e)) { InitStack(S)。 while( p || !StackEmpty(S) ){ if (p) {if ( !visit(pdata) ) return ERROR。 p=plchild。 p=prchild。 }// PreOrderTraverse 非遞歸先序遍歷二叉樹 五 、 遍歷算法的應(yīng)用舉例 統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù) 求二叉樹的深度 建立二叉樹的存儲(chǔ)結(jié)構(gòu) 查詢二叉樹中某個(gè)結(jié) 點(diǎn) Status Preorder_Seek (BiTree T, ElemType x, BiTree amp。 return OK,} else { if (Preorder_Seek (Tlchild, x, p) return OK。 }//else }//if else return FALSE。 由此， 需在遍歷算法中增添一個(gè)“計(jì)數(shù)”的參數(shù)， 并將算法中“訪問結(jié)點(diǎn)” 的操作改為 :若是葉子，則計(jì)數(shù)器增 1。 count){ if ( T ) { if ((!Tlchild)amp。 (!Trchild)) count++。 CountLeaf( Trchild, count)。 if (!Tlchild amp。 !Trchild) return 1。 n = CountLeaf( Trchild)。 } //else } // CountLeaf 算法二 123456789 求二叉樹的深度 算法基本思想 : 從二叉樹深度的定義可知， 二叉樹的深度應(yīng)為其左、右子樹深度的最大值加 1。 首先分析 二叉樹的深度 和它的 左 、 右子樹深度 之間的關(guān)系。 else { depthLeft = TreeDepth( Tlchild )。 depth = 1 + (depthLeft depthRight ? depthLeft : depthRight)。 } 算法 建立二叉樹的存儲(chǔ)結(jié)構(gòu) 不同的定義方法對(duì)應(yīng)不同的建立存儲(chǔ)結(jié)構(gòu)的算法 ? 按先序遍歷序列建二叉樹 ? 按給定的表達(dá)式建二叉樹 ? 由先序和中序序列建二叉樹 作業(yè) 以先序遍歷序列的形式 根 左子樹 右子樹 定義一棵二叉樹 例如 : A B C D 以空白字符“ ”表示 A(B( ,C( , )),D( , )) 空樹 只含一個(gè)根結(jié)點(diǎn)的二叉樹 A 以字符串“ A ” 表示 以下列字符串表示 A B C D 算法 Status CreateBiTree(BiTree amp。ch)。 39。 else { if (!(T = new BiTNode)) exit(OVERFLOW)。 // 生成根結(jié)點(diǎn) CreateBiTree(Tlchild)。 // 構(gòu)造右子樹 } return OK。ch)。 else { 建根結(jié)點(diǎn) 。 遞歸建右子樹 。ch)。 入操作數(shù)棧 。 若當(dāng)前的優(yōu)先級(jí)“高”，則入運(yùn)算符棧