《數(shù)據(jù)結(jié)構(gòu)課件、代碼》第4章 樹(shù)和二叉樹(shù).ppt

第4章樹(shù)和二叉樹(shù) 張成文北京郵電大學(xué)計(jì)算機(jī)學(xué)院 樹(shù)的定義與基本術(shù)語(yǔ) 1 定義 樹(shù)是n n 0 個(gè)結(jié)點(diǎn)的有限集合T 當(dāng)n 0時(shí) 稱(chēng)為空樹(shù) 當(dāng)n 0時(shí) 該集合滿足如下條件 1 其中必有一個(gè)稱(chēng)為根 root 的特定結(jié)點(diǎn) 它沒(méi)有直接前驅(qū) 但有零個(gè)或多個(gè)直接后繼 2 其余n 1個(gè)結(jié)點(diǎn)可以劃分成m m 0 個(gè)互不相交的有限集T1 T2 T3 Tm 其中Ti又是一棵樹(shù) 稱(chēng)為根root的子樹(shù) 每棵子樹(shù)的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū) 但有零個(gè)或多個(gè)直接后繼 一 樹(shù) tree 的基本概念 A B C D E F G H I J M K L A B E F K L C G D H I J M T1 T3 T2 樹(shù)根 例如 1 樹(shù)型圖示 2 嵌套集合 3 凹入 書(shū)目 4 廣義表 用根作為表的名字寫(xiě)在表的左邊 A B E K L F C G D H M I J 2 樹(shù)的表示法 線性結(jié)構(gòu) 樹(shù)型結(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è)后繼 對(duì)比樹(shù)型結(jié)構(gòu)和線性結(jié)構(gòu)的結(jié)構(gòu)特點(diǎn) 結(jié)點(diǎn) node 樹(shù)的度 葉子結(jié)點(diǎn) leaf 分支結(jié)點(diǎn) 數(shù)據(jù)元素 若干指向子樹(shù)的分支 樹(shù)各結(jié)點(diǎn)的度的最大值 度為零的結(jié)點(diǎn) 度大于零的結(jié)點(diǎn) D H I J M 3 樹(shù)的相關(guān)術(shù)語(yǔ) 結(jié)點(diǎn)的度 degree 結(jié)點(diǎn)擁有的子樹(shù)數(shù) 結(jié)點(diǎn)的層次 level 假設(shè)根結(jié)點(diǎn)的層次為1 第l層的結(jié)點(diǎn)的子樹(shù)根結(jié)點(diǎn)的層次為l 1 樹(shù)的深度 depth 葉子結(jié)點(diǎn)所在的最大層次 分支 branch 表示數(shù)據(jù)元素與它的子樹(shù)的關(guān)系 路徑 path 常用家族樹(shù)的術(shù)語(yǔ)表示結(jié)點(diǎn)關(guān)系孩子 child 結(jié)點(diǎn)雙親 parent 結(jié)點(diǎn)兄弟結(jié)點(diǎn) 由根到該結(jié)點(diǎn)所經(jīng)的分支和結(jié)點(diǎn)構(gòu)成 樹(shù)的結(jié)點(diǎn)數(shù)n和分支數(shù)b的關(guān)系是 b n 1 任何一棵非空樹(shù)是一個(gè)二元組Tree root F 其中 root被稱(chēng)為根結(jié)點(diǎn)F被稱(chēng)為子樹(shù)森林 森林 forest 是m m 0 棵互不相交的樹(shù)的集合 A root B C D E F G H I J M K L F 二叉樹(shù) 1二叉樹(shù)的定義與基本操作 定義 滿足以下兩個(gè)條件的樹(shù)稱(chēng)做二叉樹(shù) BinaryTree 1 每個(gè)結(jié)點(diǎn)的度都不大于2 2 每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)次序不能任意顛倒 二叉樹(shù)或?yàn)榭諛?shù) 或是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱(chēng)為左子樹(shù)和右子樹(shù)的 互不交的二叉樹(shù)組成 注意 二叉樹(shù)是有序樹(shù) 它的子樹(shù)有左右之分 二叉樹(shù)的度數(shù)不超過(guò)二 但度數(shù)不超過(guò)二的樹(shù)未必是二叉樹(shù) A B C D E F G H K 根結(jié)點(diǎn) 左子樹(shù) 右子樹(shù) 二叉樹(shù)的五種基本形態(tài) N 空樹(shù) 只含根結(jié)點(diǎn) N N N L R R 右子樹(shù)為空樹(shù) L 左子樹(shù)為空樹(shù) 左右子樹(shù)均非空樹(shù) 用歸納法證明 歸納基 歸納假設(shè) 歸納證明 i 1層時(shí) 只有一個(gè)根結(jié)點(diǎn) 2i 1 20 1命題成立 假設(shè)i 1命題成立 即 第i 1層至多有結(jié)點(diǎn) 2i 1 1 2i 2個(gè) 二叉樹(shù)每個(gè)結(jié)點(diǎn)至多有兩棵子樹(shù) 則第i層至多有結(jié)點(diǎn) 2i 2 2 2i 1個(gè) 2二叉樹(shù)的重要特性 性質(zhì)1 二叉樹(shù)第i層上至多有2i 1個(gè)結(jié)點(diǎn) 證明 基于性質(zhì)1 深度為k的二叉樹(shù)上的結(jié)點(diǎn)總數(shù)的最大值是將二叉樹(shù)每層上結(jié)點(diǎn)的最大值相加 所以深度為k的二叉樹(shù)上含結(jié)點(diǎn)數(shù)至多為 20 21 2k 1 2k 1 性質(zhì)2 深度為k的二叉樹(shù)上至多含2k 1個(gè)結(jié)點(diǎn) k 1 證明 設(shè)二叉樹(shù)上結(jié)點(diǎn)總數(shù) n n0 n1 n2再根據(jù)樹(shù)的性質(zhì) b n 1 n0 n1 n2 1由有二叉樹(shù)分支總數(shù) b n1 2n2兩式右邊相等得 n0 n2 1 性質(zhì)3 對(duì)任何一棵二叉樹(shù) 若它含有n0個(gè)葉子結(jié)點(diǎn) n2個(gè)度為2的結(jié)點(diǎn) 則必存在關(guān)系式 n0 n2 1 也可以用歸納法證明 滿二叉樹(shù) 在一個(gè)二叉樹(shù)中 若第i層的結(jié)點(diǎn)數(shù)為2i 1 則稱(chēng)此層的結(jié)點(diǎn)數(shù)是滿的 當(dāng)樹(shù)中的每一層都是滿的 則稱(chēng)此二叉樹(shù)為滿二叉樹(shù) 即如果一個(gè)二叉樹(shù)中 除最下一層的各結(jié)點(diǎn)度數(shù)為0以外 其它各層結(jié)點(diǎn)的度數(shù)均等于2 則此二叉樹(shù)為滿二叉樹(shù) 完全二叉樹(shù) 如果一個(gè)二叉樹(shù)各層都是 滿 的 只是最下面一層從右邊起連續(xù)缺n個(gè)結(jié)點(diǎn) 這種二叉樹(shù)叫做完全二叉樹(shù) 完全二叉樹(shù) 樹(shù)中所含的n個(gè)結(jié)點(diǎn)和滿二叉樹(shù)中編號(hào)為1至n的結(jié)點(diǎn)一一對(duì)應(yīng) a b c d e f g h i j 可用一維數(shù)組存儲(chǔ) bt n 順序 完全二叉樹(shù)中將編號(hào)i的結(jié)點(diǎn)存在bt i 中 一 二叉樹(shù)的順序存儲(chǔ) 3二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) 二叉樹(shù)是非線性結(jié)構(gòu) 結(jié)點(diǎn)最多有兩個(gè)后繼 存儲(chǔ)結(jié)構(gòu)有兩種 順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 例如 ABDCEF 1234567891011121314 一般二叉樹(shù) 按完全二叉樹(shù)結(jié)點(diǎn)的編號(hào)存放 無(wú)結(jié)點(diǎn)的單元存放空元素 會(huì)造成空間浪費(fèi) 二 二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)表示 二叉鏈表 每個(gè)結(jié)點(diǎn)包括兩個(gè)指針域 指向左孩子和右孩子 二叉樹(shù)T 二叉鏈表 結(jié)點(diǎn)結(jié)構(gòu) lchilddatarchild 結(jié)點(diǎn)結(jié)構(gòu) 二叉鏈表結(jié)點(diǎn)的結(jié)構(gòu)用C語(yǔ)言描述為 typedefstructNode DataTypedata strctNode LChild structNode RChild BiTNode BiTree 一 問(wèn)題的提出 二 先左后右的遍歷算法 三 算法描述 二叉樹(shù)的遍歷 遍歷 沿某條搜索路徑巡訪二叉樹(shù)的結(jié)點(diǎn) 使每個(gè)結(jié)點(diǎn)均被訪問(wèn)一次 且僅被訪問(wèn)一次 一 問(wèn)題的提出 訪問(wèn) 的含義很廣 如 輸出結(jié)點(diǎn)信息等 遍歷 是任何類(lèi)型均有的操作 對(duì)線性結(jié)構(gòu)而言 只有一條搜索路徑 因?yàn)槊總€(gè)結(jié)點(diǎn)只有一個(gè)后繼 故不需要另加討論 二叉樹(shù)是非線性結(jié)構(gòu) 每個(gè)結(jié)點(diǎn)有兩個(gè)后繼 則存在按什么樣的搜索路徑遍歷的問(wèn)題 二叉樹(shù) 由三部分組成 根結(jié)點(diǎn) 左子樹(shù)和右子樹(shù) 若能依次遍歷這三部分 就遍歷了整個(gè)二叉樹(shù) 用L D R表示遍歷左子樹(shù) 訪問(wèn)根結(jié)點(diǎn) 遍歷右子樹(shù) 則有8種遍歷二叉樹(shù)方案 先左后右 DLR LDR LRD 按層次先右后左 DRL RDL RLD 按層次 二 先左后右的遍歷算法 先序的遍歷算法DLR 中序的遍歷算法LDR 后序的遍歷算法LRD D L R 若二叉樹(shù)為空樹(shù) 則空操作 否則 1 訪問(wèn)根結(jié)點(diǎn) 2 先序遍歷左子樹(shù) 3 先序遍歷右子樹(shù) 先序的遍歷算法 D L R 若二叉樹(shù)為空樹(shù) 則空操作 否則 1 中序遍歷左子樹(shù) 2 訪問(wèn)根結(jié)點(diǎn) 3 中序遍歷右子樹(shù) 中序的遍歷算法 D L R 若二叉樹(shù)為空樹(shù) 則空操作 否則 1 后序遍歷左子樹(shù) 2 后序遍歷右子樹(shù) 3 訪問(wèn)根結(jié)點(diǎn) 后序的遍歷算法 D L R a b c d e f g h i j 例如 先序序列 abdhiejcfg 中序序列 hdibjeafcg 后序序列 hidjebfgca 三 算法描述 1 先序遍歷voidPreOrder BiTreebt 先序遍歷 根指針為bt的二叉樹(shù) if bt NULL Visit bt data 訪問(wèn)根結(jié)點(diǎn)PreOrder bt LChild 遍歷左子樹(shù)PreOrder bt RChild 遍歷右子樹(shù) 2 中序遍歷voidInOrder BiTreebt 中序遍歷根指針為bt的二叉樹(shù) if bt NULL InOrder bt LChild 遍歷左子樹(shù)Visit bt data 訪問(wèn)根結(jié)點(diǎn)InOrder bt RChild 遍歷右子樹(shù) 3 后序遍歷voidPostOrder BiTreebt 后序遍歷根指針為bt的二叉樹(shù) if bt NULL PostOrder bt LChild 遍歷左子樹(shù)PostOrder bt RChild 遍歷右子樹(shù)Visit bt data 訪問(wèn)根結(jié)點(diǎn) 利用遍歷結(jié)果確定二叉樹(shù)問(wèn)題先序序列 中序序列中序序列 后序序列先序序列 后序序列 x 先序序列 ABCDEFGH中序序列 BDCEAFHG A B F C G D E H 利用遍歷結(jié)果確定二叉樹(shù)問(wèn)題 僅知二叉樹(shù)的先序序列