第4單元非線性數(shù)據(jù)結(jié)構(gòu)樹、二叉樹主講：劉志強(存儲版)
【正文】 A B C D E F A B C D E F 下一頁 上一頁 停止放映 第 61 頁 二叉樹遍歷算法（遞歸、前序法程序驗證 ） 打印 A – 取 A?.左子 (B) – 打印 B 取 B?.左子 (C) 打印 C – 取 C?.左子 (空 ) – 取 C?.右子 (空 ) 取 B?.右子 (D) 打印 D – 取 D?.左子 (E) – 打印 E 取 E?.左子 (空 ) 取 E?.右子 (空 ) – 取 D?.右子 (F) – 打印 F 取 F?.左子 (空 ) 取 F?.右子 (空 ) – 取 A?.右子 (空 ) 結(jié)束 A B C D E F 下一頁 上一頁 停止放映 第 62 頁 二叉樹遍歷算法 （非遞歸算法 前序法） ? 算法步驟 : – step1 初始化 ,置棧為空 (top=1), 工作變量 p指向 root。 （ a） 二叉排序樹 （ b） 非二叉排序樹 10 5 7 11 14 18 15 15 14 18 5 10 12 13 7 下一頁 上一頁 停止放映 第 53 頁 二叉樹的遍歷 ? 遍歷 （ Traversing） 是樹形結(jié)構(gòu)的一種重要運算 ， 即按一定的次序系統(tǒng)地訪問結(jié)構(gòu)中的所有結(jié)點 ， 使每個結(jié)點只被訪問一次 。 – 第 k層從右邊連續(xù)缺若干個結(jié)點 (即只能從右至左不間斷缺少 )。 leftp ^ ^ A B D E G ^ F 下一頁 上一頁 停止放映 第 44 頁 特殊二叉樹 滿二叉樹 完全二叉樹 平衡二叉樹 二叉排序樹 下一頁 上一頁 停止放映 第 45 頁 滿二叉樹 若 k為二叉樹 T的深度 ， 且 T中共有 2k1個結(jié)點 （ k ? 1） ， 則稱 T為滿二叉樹 。 A B C D E F G 0 1 2 3 4 5 6 7 A B C D E F G 0 1 2 3 4 5 6 7 A B E A B E 滿樹 非滿樹 下一頁 上一頁 停止放映 第 39 頁 順序存儲（一維數(shù)組） 存儲描述為： define MAXSIZE 100； typedef TElemType SBTree[MAXSIZE]； SBTree bt； 不便查找 。 利用歸納法證明： – i=1時 ， 只有一個結(jié)點 ， 對的； – 假設(shè)對所有的 j， 1? j ? i， 命題成立 ， 即在第 j層上 ， 至多有 2j1 個結(jié)點 。 – 二叉樹的定義 – 二叉樹的性質(zhì) – 二叉樹的存儲結(jié)構(gòu) – 特殊二叉樹 – 二叉樹的遍歷操作 – 表達式樹及應(yīng)用 – 樹 、 森林與二叉樹的轉(zhuǎn)換 下一頁 上一頁 停止放映 第 29 頁 二叉樹的定義 二叉樹是另一種樹形結(jié)構(gòu)： Binary_Tree =( D,R) 其中 : D 是具有相同性質(zhì)的數(shù)據(jù)元素的集合 。 下一頁 上一頁 停止放映 第 21 頁 樹的實現(xiàn) (存儲結(jié)構(gòu) ) 數(shù)組實現(xiàn)方法 （ 雙親表示法 ） 鏈表實現(xiàn)方式 （ 孩子表示法 ） 二叉鏈表實現(xiàn)方式 （ 孩子兄弟表示法 ） 下一頁 上一頁 停止放映 第 22 頁 樹的存儲結(jié)構(gòu) (一） 數(shù)組實現(xiàn)方法（雙親表示法） 用數(shù)組存儲樹的結(jié)點信息 ， 在每個結(jié)點中附設(shè)一個指示器指示其雙親結(jié)點在數(shù)組中的位置 。 否則 ， 稱為無序樹 。 如階層 1有結(jié)點A， 階層 2有結(jié)點 B， C， D。 如 B， C， D等 。 下一頁 上一頁 停止放映 第 9 頁 樹的定義 ? 樹是一個或多個結(jié)點組成的有限集合 T，有一個特定結(jié)點稱為根 ， 其余結(jié)點分為m （ m?0 ） 個互不相交的集合 T1，T2， … ,Tm。 下一頁 上一頁 停止放映 第 8 頁 樹的邏輯結(jié)構(gòu) 樹是一種數(shù)據(jù)結(jié)構(gòu) ， 可用二元組表示為： Tree=（ D， R） 其中： D 是具有相同特性的數(shù)據(jù)元素的集合； R 是數(shù)據(jù)元素間邏輯關(guān)系的集合 ， 且滿足： – 在 D中存在唯一的稱為根的數(shù)據(jù)元素 ， 沒有前趨； – D中其余數(shù)據(jù)元素都有且只有一個前趨； – D中所有元素 ， 或有若干個互不相同的后繼 （ 子樹 ） ， 或無后繼 （ 葉結(jié)點 ） ； 則稱 Tree為樹 。 支結(jié)點 度不為 0的結(jié)點為支結(jié)點 。 路徑 結(jié)點的序列 n1， n2， … ,nk(K?1)是一條路徑 . 階層 （ 層次 ） 結(jié)點的特性值 ， 根結(jié)點的階層為 1， 子結(jié)點為 2， 依次類推 。 有序 如果將樹中結(jié)點的各子樹看成從左至右是有順序的 （ 即不能互換 ） ， 則稱該樹為 有序樹 。 按次序依此訪問樹中各個結(jié)點 ， 且使每個結(jié)點只能被訪問一次 。 ^ 下一頁 上一頁 停止放映 第 28 頁 二、二叉樹結(jié)構(gòu) 二叉樹是另一類重要的非線性結(jié)構(gòu) ，是樹的一種 。 下一頁 上一頁 停止放映 第 34 頁 二叉樹的性質(zhì) ? 性質(zhì)一 二叉樹的第 i層上至多有 2i1 個結(jié)點 （ i ? 1） 。存入時按從左到右，從低階層到高階層的順序存放。 下一頁 上一頁 停止放映 第 41 頁 記錄數(shù)組結(jié)構(gòu)舉例 1 2 6 3 4 5 1 2 6 2 3 4 3 0 5 4 0 0 5 0 0 6 0 0 結(jié)點 左子 右子 特點 : 找子方便 ,找父結(jié)點不便 . 下一頁 上一頁 停止放映 第 42 頁 二叉鏈表存儲結(jié)構(gòu) data leftp rightp 左指針 數(shù)據(jù) 右指針 A B C D E F G A B D C E F G ^ ^ ^ ^ ^ ^ ^ ^ 特點 : 找子易 , 找父難 . 下一頁 上一頁 停止放映 第 43 頁 三叉鏈表存儲結(jié)構(gòu) parent data rightp 左指針
教學課件相關(guān)推薦
鄂ICP備17016276號-1