西安交通大學(xué)數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料(存儲(chǔ)版)
【正文】 結(jié)點(diǎn)的路徑上經(jīng)過(guò)的所有分支結(jié)點(diǎn)v 結(jié)點(diǎn)層次：從根結(jié)點(diǎn)開(kāi)始，根結(jié)點(diǎn)為第1層，根結(jié)點(diǎn)的孩子為第2層，依此類(lèi)推 1 A ………..第1層 2 B 3 C 4 D …. 第2層 5 E 6 F G 7 ……... 第3層樹(shù)的深度：樹(shù)中結(jié)點(diǎn)的最大層次。 用數(shù)學(xué)歸納法證明： 對(duì)于 i=1, ki1 =k0 =1 命題成立。 證明：設(shè)k叉樹(shù)的最小深度為h，則： 前h1層滿(mǎn)的 k叉樹(shù)結(jié)點(diǎn)數(shù) n≤ h層都滿(mǎn)的k叉樹(shù)結(jié)點(diǎn)數(shù)，因此有： 上式可變換為： kh1 n (k1)+1 ≤ kh 以k為底取對(duì)數(shù)可得： h1 logk( n(k1)+1) ≤h 即： logk( n(k1)+1) ≤h logk( n(k1)+1)+1因k只能為整數(shù)，所以： h=233。它是一種樹(shù)結(jié)構(gòu),在計(jì)算機(jī)領(lǐng)域有著廣泛地應(yīng)用。n/2n/2 此性質(zhì)可以從樹(shù)的相應(yīng)性質(zhì)中直接導(dǎo)出，也可以進(jìn)行如下證明。 特點(diǎn): v 除最后一層，第 i層有2i1個(gè)結(jié)點(diǎn)； v 葉子只可能出現(xiàn)在最后兩層；v 結(jié)點(diǎn)右子樹(shù)深度為i時(shí)，左子樹(shù)深度為i或i+1。 （遍歷的過(guò)程與先根級(jí)的遞歸遍歷類(lèi)似） ② 訪(fǎng)問(wèn)根結(jié)點(diǎn)； ③ 中序遍歷右子樹(shù) （遍歷過(guò)程與先根級(jí)的遞歸遍歷相同）(3) 后序遍歷：若二叉樹(shù)為空，則空操作；否則 ① 后序遍歷左子樹(shù)； ② 后序遍歷右子樹(shù)。 由此可知，在二叉搜索樹(shù)上查找比在集合或線(xiàn)性表上進(jìn)行順序查找的時(shí)間復(fù)雜度O(n)要小得多，這正是構(gòu)造二叉搜索樹(shù)的優(yōu)勢(shì)所在。也就是說(shuō)，在二叉樹(shù)中，一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的路徑。 能根據(jù)給定的權(quán)值集合和結(jié)點(diǎn)集合構(gòu)成具有n個(gè)結(jié)點(diǎn)的哈夫曼樹(shù)(1) 根據(jù)與n個(gè)權(quán)值{w1,w2,…,wn}對(duì)應(yīng)的n個(gè)結(jié)點(diǎn)構(gòu)成具有n棵二叉樹(shù)的森林F={T1,T2,…,Tn}，其中每棵二叉樹(shù)Ti(1≤i≤n)都只有一個(gè)權(quán)值為wi的根結(jié)點(diǎn)，其左、右子樹(shù)均為空； (2) 在森林F中選出兩棵根結(jié)點(diǎn)的權(quán)值最小的樹(shù)作為一棵新樹(shù)的左、右子樹(shù)，且置新樹(shù)的根結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)上根結(jié)點(diǎn)的權(quán)值之和； (3) 從F中刪除構(gòu)成新樹(shù)的那兩棵樹(shù)，同時(shí)把新樹(shù)加入F中； (4) 重復(fù)(2)和(3)步，直到F中只含有一棵樹(shù)為止，此樹(shù)便是哈夫曼樹(shù)第七章 圖了解圖的定義以及基本性質(zhì)v 圖中的每個(gè)頂點(diǎn)，都允許有任意個(gè)前驅(qū)和后繼，即對(duì)每個(gè)頂點(diǎn)的前驅(qū)和后繼個(gè)數(shù)均不加以限制v 對(duì)于一個(gè)圖G，若E是有序?qū)Φ募希瑒t每個(gè)有序?qū)?duì)應(yīng)圖形中的一條有向邊，若E是無(wú)序?qū)Φ募希瑒t每個(gè)無(wú)序?qū)?duì)應(yīng)圖形中的一條無(wú)向邊，所以可把E看做為邊的集合。E(G)； A[i,j]= 237。v 圖的鄰接矩陣的存儲(chǔ)需要占用n n個(gè)整數(shù)存儲(chǔ)位置，所以其空間復(fù)雜度為O(n2)。在這三個(gè)域中，鄰接點(diǎn)域和鏈域是必不可少的，權(quán)域可根據(jù)情況取舍，若表示的是無(wú)權(quán)圖，則可省去此域。第九章 排序v 熟悉直接插入排序的方法以及描述其排序性能的指標(biāo)v 熟悉直接選擇排序、堆排序和交換排序的方法、性質(zhì)以及描述排序性能的指標(biāo)v 熟悉快速排序和歸并排序的方法、性質(zhì)及指標(biāo)v 通過(guò)比較各排序方法性能（時(shí)間復(fù)雜度和空間復(fù)雜度等）熟悉如何選擇合適的排序方法。v vi鄰接表中的結(jié)點(diǎn)數(shù)，對(duì)于無(wú)向圖來(lái)說(shuō)，等于vi的邊數(shù)，或鄰接點(diǎn)數(shù)或度數(shù)；對(duì)于有向圖來(lái)說(shuō)，等于vi的出邊數(shù)、或出邊鄰接點(diǎn)數(shù)或出度數(shù)。v 在有向圖中, 統(tǒng)計(jì)第 i 行 中1的個(gè)數(shù)可得頂點(diǎn) i 的出度，統(tǒng)計(jì)第 j 列中 1 的個(gè)數(shù)可得頂點(diǎn) j 的入度。 236。v 哈夫曼(Huffman)樹(shù)又稱(chēng)作最優(yōu)二叉樹(shù)。v 堆頂結(jié)點(diǎn)具有最小值(——對(duì)應(yīng)于小根堆）或最大值（—— 對(duì)應(yīng)于大根堆)。了解二叉搜索樹(shù)應(yīng)用于查找時(shí)的特性及指標(biāo)v 在二叉搜索樹(shù)上進(jìn)行查找的過(guò)程中，給定值item同樹(shù)中結(jié)點(diǎn)比較的次數(shù)最少為一次（即樹(shù)根結(jié)點(diǎn)就是待查的結(jié)點(diǎn))，最多為樹(shù)的深度，所以平均查找次數(shù)要小于等于樹(shù)的深度。lchilddataparentrchild熟悉二叉樹(shù)的4種遍歷方法，能按任何一種遍歷方法來(lái)寫(xiě)出給定樹(shù)的遍歷序列(1) 先序遍歷：若二叉樹(shù)為空，則空操作；否則① 訪(fǎng)問(wèn)根結(jié)點(diǎn)； ② 先序遍歷左子樹(shù)； { 先訪(fǎng)問(wèn)左子樹(shù)根節(jié)點(diǎn)；再遍歷左子樹(shù)根節(jié)點(diǎn)的左子樹(shù)，再遍歷左子樹(shù)根節(jié)點(diǎn)的右子樹(shù)；……直至遍歷完所有左子樹(shù)的節(jié)點(diǎn)}③ 先序遍歷右子樹(shù)。 第i層有2i1個(gè)結(jié)點(diǎn)；全部分支結(jié)點(diǎn)度為2。log2n (3) 若編號(hào)為i的結(jié)點(diǎn)有左孩子，則左孩子結(jié)點(diǎn)的編號(hào)為2i；若編號(hào)為i的結(jié)點(diǎn)有右孩子，則右孩子結(jié)點(diǎn)的編號(hào)為2i+1，即遵循對(duì)一般二叉樹(shù)的編號(hào)規(guī)則。 由于在二叉樹(shù)中，任一結(jié)點(diǎn)的度數(shù)小于或等于2，所以其結(jié)點(diǎn)總數(shù)n為: n = n0 + n1 + n2 (n0 :終端結(jié)點(diǎn)。 表示對(duì)x進(jìn)行向上取整熟悉二叉樹(shù)的定義及基本性質(zhì)，并能根據(jù)這些性質(zhì)進(jìn)行相關(guān)推理和計(jì)算。logk(n(k1)+1)249。 證明：根據(jù)定義：除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)有一個(gè)分支指向。v 兄弟結(jié)點(diǎn)(sibling)：同一個(gè)雙
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1