【正文】 操作結(jié)果：返回 T的根 。 操作結(jié)果；返回 e的值 。e， value)； 初始條件；二叉樹(shù) T存在 ， e是 T中某個(gè)結(jié)點(diǎn) 。 Parent(T， e)； 初始條件：二叉樹(shù) T存在 ， e是 T中某個(gè)結(jié)點(diǎn) 。 LeftChild(T， e)； 初始條件：二叉樹(shù) T存在 ， e是 T中某個(gè)結(jié)點(diǎn) 。 RightChild(T， e)； 初始條件：二叉樹(shù) T存在 ， e是 T中某個(gè)結(jié)點(diǎn) 。 基本操作 : LeftSibling(T， e)； 初始條件：二叉樹(shù) T存在， e是 T中某個(gè)結(jié)點(diǎn)。若 e是 T的左孩子或無(wú)左兄弟，則 返回 “ 空 ” 。 操作結(jié)果：返回 e的右兄弟。 基本操作 : InsertChild(T， p， LR， c)； 初始條件：二叉樹(shù) T存在， p指向 T中某個(gè)結(jié)點(diǎn)， LR為 0或 1， 非空二叉樹(shù) c與 T不相交且右子樹(shù)為空。 P所指結(jié)點(diǎn)的原有左或右子樹(shù)則成為 c 的右子樹(shù)。 操作結(jié)果：根據(jù) LR為 0或 1，刪除 T中 p所指結(jié)點(diǎn)的左或右子樹(shù)。 操作結(jié)果：先序遍歷 T中對(duì)每個(gè)結(jié)點(diǎn)一次且僅一次。 操作結(jié)果：中序遍歷 T中每個(gè)結(jié)點(diǎn)一次且僅一次。 操作結(jié)果：后序遍歷 T中每個(gè)結(jié)點(diǎn)一次且僅一次 。 操作結(jié)果：層序遍歷 T中每個(gè)結(jié)點(diǎn)一次且僅一次 . }ADT BinaryTree 性質(zhì) 1: 在二叉樹(shù)的第 i層最多有 2i1 個(gè)結(jié)點(diǎn) (i=1). 用歸納法證明 ： 歸納基 ： 歸納假設(shè)： 歸納證明： i = 1 層時(shí)，只有一個(gè)根結(jié)點(diǎn)， 2i1 = 20 = 1； i=k時(shí)命題成立 。 二叉樹(shù)的性質(zhì) 性質(zhì) 2: 深度為 k的二叉樹(shù)最多有 2k –1個(gè)結(jié)點(diǎn)（ k=1). 證明： 基于性質(zhì) 1，深度為 k 的二叉樹(shù)上的結(jié)點(diǎn)數(shù)最多為 20+21+ ? ? ? ? ? ? +2k1 = 2k1 二叉樹(shù)的性質(zhì) 性質(zhì) 3: 任一二叉樹(shù) , 若葉結(jié)點(diǎn)數(shù)是 n0 , 度為 2的結(jié)點(diǎn)數(shù) 是 n2 ,則 n0 = n2 +1 證明： 設(shè) 二叉樹(shù)上結(jié)點(diǎn)總數(shù) n = n0 + n1 + n2 又 二叉樹(shù)上分支總數(shù) b = n1+2n2 而 b = n1 = n0 + n1 + n2 1 由此， n0 = n2 + 1 二叉樹(shù)的性質(zhì) 滿(mǎn)二叉樹(shù) (Full Binary Tree): 每一層的結(jié)點(diǎn)數(shù)都達(dá)到了最 大的二叉樹(shù) . 編號(hào)的滿(mǎn)二叉樹(shù) : 從根開(kāi)始 ,由上到下 , 從左到右地對(duì)每個(gè)結(jié)點(diǎn) 進(jìn)行編號(hào) . 也就是說(shuō) :根的編號(hào)是 1,一個(gè)結(jié)點(diǎn) ,若它是雙親 的左子女 ,則它的編號(hào)是它的雙親編號(hào)的 2倍 。 ? ? 1lo g 2 ?n證明： 二叉樹(shù)的性質(zhì) 設(shè) 完全二叉樹(shù)的深度為 k 則根據(jù)性質(zhì) 2得 2k1 1 n ≤ 2k1 或 者 2k1 ≤ n 2k 即 k1 ≤ log2 n k 因?yàn)? k 只能是整數(shù)，因此， k =?log2n? + 1 或 k = log2n+1 性質(zhì) 5： 在編號(hào)的完全二叉樹(shù)中，對(duì)任一結(jié)點(diǎn) i（ 1≤i ≤ n） 有： （ 1）若 i=1, 是根 。 否則無(wú)左子女； （ 3）若 2i+1 ≤ n， 則結(jié)點(diǎn) i的右子女是 2i。 struct BiTNode *lchild,* rchild。 A B C E F H G 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) A B C E H F G 二叉鏈表 BT lchild data rchild Left child Right child BiTNode: 二 、二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) (三叉鏈表 ) lchild data rchild parent Left child Right child Parent typedef struct BiTNode{ ElemType data。 }BiTNode, *BiTree。 一、遍歷 “ 訪(fǎng)問(wèn) ”的含義特別很廣，如：輸出結(jié)點(diǎn)的信息等。 前 (先 )序 遍歷 中序遍歷 后序遍歷 N L R 1 2 3 二、遍歷方法 NLR LNR LRN NRL RNL RLN 遍歷二叉樹(shù)和 線(xiàn)索二叉樹(shù) 算法思想 前序遍歷： 若 BT非空，則： ； ； 。 遍歷二叉樹(shù)和 線(xiàn)索二叉樹(shù) 前序遍歷二叉樹(shù)的 遞歸算法 算法 Void PreOrderTraverse(BiTree BT){ if (BT){ visit(BT)。 PreOrderTraverse(BTrchild)。 是擴(kuò)充的葉結(jié)點(diǎn)，它代表空指針。 2. 建立根。 建立二叉樹(shù)的算法 Status CreateBiTree(BiTree amp。ch)； if(ch==‘ ’) BT=NULL； else{ if(!(BT=(BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW)； BTdata=ch。 ／／ 構(gòu)造左子樹(shù) CreateBiTree(BTrchild)。 amp。 amp。 amp。 amp。 A B C E F H G D I 后序遍歷 LRN amp。 amp。 amp。 amp。 amp。 時(shí)訪(fǎng)問(wèn) 遍歷線(xiàn)路的核心規(guī)則是：先左后右； 我們用一個(gè)棧 stack記錄走過(guò)的位置，以便返回； stack 中數(shù)據(jù)元素的類(lèi)型： *BiTNode(或 BiTree) 函數(shù)： BiTree P。 pop(S,p)。 下面給出基于邏輯 結(jié)構(gòu)的算法描述 非遞歸中序遍歷二叉樹(shù)的算法思想 建立棧 stack； 1. P指向根； 2. 當(dāng) p不空 且 stack 不空時(shí)反復(fù)做： 若 p不空 ,p 入 棧 。 p=prchild； }//else }／／ InOrderTraverse 非遞歸中序遍歷 BT的算法 : A B C D E F G p i amp。A amp。A amp。C (3) 例 p=NULL A B C D E F G i amp。B 訪(fǎng)問(wèn)： C (4) 例 p A B C D E F G i amp。A amp。A amp。E 訪(fǎng)問(wèn)： C B p (7) 例 A B C D E F G i amp。D 訪(fǎng)問(wèn)： C B E p (8) 例 A B C D E F G i amp。D amp。A amp。A 訪(fǎng)問(wèn)： C B E G D p (11) 例 A B C D E F G i amp。F 訪(fǎng)問(wèn)： C B E G D p (12) 例 A B C D E F G i amp。 p指向左子女； 否則 ： ? 出棧頂元到 p和 tag中； ? 若 tag==R ,則訪(fǎng)問(wèn) p； p置空； ? 否則 （ p,R） 入棧； 并讓 p指向右子女； 4. 結(jié)束 后序遍歷時(shí)，訪(fǎng)問(wèn)一個(gè)結(jié)點(diǎn)的時(shí)間是： ?第 3次經(jīng)過(guò)時(shí)或 ?第 2次反回時(shí)或 ?從右邊返回時(shí)； 如何區(qū)分從 左 還是 右返回的呢？ P入棧時(shí)帶一標(biāo)記 : 向左走時(shí)帶 L 向左走時(shí)帶 R 非遞歸后序遍歷 BT的算法 非遞歸的后序遍歷 BT算法 :（ 基于二叉鏈表存儲(chǔ)結(jié)構(gòu)） void PostOrderTraverse (BiTree BT) { InitStack(S)； //建立棧 p=BT。 } // p指向左子女 else { pop(p,e)。 tag=。 p=NULL。 p=prchild。 n個(gè)結(jié)點(diǎn)的二叉樹(shù) ,有 2n個(gè)指針 ,只用了 n1個(gè) ,有 n+1個(gè)是空指。 為了區(qū)分線(xiàn)索與真實(shí)指針，給結(jié)點(diǎn)增加兩個(gè)域 Ltag和 Rtag lchild Ltag data Rtag rchild Ltag=0: lchild 指向結(jié)點(diǎn)的左子女； Ltag=1: lchild 指向 某一遍歷序列 前驅(qū)； Rtag=0: rchild 指向結(jié)點(diǎn)的右子女； Rtag=1: rchild 指向 某一遍歷序列 后繼 ； 二、線(xiàn)索二叉樹(shù) (Threaded Binary Tree) Typedef enum{Link,Thread} PointerTag。 struct BiThrNode *lchild, *rchild。 } BiThrNode, *BiThrTree。 p=prchild； }//else }／／ InOrderTraverse 非遞歸中序遍歷二叉樹(shù)的算法 (回憶 ) 對(duì)以二叉鏈表存儲(chǔ)的二叉樹(shù)進(jìn)行中序線(xiàn)索化 (非遞歸的 ) void InOrderThreading (BiThrTree BT) { InitStack(S)。 pre=NULL。 // p入棧 p=plchild。 //出棧頂元到 p中 if (!plchild) { plchild=pre。} if(pre amp。 !prerchild) { prerchild=p。} pre=p。 } // p指向右子女 } // end of while } // end of InOrderThreading(BT) visit(p) ? (中序 )線(xiàn)索二叉樹(shù)的線(xiàn)索給我們提供了足夠的信息 , 對(duì)其進(jìn)行遍歷時(shí)，既不需要遞歸 (使用了系統(tǒng)棧 ), 也不需要棧 . 對(duì) (中序 )線(xiàn)索二叉樹(shù)進(jìn)行非遞歸遍歷且不需要設(shè)棧時(shí)需要主要解決的兩個(gè)問(wèn)題 : 1) 找到某一次序下的第一個(gè)結(jié)點(diǎn) p。 關(guān)鍵問(wèn)題 1 沿著根的左鏈走 ,直到無(wú)左子女的結(jié)點(diǎn) p， 即中序序列中的第一個(gè)結(jié)點(diǎn) 。 while (!) p=plchild。 if () p=prchild。 // P有右子女 while (!) p=plchild。 while(!p) { while (!pltag) p=plchild。 while (prtag amp。 p) { p=prchild。} p=prchild。 否則 ?P是葉：沿著 p的線(xiàn)索走，直到空或一個(gè)有右子女的結(jié)點(diǎn) r為止，若空，則 p無(wú)后繼，否則 r的右子女是 p 的 后繼。 while (p) { visit(p)。 // P有左子女 else if (!prtag) p=prchild。 //p是葉 while (r amp。 ) r=rrchild。 else p=r。 每個(gè)結(jié)點(diǎn)有兩個(gè)域 : data是結(jié)點(diǎn)的數(shù)據(jù)元素； parent是指出該結(jié)點(diǎn)的雙親結(jié)點(diǎn)在數(shù)組中的下標(biāo)； data parent 一、 樹(shù)的存儲(chǔ)結(jié)構(gòu) 樹(shù)的存儲(chǔ)結(jié)構(gòu) PTNode: 樹(shù)的雙親表示法說(shuō)明：