【正文】 10 圖 6 3 具有 1 1 個(gè)關(guān)鍵字序列的二分查找判定樹(shù) 1 在長(zhǎng)度為 n的有序線(xiàn)性表中進(jìn)行二分查找。 把當(dāng)前查找區(qū)間的中點(diǎn)作為根結(jié)點(diǎn) ， 左子區(qū)間和右子區(qū)間分別作為根的左子樹(shù)和右子樹(shù) ， 左子區(qū)間和右子區(qū)間再按類(lèi)似的方法 ， 由此得到的二叉樹(shù)稱(chēng)為二分查找的判定樹(shù) 。 重復(fù)以上過(guò)程，直到找到滿(mǎn)足條件的記錄，使查找成功，或直到子表不存在為止，此時(shí)查找不成功。假設(shè)表中元素為升序排列。 查找 （ 折半查找 ） 高效率的查找方法。 又假設(shè)查找每個(gè)數(shù)據(jù)元素的概率相等 ， 即 Pi=1/n， 則順序查找算法的平均查找長(zhǎng)度為： ? ??? ?????????niniiniii ninnCnCPA SL1 11)1(21)1(11順序查找的特點(diǎn) 順序查找的 優(yōu)點(diǎn)是算法簡(jiǎn)單 ，對(duì)查找表結(jié)構(gòu)無(wú)任何要求，無(wú)論是用向量還是用鏈表來(lái)存放結(jié)點(diǎn)，也無(wú)論結(jié)點(diǎn)之間是否按關(guān)鍵字有序或無(wú)序排，它都同樣適用。 順序查找算法的性能 。 若用順序表 ，查找可從前往后掃描 ， 也可從后往前掃描 ， 但若采用單鏈表 ，則只能從前往后掃描 。 若找到相應(yīng)的數(shù)據(jù)元素 ， 稱(chēng)查找成功 ， 否則稱(chēng)查找失敗 5． 2 線(xiàn)性表的查找 順序查找 最簡(jiǎn)單的查找方法 順序查找的基本思想 從表的一端開(kāi)始 ， 順序掃描線(xiàn)性表 ， 依次將掃描到的結(jié)點(diǎn)關(guān)鍵字和待找的值Ｋ相比較 ， 若相等 ， 則查找成功 ， 若整個(gè)表掃描完畢 ， 仍末找到關(guān)鍵字等于Ｋ的元素 ， 則查找失敗 。 如果一個(gè)數(shù)據(jù)項(xiàng)可以 唯一標(biāo)識(shí)列表中的一個(gè)數(shù)據(jù)元素 ， 則稱(chēng)其為關(guān)鍵字 。 4 二叉樹(shù)的遍歷可以分解為：訪問(wèn)根，遍歷 左子樹(shù)和 遍歷 右子樹(shù)，常用的三種遍歷算法： 先序遍歷、中序遍歷、后序遍歷； 5 查找 查找的基本概念 查找 （ 列 ） 表：由同一類(lèi)型的數(shù)據(jù)元素 （ 或記錄 ） 構(gòu)成的集合 ， 可利用任意數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn) 。 如何訪問(wèn)二叉樹(shù)的每個(gè)結(jié)點(diǎn)， 而且每個(gè)結(jié)點(diǎn)僅被訪問(wèn)一次？ 二叉樹(shù)的遍歷方法（必考） 二叉樹(shù)由根、左子樹(shù)、右子樹(shù)三部分組成 二叉樹(shù)的遍歷 可以分解為：訪問(wèn)根，遍歷 左子樹(shù) 和 遍歷 右子樹(shù) 令 ： L： 遍歷左子樹(shù) T： 訪問(wèn)根結(jié)點(diǎn) R： 遍歷右子樹(shù) 約定先左后右 , 有三種遍歷方法： T L R前序遍歷、 L T R中序遍歷 、 L R T后序遍歷。 二、二叉樹(shù)的遍歷（必考） 遍歷 ： 按某種順序訪問(wèn)二叉樹(shù)的每個(gè)結(jié)點(diǎn)，而且每個(gè)結(jié)點(diǎn)僅被訪問(wèn)一次。 （ 3） 如 2i＋ 1n， 則序號(hào)為 i的結(jié)點(diǎn)無(wú)右孩子；如 2i＋ 1≤n， 則序號(hào)為 i的結(jié)點(diǎn)的右孩子結(jié)點(diǎn)的序號(hào)為 2i＋ 1。 性質(zhì) 4：具有 n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為 ［ log2n］ +1。 8 9 10 11 12 134 52136 714 15 8 9 10 11 12 134 52136 714( a ) 滿(mǎn)二叉樹(shù) ( b ) 完全二叉樹(shù) 完全二叉樹(shù)： 深度為 k， 結(jié)點(diǎn)數(shù)為 n的二叉樹(shù) ， 如果其結(jié)點(diǎn) 1~n的位置序號(hào)分別與滿(mǎn)二叉樹(shù)的結(jié)點(diǎn) 1~n的位置序號(hào)一一對(duì)應(yīng) ， 則為完全二叉樹(shù) ， 如上圖 (b)所示 。 兩種特殊的二叉樹(shù) 滿(mǎn)二叉樹(shù)：深度為 k的二叉樹(shù)，如有 2k1個(gè)結(jié)點(diǎn)則稱(chēng)為滿(mǎn)二叉樹(shù)； A G F E D C B A C B K=3的滿(mǎn)二叉樹(shù) K=2的滿(mǎn)二叉樹(shù) 滿(mǎn)二叉樹(shù)的順序表示： 從二叉樹(shù)的根開(kāi)始 ， 從上到下 ， 從左到右 ， 逐層進(jìn)行編號(hào) （ 1， 2， …， n） 。 性質(zhì) 2: 深度為 k的二叉樹(shù)至多有 2k1個(gè)結(jié)點(diǎn) （ k≥1） 。 3）二叉樹(shù)是遞歸結(jié)構(gòu)，在二叉樹(shù)的定義中又用到了二叉樹(shù)的概念 。 A F G E D C B 一 二叉樹(shù)的概念 二叉樹(shù) 說(shuō)明 1）二叉樹(shù)中每個(gè)結(jié)點(diǎn)最多有兩個(gè)子樹(shù)； 既：二叉樹(shù)每個(gè)結(jié)點(diǎn)度小于等于 2。 文件夾 1 文件夾 n 文件 1 文件 2 文件夾 11 文件夾 12 文件 11 文件 12 C盤(pán) 樹(shù)的 基本術(shù)語(yǔ) 樹(shù)的結(jié)點(diǎn)：包含一個(gè)數(shù)據(jù)元素及若干指 向子樹(shù)的分支； 孩子結(jié)點(diǎn)：結(jié)點(diǎn)的子樹(shù)的根稱(chēng)為該結(jié)點(diǎn) 的孩子， B、 C是 A的孩子； 雙親結(jié)點(diǎn)： B 結(jié)點(diǎn)是 A 結(jié)點(diǎn)的孩子，則 A 結(jié)點(diǎn)是 B 結(jié)點(diǎn)的雙親； 兄弟結(jié)點(diǎn)：同一雙親的孩子結(jié)點(diǎn)， H、 I、 J互為兄弟； 堂兄結(jié)點(diǎn) ： 同一層上結(jié)點(diǎn)， E、 F、 G、 H、 I、 J、 互為堂兄弟； J I A C B D H G F E K L M 樹(shù)的 基本術(shù)語(yǔ) 結(jié)點(diǎn)的層次：根結(jié)點(diǎn)的層次定義為 1；根的孩子為第二層，依此類(lèi)推； 樹(shù)的深度： 樹(shù)中所有結(jié)點(diǎn)的層次的最大值 結(jié)點(diǎn)的度： 結(jié)點(diǎn)子樹(shù)的個(gè)數(shù) 樹(shù)的度： 樹(shù)中結(jié)點(diǎn)度的最大值。 J I A C B D H G F E K L M 2．樹(shù)的實(shí)例 樹(shù)可表示具有分枝結(jié)構(gòu)關(guān)系的對(duì)象 例 1．家族族譜 設(shè)某家庭有 13個(gè)成員 A、 B、 C、 D、 E、 F、 G、 H、I、 J、 K、 L、 M，他們之間的關(guān)系可用樹(shù)表示： J I A C B D H G F E K L M 計(jì)算機(jī)中樹(shù)是常用的數(shù)據(jù)組織形式 盡管有些應(yīng)用中數(shù)據(jù)元素之間并不存在分支結(jié)構(gòu)關(guān)系，但為了便于管理和使用數(shù)據(jù)，將它們用樹(shù)的形式來(lái)組織。 （ 2022年 3月） 答案： 19 答案： 15 4 樹(shù)和二叉樹(shù) 1．樹(shù)的定義 樹(shù)是 n個(gè)結(jié)點(diǎn)的有限集合 T，當(dāng) n=0時(shí)，稱(chēng)為空樹(shù)；當(dāng) n0時(shí)， T滿(mǎn)足如下條件：在任一棵非空樹(shù)中： （ 1）有且僅有一個(gè)稱(chēng)為根的結(jié)點(diǎn)。（ ） 答案： A， B， C， D， E， F， 5， 4， 3， 2， 1 9. 設(shè)某循環(huán)隊(duì)列的容量為 50，如果頭指針 front=45(指向隊(duì)頭元素的前一位置 )，尾指針 rear=10(指向隊(duì)尾元素 )，則該循環(huán)隊(duì)列中共有 【 2】 個(gè)元素。 7. 一個(gè)隊(duì)列的初始狀態(tài)為空。 A） 順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)一定是連續(xù)的 ， 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的存儲(chǔ)空間不一定是連續(xù)的 B） 順序存儲(chǔ)結(jié)構(gòu)只針對(duì)線(xiàn)性結(jié)構(gòu) ， 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)只針對(duì)非線(xiàn)性結(jié)構(gòu) C） 順序存儲(chǔ)結(jié)構(gòu)能存儲(chǔ)有序表 ， 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)不能存儲(chǔ)有序表 D） 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)比順序存儲(chǔ)結(jié)構(gòu)節(jié)省存儲(chǔ)空間 答案： A。 答案：線(xiàn)性結(jié)構(gòu)。 A） 循環(huán)隊(duì)列 B) 帶鏈隊(duì)列 C) 二叉樹(shù) D） 帶鏈棧 答案： D。 A） 棧是 “ 先進(jìn)先出 ” 的線(xiàn)性表 B） 隊(duì)列是 “ 先進(jìn)后出 ” 的線(xiàn)性表 C） 循環(huán)隊(duì)列是非線(xiàn)性結(jié)構(gòu) D） 有序線(xiàn)性表既可以采用順序存儲(chǔ)結(jié)構(gòu) ， 也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 3. 數(shù)據(jù)結(jié)構(gòu)分為線(xiàn)性結(jié)構(gòu)和非線(xiàn)性結(jié)構(gòu) ， 帶鏈的隊(duì)列屬于 （ ） 。 或少用一個(gè)空間 Real+1=front 為滿(mǎn) front 5 4 0 3 1 2 J6 J7 J8 J4 J5 （ c） rear 入隊(duì)操作 ： 將元素 x 插入隊(duì)尾 front rear 5 4 0 3 1 2 J1 J3 J2 x front rear 5 4 0 3 1 2 J1 J3 J2 元素 x 入隊(duì)前 元素 x 入隊(duì)后 出隊(duì)操作 ：刪除隊(duì)頭 元素； front rear 5 4 0 3 1 2 J1 J3 J2 出隊(duì)操作前 front rear 5 4 0 3 1 2 J1 J3 J2 出隊(duì)操作后 小 結(jié) 1 隊(duì)列是限定僅能在表尾一端進(jìn)行插入，表頭一端刪除 操作的線(xiàn)性表； 2 隊(duì)列中的元素具有先進(jìn)先出的特點(diǎn)； 3 隊(duì)頭、隊(duì)尾元素的位置分別由稱(chēng)為隊(duì)頭指針和隊(duì)尾指針的變量指示， 4 入隊(duì)操作要修改隊(duì)尾指針，出隊(duì)操作要修改隊(duì)頭指針； 數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)方面的考題 1：數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指 （ ） 。 2） S=0 隊(duì)空： front=rear。 棧的插入操作稱(chēng)為 進(jìn)?；蛉霔?， 刪除操作稱(chēng)為 出?；蛲藯?。 表的另一端稱(chēng)為棧底 (Bottom)。 在線(xiàn)性鏈表存儲(chǔ)結(jié)構(gòu)下，線(xiàn)性表的插入、刪除操作，通過(guò)修改指針實(shí)現(xiàn)。 這樣形成的鏈表中就有兩條方向不同的鏈 ， 稱(chēng)為雙向鏈表 。如將一個(gè)鏈表鏈在另一個(gè)鏈表的后面； 對(duì)循環(huán)鏈表，有時(shí)不給出頭指針，而是給出尾指針 a a1 an anext 給出尾指針的循環(huán)鏈表 雙向鏈表 循環(huán)單鏈表 ， 雖然從任一結(jié)點(diǎn)出發(fā)沿著指針鏈能找到其前件 ， 但時(shí)間耗費(fèi)是 O(n) 。 free(q)。 head z y x p y x z p head a q 插入操作功能：在線(xiàn)性鏈表的第 i個(gè)元素結(jié)點(diǎn)之前插入一個(gè)新元素結(jié)點(diǎn) e； 插入操作圖示： 插入前 插入后 ai1 ai a2 a1 ai+1 n anhead ai1 ai a2 a1 ai+1 n ane head 4） 刪除結(jié)點(diǎn) q=pnext。 qnext=p next。 頭結(jié)點(diǎn)： 鏈表的第一個(gè)元素結(jié)點(diǎn)前的附加結(jié)點(diǎn)； 帶頭結(jié)點(diǎn)的線(xiàn)性鏈表 ：第一個(gè)元素結(jié)點(diǎn)前增加一個(gè)附加結(jié)點(diǎn)的線(xiàn)性鏈表稱(chēng)為 帶頭結(jié)點(diǎn)的線(xiàn)性鏈表； head是頭指針 ai1 ai a2 a1 ai+1 n an 頭結(jié)點(diǎn) 空指針 head 線(xiàn)性鏈表的每個(gè)結(jié)點(diǎn)中只有一個(gè)指針域 故也稱(chēng)為 單鏈表 插入結(jié)點(diǎn) (存 a) q=(LNODE *)malloc(sizeof(LNODE))。 線(xiàn)性鏈表有關(guān)術(shù)語(yǔ) 存儲(chǔ)數(shù)據(jù)元素 存儲(chǔ)后繼結(jié)點(diǎn) 存儲(chǔ)地址 結(jié)點(diǎn) 數(shù)據(jù)域 指針域 頭指針： 存放線(xiàn)性鏈表中第一個(gè)結(jié)點(diǎn)的存儲(chǔ)地址 。 用鏈表存儲(chǔ)線(xiàn)性表時(shí)，數(shù)據(jù)元素之間的關(guān)系是通過(guò) 保存直接后繼元素的存儲(chǔ)位置來(lái)表示的 ai1 ai a2 a1 ai+1 n a結(jié)點(diǎn)： 數(shù)據(jù)元素及直接后繼的存儲(chǔ)位置（地址）組成一個(gè)數(shù)據(jù)元素的存儲(chǔ)結(jié)構(gòu)，稱(chēng)為一個(gè)結(jié)點(diǎn)； 結(jié)點(diǎn)的數(shù)據(jù)域 ： 保存數(shù)據(jù)元素 。 為了表示線(xiàn)性表中元素的先后關(guān)系，每個(gè)元素除需要存儲(chǔ)自身的信息外，還要保存直接前趨元素或直接后繼元素的存儲(chǔ)位置。 a1 a2 ai1 ai ai+1 an 0 1 i1 i2 n1 . . 由此可見(jiàn) 在順序表中插入一個(gè)元素 ，平均要移動(dòng)表的一半元素。 線(xiàn)性表的概念 設(shè) A=（ a1, a2, ... , ai 1, ai , ai+1, …, a n ）是一線(xiàn)性表， 1） 同一線(xiàn)性表中的元素必須是 同一類(lèi)型 的； 2） 在表中 ai1 領(lǐng)先于 ai ， ai 領(lǐng)先于 ai+1 ，稱(chēng) ai1 是 ai 的前件， ai+1 是 ai 的后件； 3） 在線(xiàn)性表中，除第一個(gè)元素和最后一個(gè)元素之外，其他元素都有且 僅有一個(gè)前件，有且僅有一個(gè)后件 ； 4） 線(xiàn)性表中元素的個(gè)數(shù) n 稱(chēng)為線(xiàn)性表的長(zhǎng)度， n=0 時(shí)稱(chēng)為空表； 用 一組連續(xù)的內(nèi)存單元依次存放 線(xiàn)性表的數(shù)據(jù)元素。 ? 棧、隊(duì)列、串 是特殊的線(xiàn)性表 ?數(shù)組和廣義表 是線(xiàn)性表的擴(kuò)展 線(xiàn)性結(jié)構(gòu) 例、英文字母表（ A, B, C, D, E? Z ）。 數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)和數(shù)據(jù)之間關(guān)系的一門(mén)學(xué)科，研究以下三方面內(nèi)容： ? 數(shù)據(jù)的邏輯結(jié)構(gòu) ? 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) ? 數(shù)據(jù)的運(yùn)算 常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)