計算機基礎與Visual Basic程序設計（第二版）第十二章_數據結構與算法

數據結構與算法 公共基礎知識考試大綱 一、數據結構與算法 二、程序設計基礎 三、軟件工程基礎 四、數據庫設計基礎 包含四部分內容： 公共基礎知識考試大綱 1. 掌握算法的基本概念。 2. 掌握基本數據結構及其操作。 3. 掌握基本排序和查找算法。 4. 掌握逐步求精的結構化程序設計方法。 5. 掌握軟件工程的基本方法，具有初步應用相關技術進行軟件開發(fā)的能力。 6. 掌握數據庫的基本知識，了解關系數據庫的設計。 基本要求： 公共基礎知識考試大綱 1. 算法的基本概念；算法復雜度的概念和意義。 2. 數據結構的定義；數據的邏輯結構與存儲結構；數據結構的圖形表示；線性結構與非線性結構的概念。 3. 線性表的定義；線性表的順序存儲結構及其插入與刪除運算。 4. 棧和隊列的定義；棧和隊列的順序存儲結構及其基本運算。 數據結構與算法考試內容： 公共基礎知識考試大綱 5. 線性單鏈表、雙向鏈表與循環(huán)鏈表的結構及其基本運算。 6. 樹的基本概念；二叉樹的定義及其存儲結構；二叉樹的前序、中序和后序遍歷。 7. 順序查找與二分法查找算法；基本排序算法（交換類排序，選擇類排序，插入類排序）。 數據結構與算法考試內容： 一、數據結構與算法 用計算機解決實際問題，需要編寫程序。 一個程序應 包括兩個方面 ： 數據結構（ ，對數據的描述，即在程序中要指定 數據的類型 和 數據的組織形式 ； 算法（ 是對操作的描述，即操作步驟。 這就是著名計算機科學家沃思（ 出的一個公式： 程序 = 數據結構 + 算法 一、數據結構與算法 考點 1 算法的基本概念 算法（ 是指解題方案的準確而完整的描述。 算法的基本特征： （ 1）有窮性（ 一個算法應包含有限的操作步驟而不能是無限的。 （ 2）確定性（ 算法中的每一個步驟都應該是確定的，而不應當是含糊的、模棱兩可的。 （ 3）可行性（ 一個算法應該可以有效地執(zhí)行，即算法描述的每一步都可通過已實現(xiàn)的基本運算執(zhí)行有限次來完成。 法 算法（ 是指解題方案的準確而完整的描述。 算法的基本特征： （ 4）輸入（ 是指在執(zhí)行算法時需要從外界取得必要的信息。 （ 5）輸出（ 算法的目的是為了求解，“解”就是輸出。一個算法可以有一個或多個輸出。 （ 4）擁有足夠的情報。算法中各種運算總是要施加到各個運算對象上，而這些運算對象又可能具有某種初始狀態(tài)，這就是算法執(zhí)行的起點或依據。 法 考點 1 算法的基本概念 算法的基本要素： 一個算法有 兩個基本要素 ：一個是 對數據對象的運算和操作 ，另一個是 算法的控制結構 。 對數據對象的運算和操作： 算術運算： 主要包括加、減、乘、除等運算。 邏輯運算： 主要包括“邏輯與”、“邏輯或”、“邏輯非”等運算。 關系運算： 主要包括 “大于”、“大于或等于”、“小于”、“小于或等于”、“等于”、“不等于”等運算。 數據傳輸： 主要包括賦值、輸入、輸出等操作。 考點 1 算法的基本概念 算法的基本要素： 一個算法有 兩個基本要素 ：一個是 對數據對象的運算和操作 ，另一個是 算法的控制結構 。 算法的控制結構： 算法中各種操作之間的執(zhí)行順序稱為 算法的控制結構 。 算法的控制結構給出了算法的基本框架。 描述算法的工具通常有： 傳統(tǒng)流程圖、 N 法描述語言等。 一個算法一般都可以用 順序結構 、 選擇結構 和 循環(huán)結構這三種基本控制結構組合而成。 考點 1 算法的基本概念 算法設計基本方法： （ 1）列舉法 列舉法就是根據所要解決的問題，把所有可能的情況都一一列舉出來，并用問題中給定的條件來檢驗哪些是需要的，哪些是不需要的。 （ 2）歸納法 歸納法的基本思想是通過列舉少量的特殊情況，經過分析最后找出一般的關系。 （ 3）遞推法 遞推法是指從已知的初始條件出發(fā)，逐步推出所要求的結果。 考點 1 算法的基本概念 算法設計基本方法： （ 4）遞歸法 在解決某些復雜問題時，為了降低問題的復雜程度（如問題的規(guī)模等），可以將問題逐層分解，最后歸結為一些最簡單的問題。 （ 5）減半遞推法 有些問題的復雜程度與問題本身的規(guī)模大小有關。 “減半” 是指將問題的規(guī)模減半，而問題的性質不變； “遞推” 是指重復“減半”的過程。 減半遞推法又稱為 二分法 。 考點 1 算法的基本概念 考點 2 算法復雜度 算法的復雜度： （是一個經?？疾榈膬热?，在筆試考試中出現(xiàn)的幾率為70%，此考點為重點識記內容。） （ 1）算法的時間復雜度 算法的時間復雜度是指執(zhí)行算法所需要的計算工作量。 同一個算法用不同的語言實現(xiàn)，或者用不同的編譯程序進行編譯，或者在不同的計算機上運行，效率均不同。這表明使用絕對的時間單位衡量算法的效率是不合適的。 算法的時間復雜度可表示為： 其中 O 表示數量級， f (n) 是算法的工作量。 O ( f( n ) )T ( n ) 算法的復雜度： （是一個經常考查的內容，在筆試考試中出現(xiàn)的幾率為70%，此考點為重點識記內容） （ 2）算法的空間復雜度 算法的空間復雜度是指執(zhí)行算法所需要的內存空間。 一個算法所占用的存儲空間包括算法程序所占用的空間、輸入的初始數據所占用的存儲空間以及算法執(zhí)行過程中所需要的額外空間。其中額外空間包括算法程序執(zhí)行過程中的工作單元以及某種數據結構所需要的附加存儲空間 （例如，在鏈式結構中，除了要存儲數據本身外，還需要存儲鏈接信息）。在許多實際問題中，為了減少算法所占的存儲空間，通常采用壓縮存儲技術，以便盡量減少不必要的額外空間。 考點 2 算法復雜度 練習 1： 算法的時間復雜度是指 _。 A) 執(zhí)行算法程序所需要的時間 B) 算法程序的長度 C) 算法執(zhí)行過程中所需要的基本運算次數 D) 算法程序中的指令條數 練習 2： 算法的空間復雜度是指 _。 A) 算法程序的長度 B) 算法程序中的指令條數 C) 算法程序所占的存儲空間 D) 算法執(zhí)行過程中所需要的存儲空間 C D 考點 2 算法復雜度 考點 3 數據結構的定義 數據結構 作為計算機的一門學科，主要研究和討論以下三個方面： （ 1）數據集合中各數據元素之間所固有的邏輯關系，即數據的 邏輯結構（ （ 2）在對數據進行處理時，各數據元素在計算機中的存儲關系，即數據的 存儲結構（ （ 3）對各種數據結構進行的 運算。 數據（ 是計算機可以保存和處理的信息。 數據元素（ 是數據的基本單位，即數據集合中的個體。有時也把數據元素稱作 結點 、 記錄 等。 據結構的基本概念 數據處理， 是指對數據集合中的各元素以各種方式進行運算，包括 插入 、 刪除 、 查找 、 更改 等運算，也包括 對數據元素進行分析 。 數據結構（ 是指相互有關聯(lián)的 數據元素 的集合。 例如，向量和矩陣就是數據結構，在這兩個數據結構中，數據元素之間有著位置上的關系。 數據元素 的含義非常廣泛，現(xiàn)實世界中存在的一切個體都可以是數據元素。 例如，描述一年四季的季節(jié)名“春、夏、秋、冬”，可以作為季節(jié)的數據元素；表示家庭成員的名字“父親、兒子、女兒”，可以作為家庭成員的數據元素。 考點 3 數據結構的定義 數據對象： 是性質相同的數據元素的集合，是數據的一個子集。 1. 數據的邏輯結構 數據的邏輯結構： 是對數據元素之間的邏輯關系的描述，它可以用一個數據元素的集合和定義在此集合中的若干關系來表示。 數據的邏輯結構與它們在計算機中的存儲位置無關 。 數據的邏輯結構有兩個要素： 一是數據元素的集合，通常記為 D； 二是 反映了數據元素之間的前后件關系，通常記為 R。 考點 3 數據結構的定義 一個數據結構可以表示成 B=（ D， R） 其中 B 表示數據結構。為了反映 D 中各數據元素之間的前后件關系，一般用二元組來表示。 例 一年四季的數據結構可以表示成 B =（ D， R） D = 春，夏，秋，冬 R = （春，夏），（夏，秋），（秋，冬） 例 家庭成員數據結構可以表示成 B =（ D， R） D = 父親，兒子，女兒 R = （父親，兒子），（父親，女兒） 考點 3 數據結構的定義 2數據的存儲結構 數據的存儲結構， 數據的邏輯結構在計算機存儲空間中的存放形式稱為數據的存儲結構（也稱 數據的物理結構 ）。 由于數據元素在計算機存儲空間中的位置關系可能與邏輯關系不同，因此，為了表示存放在計算機存儲空間中的各數據元素之間的邏輯關系（即前后件關系），在數據的存儲結構中， 不僅要存放各數據元素的信息，還需要存放各數據元素之間的前后件關系的信息 。 考點 3 數據結構的定義 2數據的存儲結構 一種數據的邏輯結構根據需要可以表示成多種存儲結構，常用的存儲結構有， 順序 、 鏈接 、索引 等存儲結構。 順序存儲 ，它是把邏輯上相鄰的結點存儲在物理位置相鄰的存儲單元里，結點間的邏輯關系由存儲單元的鄰接關系來體現(xiàn)。由此得到的存儲表示稱為 順序存儲結構 。 鏈接存儲 ，它不要求邏輯上相鄰的結點在物理位置上亦相鄰，結點間的邏輯關系是由附加的指針字段表示的。由此得到的存儲表示稱為 鏈式存儲結構 。 索引存儲 ，除建立存儲結點信息外，還建立附加的索引表來標識結點的地址。 考點 3 數據結構的定義 3. 數據結構的圖形表示 春 冬秋夏父親女兒兒子在數據結構的圖形表示中，對于數據集合 之為數據結點，簡稱 結點 。 對于關系 一條有向線段從前件結點指向后件結點。 在數據結構中，沒有前件的結點稱為 根結點 ； 沒有后件的結點稱為 終端結點 （也稱為 葉子 結點）。 考點 3 數據結構的定義 考點 4 線性結構與非線性結構 4. 線性結構與非線性結構 一個數據結構可以是空的，即一個數據元素都沒有，稱為 空的數據結構 。 一般將數據結構分為兩大類： 線性結構 與 非線性結構 。 線性結構， 如果一個非空的數據結構滿足下面兩個條件： （ 1）有且只有一個根結點；（ 2）每個結點最多有一個前件，也最多有一個后件。則稱該數據結構為 線性結構 。 線性結構又稱 線性表 。 4. 線性結構與非線性結構 如一年四季這個數據結構屬于線性結構。 需要說明的是，在一個線性結構中插入或刪除任何一個結點后還應是線性結構。 非線性結構 ，如果一個數據結構不是線性結構，則稱為非線性結構。 如 家庭成員之間輩分關系的數據結構是非線性結構。 考點 4 線性結構與非線性結構 考點 5 線性表的基本概念 線性表（ 由一組數據元素構成，數據元素的位置只取決于自己的序號，元素之間的相對位置是線性的。 線性表是由 n(n0) 個數據元素組成的一個有限序列， 表中的每一個數據元素，除了第一個外，有且只有一個前件，除了最后一個外，有且只有一個后件。 線性表中數據元素的個數稱為 線性表的長度 。 線性表可以為空表。 線性表及其順序存儲結構 線性表的順序存儲結構， 用順序存儲結構來存儲的線性表也稱為順序表。其特點如下： （ 1）順序表中所有元素所占的存儲空間是連續(xù)的； （ 2）順序表中各數據元素在存儲空間中是按邏輯順序依次存放的。 在順序表中，其前后件兩個元素在存儲空間中是緊鄰的，且前件元素一定存儲在后件元素的前面。 線性表及其順序存儲結構 考點 5 線性表的基本概念 順序表的插入、刪除運算 （ 1）順序表的插入運算： 在一般情況下，要在第 i（ 1in）個元素之前插入一個新元素時，首先要從最后一個（即第 素開始，直到第 i 個元素之間共 個元素依次向后移動一個位置，移動結束后，第 i 個位置就被空出，然后將新元素插入到第 i 項。插入結束后，線性表的長度就增加了 1。 順序表的插入運算時需要移動元素，在等概率情況下，平均需要移動 n/2 個元素。 考點 5 線性表的基本概念 順序表的插入、刪除運算 （ 2）順序表的刪除運算： 在一般情況下，要刪除第 i（ 1in）個元素時，則要從第 i+1個元素開始，直到第 元素依次向前移動一個位置。刪除結束后，線性表的長度就減小了 1。 進行順性表的刪除運算時也需要移動元素，在等概率情況下，平均需要移動 （ 。 順序表的插入、刪除運算效率很低。 考點 5 線性表的基本概念 1棧的基本概念 棧（ 是一種特殊的線性表，它是限定僅在一端進行插入和刪除運算的線性表。 其中，允許插入與刪除的一端稱為 棧頂（ 而不允許插入與刪除的另一端稱為 棧底（ 棧頂元素總是最后被插入的那個元素，從而也是最先能被刪除的元素；棧底元素總是最先被插入的元素，從而也是最后才能被刪除的元素。 棧是按照“ 先進后出”（ n “ 后進先出”（ n 原則操作數據的。由此可以看出， 棧具有記憶作用 。 考點 6 棧和隊列 棧和隊列 2棧的順序存儲及基本運算 棧的順序存儲結構是利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂的數據元素，并設有指針 向棧頂元素的位置。 用一維數組 S（ 1 m）作為棧的順序存儲空間，其中 在棧的順序存儲空間 S（ 1 m）中， S（ 棧底元素， S（ 棧頂元素。 0表示棧空； m 表示棧滿。 棧的基本運算有三種： 入棧 、 退棧 與 讀棧頂元素 。 考點 6 棧和隊列 棧和隊列 （ 1）入棧運算 ：入棧運算是指在棧頂位置插入一個新元素。首先將棧頂指針加一（即 ），然后將新元素插入到棧頂指針指向的位置。當棧頂指針已經指向存儲空間的最后一個位置時，說明棧空間已滿，不可能再進行入棧操作。這種情況稱為棧 上溢 錯誤。 （ 2）退棧運算： 退棧是指取出棧頂元素并賦給一個指定的變量。首先將棧頂元素（棧頂指針指向的元素）賦給一個指定的變量，然后將棧頂指針減一（即 ）。當棧頂指針為 0時，說明棧空，不可進行退棧操作。這種情況稱為棧的 下溢 錯誤。 （ 3）讀棧頂元素： 讀棧頂元素是指將棧頂元素賦給一個指定的變量。這個運算不刪除棧頂元素，只是將它賦給一個變量，因此棧頂指針不會改變。當棧頂指針為 0時，說明?？?，讀不到棧頂元素。 考點 6 棧和隊列 3隊列的基本概念 隊列（ 是一種特殊的線性表，它是限定僅在表的一端進行插入，而在表的另一端進行刪除的線性表。 在隊列中，允許插入的一端稱為 隊尾 ，允許刪除的一端稱為 隊頭 。 隊列是按照 “先進先出”（ n “ 后進后出”（ n 原則操作數據的，因此，隊列也被稱為“先進先出”表或“后進后出”表。 在隊列中，通常用指針 向隊頭 ，用 考點 6 棧和隊列 3隊列的基本概念 隊列的基本運算有兩種： 往隊列的隊尾插入一個元素稱為 入隊運算 ，從隊列的隊頭刪除一個元素稱為出隊運算 。 在隊列的末尾插入一個元素（ 入隊運算 ）只涉及隊尾指針 變化，而要刪除隊列中的隊頭元素（ 出隊運算） 只涉及隊頭指針 與棧類似，在程序設計語言中，用一維數組作為隊列的順序存儲空間。 用順序存儲結構存儲的隊列稱為 順序隊列 。 考點 6 棧和隊列 4循環(huán)隊列及其運算 循環(huán)隊列（ 為了充分利用存儲空間，在實際應用中，隊列的順序存儲結構一般采用循環(huán)隊列的形式，將順序存儲的隊列的最后一個位置指向第一個位置，從而使順序隊列形成邏輯上的環(huán)狀空間，稱為 循環(huán)隊列（ 在循環(huán)隊列中，用隊尾指針 向隊列中的隊尾元素，用排頭指針 向排頭元素的前一個位置，因此，從頭指針 有的元素均為隊列中的元素。 循環(huán)隊列中元素的個數 = 考點 6 棧和隊列 4循環(huán)隊列及其運算 循環(huán)隊列主要有兩種基本運算： 入隊運算 與 出隊運算 。 每進行一次 出隊運算 ，隊頭指針就加 1。當隊頭指針 n+1時，則設置 。 每進行一次 入隊運算 ，隊尾指針就加 1。當隊尾指針 n+1時，則設置 。 隊列空與隊列滿的條件： 隊列空的條件為 ； 隊列滿的條件為 l，且 考點 6 棧和隊列 1 線性鏈表的基本概念 在鏈式存儲方式中，要求 每個結點由兩部分組成 ：一部分用于存放數據元素值，稱為 數據域 ，另一部分用于存放指針，稱為 指針域 。其中指針用于指向該結點的前一個或后一個結點（即前件或后件）。 鏈式存儲方式既可用于表示線性結構，也可用于表示非線性結構。 （ 1）線性鏈表 線性表的鏈式存儲結構稱為 線性鏈表 。 考點 7 線性鏈表的基本概念 線性鏈表 在線性鏈表中，一般用一個專門的指針 用 在線性表中，最后一個元素沒有后件，所以，線性鏈表中最后一個結點的指針域為空（用 0表示）， 表示鏈表終止 。 考點 7 線性鏈表的基本概念 線性鏈表 線性鏈表的存儲結構 設有 4個學生的某門功課的成績分別是 4 個數據在內存中的存儲單元地址分別是 1248、 1488、1366 和 1522，其鏈表結構如圖 a 所示。實際上，常用圖 b 來表示它們的邏輯關系。 1248a 1148813661366a 315221522a 4 線性鏈表的基本概念 圖 a 線性鏈表的物理狀態(tài) 圖 b 線性鏈表的邏輯狀態(tài) a 1a 2 a 3 雙向鏈表 的存儲結構 在一些應用中，對線性鏈表中的每個結點 設置兩個指針域 ，一個指向其前件結點，稱為 前件指針或 左指針 ；另一指向其后件結點，稱為 后件指針 或右指針 。 這樣的線性鏈表稱為 雙向鏈表 ，其邏輯狀態(tài)如圖所示。 考點 7 線性鏈表的基本概念 圖 雙向線性鏈表的物理狀態(tài) （ 2） 帶鏈的棧 用鏈式存儲結構來存儲的棧，稱為 帶鏈的棧 ，簡稱為 鏈棧。 考點 7 線性鏈表的基本概念 圖 棧在鏈式存儲時的邏輯狀態(tài)示意圖 a a （ 3） 帶鏈的隊列 用鏈式存儲結構來存儲的隊列，稱為 帶鏈的隊列 ，簡稱為 鏈隊列 。 考點 7 線性鏈表的基本概念 圖 隊列在鏈式存儲時的邏輯狀態(tài)示意圖 在鏈式結構中，存儲空間位置關系與邏輯關系是什么？ 在鏈式存儲結構中，存儲數據結構的存儲空間可以不連續(xù)，各數據結點的存儲順序與數據元素之間的邏輯關系可以不一致，而數據元素之間的邏輯關系是由指針域來確定的。 考點 7 線性鏈表的基本概念 考點 7 線性鏈表的基本概念 2 線性鏈表的基本運算 （ 1）在線性鏈表中包含指定元素的結點之前 插入一個新元素 。 在線性鏈表中插入元素時，不需要移動數據元素，只需要修改相關結點指針即可，也不會出現(xiàn)“上溢”現(xiàn)象。 例 假設線性鏈表如圖（ a）所示?，F(xiàn)在要在線性鏈表中包含元素 a 的結點之前插入一個包含新元素 插入過程如下： 考點 7 線性鏈表的基本概念 a a a）原來的線性鏈表 （ b）申請一個由 （ d）將新結點插入到指定結點之前 （ c）在線性鏈表中找到由 a 線性鏈表的基本概念 2 線性鏈表的基本運算 （ 2）在線性鏈表中刪除包含指定元素的結點。 在線性鏈表中刪除元素時，也不需要移動數據元素，只需要修改相關結點指針即可。 （ 3）將兩個線性鏈表按要求合并成一個線性鏈表。 （ 4）將一個線性鏈表按要求進行分解。 （ 5）逆轉線性鏈表。 （ 6）復制線性鏈表。 考點 7 線性鏈表的基本概念 2 線性鏈表的基本運算 （ 7）線性鏈表的排序。 （ 8）線性鏈表的查找。 注：線性鏈表不能隨機存取。 在鏈表中，即使知道被訪問結點的序號 i，也不能像順序表中那樣直接按序號 i 訪問結點，而只能從鏈表的頭指針出發(fā)，順著鏈域逐個結點往下搜索，直至搜索到第 i 個結點為止。 因此， 鏈表不是隨機存儲結構 。 考點 7 線性鏈表的基本概念 3循環(huán)鏈表 循環(huán)鏈表（ 結構具有下面兩個特點： （ 1）在循環(huán)鏈表中 增加了一個表頭結點 。表頭結點的數據域為任意或者根據需要來設置，指針域指向線性表的第一個元素的結點。 循環(huán)鏈表的頭指針指向表頭結點 。 （ 2）循環(huán)鏈表中 最后一個結點的指針域不是空的，而是指向表頭結點 。即在循環(huán)鏈表中，所有結點的指針構成了一個環(huán)狀鏈 考點 7 線性鏈表的基本概念 3循環(huán)鏈表 下圖為循環(huán)鏈表的邏輯狀態(tài)示意圖，圖（ a）是一個非空的循環(huán)鏈表，圖（ b）是一個空的循環(huán)鏈表。 a a 1表頭結點（ a）非空循環(huán)鏈表 （ b）空循環(huán)鏈表 樹與二叉樹及其基本性質 1 樹的基本概念 樹 ( 是一種簡單的非線性結構。 在樹結構中，每一個結點只有一個前件，稱為 父結點 ，沒有前件的結點只有一個，稱為樹的 根結點 。 每一個結點可以有多個后件，它們稱為該結點的 子結點 。沒有后件的結點稱為 葉子結點 。 一個結點所擁有的后件個數稱為該 結點的度 。 葉子結點的度為 0。 在樹中，所有結點中的最大的度稱為樹的度 。樹的最大層次稱為 樹的深度。 樹與二叉樹 在筆試考試中，一般是一個必考的內容，出現(xiàn)的幾率為100%，此考點為重點掌握內容。重點識記樹及二叉樹的性質。 考點 8 樹與二叉樹及其基本性質 根結點 : 父結點 : 除根結點外，每個結點只有一個前件，稱為該結點的父結點。 葉子結點 : 節(jié)點的度數： 根結點 ； ； ； ；葉子結點的度為 0。 樹的度： G H I 樹的結構圖 A E、 F、 G、 H、 I、 J 3。 3。 樹的深度： 考點 8 樹與二叉樹及其基本性質 2 二叉樹及其基本運算 二叉樹（ 是一種非常有用的非線性數據結構。 二叉樹與前面介紹的樹結構不同，但它與樹結構很相似，并且，有關樹結構的所有術語都可以用到二叉樹上。 二叉樹的特點： 非空二叉樹只有一個根結點； 每個結點最多有兩棵子樹，且分別稱為該結點的 左子樹 與 右子樹 。 考點 8 樹與二叉樹及其基本性質 在二叉樹中，每個結點的度最大為 2，而樹結構中的每一個結點的度可以是任意的。另外，二叉樹中的每一個結點的子樹要區(qū)分為左子樹與右子樹。 例如，下圖中所示的是 4 顆不同的二叉樹。 樹與二叉樹及其基本性質 滿二叉樹與完全二叉樹： （ 1）滿二叉樹 在一顆二叉樹中，如果所有分支結點都存在左子樹和右子樹，并且所有葉子結點都在同一層上，這樣的二叉樹稱為滿二叉樹。下圖分別是深度為 2、 3的滿二叉樹。 樹與二叉樹及其基本性質 滿二叉樹與完全二叉樹： （ 2） 完全二叉樹 完全二叉樹是指除最后一層外，每一層上的結點數均達到最大值，而在最后一層上只缺少右邊的若干結點。 下圖是兩顆深度為 3的完全二叉樹。 考點 8 樹與二叉樹及其基本性質 二叉樹的基本性質： 性質 1 在二叉樹中，第 i1）。 性質 2 在深度為 點總數最多為 2k1）。 性質 3 對任意一棵二叉樹，度為 0的結點（即葉子結點）總是比度為 2的結點多一個。 性質 4 （ 1）具有 深度至少為1，其中 示取 （ 2）具有 1。 考點 8 樹與二叉樹及其基本性質 二叉樹的基本性質： 性質 5 如果對一棵有 到 一層從左到右）編號，則 對任一結點 i(1in)，有 （ 1）如果 i=1，則結點 沒有父結點；如果 i1，則其父結點編號為 i/2。 （ 2）如果 2in，則結點 點 否則，其左子結點是結點 2i。 （ 3）如果 2i+1n，則結點 則，其右子結點是結點 2i+1。 根據完全二叉樹的這個性質，如果按從上到下、從左到右順序存儲完全二叉樹的各結點，則很容易確定每一個結點的父結點、左子結點和右子結點的位置。 考點 8 樹與二叉樹及其基本性質 3 二叉樹的存儲結構 在計算機中， 二叉樹通常采用鏈式存儲結構 。 與線性鏈表類似，用于存儲二叉樹中各元素的存儲結點也 由兩部分組成 ： 數據域 和 指針域 。 但在二叉樹中，由于每一個元素可以有兩個后件（即兩個子結點），因此，用于存儲二叉樹的存儲結點的指針域有兩個： 一個用于指向該結點的左子結點的存儲地址，稱為 左指針域 ；另一個用于指向該結點的右子結點的存儲地址，稱為 右指針域 。 考點 8 樹與二叉樹及其基本性質 3 二叉樹的存儲結構 下圖是二叉樹存儲結點的示意圖。其中： L(i)是結點 即 L(i)為結點 R(i)是結點 即 R(i)為結點 V(i)是數據域 。 L(i) V(i) R(i) 樹與二叉樹及其基本性質 3 二叉樹的存儲結構 二叉樹的鏈式存儲結構也稱為二叉鏈表。下圖表示二叉鏈表的存儲示意圖。 0 0 0 E 0頭指針對于滿二叉樹與完全二叉樹來說，可按層序進行順序存儲。 這樣，不僅節(jié)省存儲空間，又方便確定每個結點的父結點與左右子結點的位置，但順序存儲結構對于一般的二叉樹不適用。 考點 8 樹與二叉樹及其基本性質 4 二叉樹的遍歷 二叉樹的遍歷是指不重復地訪問二叉樹中的所有結點。 在遍歷二叉樹的過程中，通常規(guī)定： 先遍歷左子樹，然后再遍歷右子樹 。 在先左后右的原則下，根據 訪問根結點的次序，二叉樹的遍歷可以分為三種： 前序遍歷 、 中序遍歷 、 后序遍歷 。 用 D、 L、 “ 訪問根結點 ”、“ 遍歷根結點的左子樹 ” 和 “ 遍歷根結點的右子樹 ”。 考點 8 樹與二叉樹及其基本性質 4 二叉樹的遍歷 （ 1）前序遍歷（ 若二叉樹為空，則結束返回。否則：首先訪問根結點，然后遍歷左子樹，最后遍歷右子樹；并且，在遍歷左右子樹時，仍然先訪問根結點，然后遍歷左子樹，最后遍歷右子樹。 H 則遍歷的結果為： 考點 8 樹與二叉樹及其基本性質 4 二叉樹的遍歷 （ 2）中序遍歷（ 若二叉樹為空，則結束返回。否則：首先遍歷左子樹，然后訪問根結點，最后遍歷右子樹；并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后訪問根結點，最后遍歷右子樹。 H 則遍歷的結果為： 考點 8 樹與二叉樹及其基本性質 4 二叉樹的遍歷 （ 3）后序遍歷（ 若二叉樹為空，則結束返回。否則：首先遍歷左子樹，然后遍歷右子樹，最后訪問根結點，并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根結點。 H 則遍歷的結果為： 考點 9 順序查找 1 順序查找 順序查找 又稱為 順序搜索 ，基本方法是： 從線性表的第一個元素開始，依次與被查找元素進行比較，若相等則查找成功；若所有的元素都與被查元素進行了比較，都不相等，則查找失敗。 在下列兩種情況下也只能采用順序查找： （ 1）如果線性表為無序表，則不管是順序存儲結構還是鏈式存儲結構，只能用順序查找。 （ 2）即使是有序線性表，如果采用鏈式存儲結構，也只能用順序查找。 順序查找一個 平均復雜度為 O（ n）。 查找技術 考點 10 二分法查找 2 二分法查找 二分法 只適用于順序存儲的，按非遞減排列的有序表，其方法如下： 設有序線性表的長度為 n，被查找的元素為 i， （ 1）將 i 與線性表的中間項進行比較； （ 2）若 i 與中間項的值相等，則查找成功； （ 3）若 i