【正文】 //出隊(duì)一個(gè)結(jié)點(diǎn) if(!Visit(pdata)) return ERROR。 71 (1)從根開始：若二叉樹非空 ， 則根入隊(duì)； (2)隊(duì)頭出隊(duì) ， 并訪問； B A ^ C ^ D ^ E ^ G ^ ^ F ^ ^ H ^ T 排隊(duì)處 遍歷序列 思路： A p BC (3)若當(dāng)前結(jié)點(diǎn)有左子樹 ， 則其左子樹的根入隊(duì)； (4)若當(dāng)前結(jié)點(diǎn)有右子樹 ， 則其右子樹的根入隊(duì)； (5)重復(fù) (2)~(4)， DE p F p G H p p p 直至隊(duì)空 。 二、前序遍歷 (Preorder Traversal) 65 三、中序遍歷 (Inorder Traversal) ? 原則 – 若被遍歷的二叉樹為空，則空操作 – 否則 遍歷根結(jié)點(diǎn)的左子樹 遍歷根結(jié)點(diǎn)的右子樹 遞歸 66 遍歷序列： (1)中序遍歷左子樹； (2)訪問根結(jié)點(diǎn)； (3)中序遍歷右子樹 。 練習(xí) 3 61 一、二叉樹的遍歷 按照一定的順序 (原則 )對二叉樹中每一個(gè)結(jié)點(diǎn)都訪問一次 (僅訪問一次 )，得到一個(gè)由該二叉樹的所有結(jié)點(diǎn)組成的序列，這一過程稱為 二叉樹的遍歷 。 /*BT[i]是雙親的左孩子 */ else PTR[j]rchild=PTR[i]。 PTR[i]lchild=NULL。 /*建立根結(jié)點(diǎn) */ 59 for(i=2。 PTR[1]data=BT[1]。 55 建立根結(jié)點(diǎn) 以 BT的第 2個(gè)元素開始取一個(gè)元素 建立一個(gè)新結(jié)點(diǎn) 保存新結(jié)點(diǎn)的地址 找到新結(jié)點(diǎn)的雙親結(jié)點(diǎn)的地址 確定新結(jié)點(diǎn)是雙親結(jié)點(diǎn)的左（或右）孩子 將新結(jié)點(diǎn)插入二叉鏈表中 保存在一個(gè)數(shù)組中 利用二叉樹的性質(zhì) 5 56 ?設(shè)置一個(gè)一維數(shù)組 PTR存放結(jié)點(diǎn)所在鏈結(jié)點(diǎn)的地址 ?建立根結(jié)點(diǎn)，并將根結(jié)點(diǎn)的地址保存在數(shù)組 PTR中 ?從數(shù)組 BT的第 2個(gè)元素開始依次取結(jié)點(diǎn)的信息 BT[i]，每取得一個(gè)結(jié)點(diǎn)做如下操作： ，并將結(jié)點(diǎn)地址保存在 PTR[i]中； (地址 )； ； 。 ，則表明以左孩子為根的子樹處理完畢，接著應(yīng)該處理以右孩子為根的子樹， 將標(biāo)志置為 2。 A B C D F G E 50 ? 二叉樹的廣義表表示方法 二叉樹 defi=“” 空樹 Φ 51 大寫字母 二叉樹 defi=“A” 只有樹根 A ? 二叉樹的廣義表表示方法 52 大寫字母 ( 二叉樹 , ) 二叉樹 二叉樹 defi=“A(B,C(D,E))” A C D E B ? 二叉樹的廣義表表示方法 53 ，則如下 建立一個(gè)新結(jié)點(diǎn) ， ?若該結(jié)點(diǎn)為根結(jié)點(diǎn)，則將該結(jié)點(diǎn)的地址送 T。 49 關(guān)于廣義表形式表示二叉樹的說明 表中的一個(gè)字母代表一個(gè)結(jié)點(diǎn)的數(shù)據(jù)信息。 typedef struct node { datatype data。 ?具有 n個(gè)結(jié)點(diǎn)的二叉鏈表中 ， 共有 2n個(gè)指針域 。 40 48 951 0 1 161 2 1 371 4 1 52 311 2 3 4 0 6 7 8 9 0 0 12 0 0 15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 BT[6]的雙親為 ?6/2?=3，即在 BT[3]中！ 其左孩子在 BT[2i]=BT[12]中； 其右孩子在 BT[2i+1]=BT[13]中，而 BT[13]＝ 0，表示無右孩子。 – 按照滿二叉樹的順序存放 38 完全二叉樹的順序存儲(chǔ)結(jié)構(gòu) 根據(jù)完全二叉樹的 性質(zhì) 5，對于深度為 h的完全二叉樹，將樹中所有結(jié)點(diǎn)的數(shù)據(jù)信息按編號順序一次存儲(chǔ)到數(shù)組 BT[1…2 h1]中，由于編號與數(shù)組下標(biāo)一一對應(yīng)，該數(shù)組就是該完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)。 35 自測題 1025個(gè)結(jié)點(diǎn)的二叉樹的高 h為 ( ) 。 ?(1000+1)/2? =500 葉子總數(shù) 1=499 1 0 因?yàn)樽詈笠粋€(gè)結(jié)點(diǎn)坐標(biāo)是偶數(shù)，所以必為左子樹。 30 (n0)個(gè)結(jié)點(diǎn)的樹的高度最低是多少？最高是多少？ (n0)個(gè)結(jié)點(diǎn)的二叉樹的高度最低是多少？最高是多少？ 推論 ? n個(gè)結(jié)點(diǎn)的樹： 高最多為 n， 最低為 2。 2的 有序樹 是二叉樹。 16 二叉樹的基本定義 ? 二叉樹的定義 – 是 n≥0個(gè)結(jié)點(diǎn)的有窮集合 – 該集合或者為空、或者由一個(gè)根結(jié)點(diǎn)和兩個(gè)分別稱為左子樹和右子樹的互不相交的二叉樹組成。 A B C D E F G H I J K L M 孩子 雙親 10 樹的基本概念 ? 祖先、子孫 結(jié)點(diǎn)的 祖先 是從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)； 以某結(jié)點(diǎn)為根的子樹中的任一結(jié)點(diǎn)都稱該結(jié)點(diǎn)的 子孫 。 ?樹的深度即樹中結(jié)點(diǎn)的最大層次 。1 數(shù)據(jù)結(jié)構(gòu) 6 樹和二叉樹 2 ? 樹的類型定義 ? 二叉樹的類型定義 ? 二叉樹的存儲(chǔ)結(jié)構(gòu) ? 遍歷二叉樹和線索二叉樹 ? 樹和森林 ? 赫夫曼樹 主要內(nèi)容 3 –社會(huì)的組織結(jié)構(gòu) –家族的族譜 –計(jì)算機(jī)中的目錄組織 描述層次結(jié)構(gòu)，是一種一對多的邏輯關(guān)系 樹型結(jié)構(gòu)實(shí)例 4 ? 樹的定義 (Tree) – 樹 是由 n(n0)個(gè)結(jié)點(diǎn)組成的有限集合 – 如果 n=0，稱為空樹 – 如果 n0，則 ? 有一個(gè)特定的稱之為 根 (root)的結(jié)點(diǎn)，它只有直接后繼，但 沒有直接前驅(qū) ? 除根以外的其它結(jié)點(diǎn)劃分為 m(m=0)個(gè) 互不相交 的有限集合 T0,T1,…,T m1，每個(gè)集合又是一棵樹，并且稱之為根的 子樹 遞歸定義 5 A B C D E F G H I J K L M 根 子樹 樹 (邏輯上 )的特點(diǎn) ? 每棵子樹的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)，但可以有 0個(gè)或多個(gè)直接后繼 6 A B C D E F G H I J K L M 樹的基本概念 ? 結(jié)點(diǎn) 分支結(jié)點(diǎn) 葉子結(jié)點(diǎn) 根結(jié)點(diǎn) 內(nèi)部結(jié)點(diǎn) 結(jié)點(diǎn) 度不為 0的結(jié)點(diǎn) 度為 0的結(jié)點(diǎn) 7 樹的基本概念 ? 結(jié)點(diǎn)的度和樹的度 ?結(jié)點(diǎn)的度即結(jié)點(diǎn)擁有的子樹個(gè)數(shù) 。 根位于第 1層 ， 根的孩子位于第2層 ， 余則類推 。 ?同一雙親的孩子間互稱 兄弟 。 老大 老二 老三 ? 有序樹的第一個(gè)孩子和最后一個(gè)孩子 樹的基本概念 A B D C 14 樹的常用表示法 A E F B I J G H C D F G I J A B C E D H 凹入表示 嵌套集合 廣義表 A(B(E,F),C,D(G(J),H,I)) A B E F C D G J H I 15 ? 為何要重點(diǎn)研究每結(jié)點(diǎn)最多只有兩個(gè)“叉” 的樹？ – 樹太一般，子樹的個(gè)數(shù)無限制，表示困難 – 二叉樹的結(jié)構(gòu)最簡單，規(guī)律性最強(qiáng) – 可以證明， 所有樹都能轉(zhuǎn)為唯一對應(yīng)的二叉樹 ，不失一般性。 18 二叉樹的五種基本形態(tài) A Φ B A D E B A D E B C A D E 19 問：具有 3個(gè)結(jié)點(diǎn)的二叉樹可能有幾種不同形態(tài)？ 有 5種 Φ 二叉樹的基本形態(tài) 20 2的 樹 是二叉樹。 – 證明： ?除了根結(jié)點(diǎn)以外，每個(gè)結(jié)點(diǎn)有且僅有一個(gè)雙親結(jié)點(diǎn)，即每個(gè)結(jié)點(diǎn)與其雙親結(jié)點(diǎn)之間僅有一個(gè)分支存在，因此，具有 n個(gè)結(jié)點(diǎn)的非空二叉樹的分支總數(shù)為 n1。 33 一棵完全二叉樹有 1000個(gè)結(jié)點(diǎn)，則它必 有 個(gè)葉子結(jié)點(diǎn)； 有 個(gè)度為 2的結(jié)點(diǎn)； 有 個(gè)結(jié)點(diǎn)只有非空左子樹； 有 個(gè)結(jié)點(diǎn)只有非空右子樹。 626個(gè)結(jié)點(diǎn)，葉子結(jié)點(diǎn)的個(gè)數(shù)應(yīng)為 ( )。 SqBiTree Bt。 ? 對于一般二叉樹 ， 需要在二叉樹中 “ 增添 ” 一些實(shí)際上并不存在的 “ 虛結(jié)點(diǎn) ” (可以認(rèn)為這些結(jié)點(diǎn)的數(shù)據(jù)信息為空 )， 使其在形式上成為一棵 “ 完全二叉樹 ” ； ? 然后按照完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)的構(gòu)造方法將所有結(jié)點(diǎn)的信息依次存放到數(shù)組 BT[1..2h1]中 。 ?若二叉樹為空 ， 則 T=NULL；若結(jié)點(diǎn)的某個(gè)孩子不存在 ， 則相應(yīng)的指針為空 。 lchild data parent rchild parent data leftchild rightchild 45 ?三叉鏈表示例 46 ? 二叉鏈表結(jié)點(diǎn)結(jié)構(gòu)的定義 typedef int datatype。 二叉樹的鏈表表示 lchild data rchild 47 二叉樹的存儲(chǔ)結(jié)構(gòu) ? 本節(jié)小結(jié) – 各種存儲(chǔ)結(jié)構(gòu) ?注意各自的優(yōu)缺點(diǎn) ?比如順序存儲(chǔ)空間浪費(fèi)大 ?二叉鏈表不能直接找到父結(jié)點(diǎn) 48 練習(xí) 1 已知非空二叉樹采用廣義表形式作為輸入，請寫一算法，建立該二叉樹的二叉鏈表存儲(chǔ)結(jié)構(gòu)。 （如 ）作為結(jié)束標(biāo)志。 ），則表明一個(gè)子表結(jié)束， 作退棧操作 。請寫出由此產(chǎn)生該二叉樹二叉鏈表結(jié)構(gòu)的算法。 PTR[1]=(bitree *)malloc(sizeof(bitree))。 T=PTR[1]。 PTR[i]data=BT[i]。 /*計(jì)算雙親結(jié)點(diǎn)的位置 j*/ if(i%2==0) PTR[j]lchild=PTR[i]。請寫出由此產(chǎn)生該二叉樹二叉鏈表結(jié)構(gòu)的算法。 以根結(jié)點(diǎn)為參照系 根 左子樹 右子樹 63 ? 原則 – 若被遍歷的二叉樹為空，則空操作 – 否則 遍歷根結(jié)點(diǎn)的左子樹 遍歷根結(jié)點(diǎn)的右子樹 二、前序遍歷 (Preorder Traversal) 遞歸 64 B A C F D E G H 遍歷序列： (1)訪問根結(jié)點(diǎn)； (2)前序遍歷左子樹； (3)前序遍歷右子樹 。 70 二叉樹的其它操作：廣度優(yōu)先遍歷 二叉樹的層序遍歷算法： (1)初始化設(shè)置一個(gè)隊(duì)列； (2)把根結(jié)點(diǎn)指針入隊(duì)列； (3)當(dāng)隊(duì)列非空時(shí)，循環(huán)執(zhí)行步驟 (a)到步驟 (c): (a)出隊(duì)列取得一個(gè)結(jié)點(diǎn)指針，訪問該結(jié)點(diǎn)； (b)若該結(jié)點(diǎn)的左子樹非空，則將該結(jié)點(diǎn)的左子樹指針入隊(duì)列； (c)若該結(jié)點(diǎn)的右子樹非空，則將該結(jié)點(diǎn)的右子樹指針入隊(duì)列； (4)結(jié)束。 //樹根入隊(duì) while(!QueueEmpty(Q)) //只要隊(duì)列非空 { DeleteQueue(Q,p)。 //右孩子入隊(duì) } return OK。 ??前序遍歷左子樹 PreOrderTraverse(Trchild)。 InOrderTraverse(Trchild)。 printf(\t%c\n,Tdata)。 五、遞歸問題的非遞歸算法的設(shè)計(jì) 78 五、遞歸問題的非遞歸算法的設(shè)計(jì) ? 回顧遍歷的過程 (以中序?yàn)槔?) 1 先走到最左 2 往回訪問父結(jié)點(diǎn) 3 往右訪問右子樹 走到最左 回訪父結(jié)點(diǎn) 訪問右子樹 ... A B C D E F G 79 二叉樹的遍歷：非遞歸算法 A B C D E F G ? 當(dāng)向左 /右走到底時(shí)怎么辦？ ? 需要返回到祖先 ? 哪個(gè)祖先？ ? 路過的卻未訪問的最近的祖先 ? 這就需要一種機(jī)制能記錄訪問的“歷史信息” :路過卻未訪問的結(jié)點(diǎn) ，以便能夠回溯回去 ? 這就需要一個(gè) 棧 存放來這些祖先 80 E H二叉樹的遍歷：非遞歸算法 (1)非空樹從根開始； (2)若當(dāng)前結(jié)點(diǎn)存在 ， 則暫存 ， p下到左子樹； 否則回退 → 訪問當(dāng)前結(jié)點(diǎn) → p下到右子樹 中序遍歷非遞歸思路： B A ^ C ^ D ^ E ^ G ^ ^ F ^ ^