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