嚴(yán)蔚敏數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)整理完整版

1、本文格式為Word版，下載可任意編輯 嚴(yán)蔚敏數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)整理完整版 1.繁雜性分析 對各種操作的時間繁雜性的分析。 主要是鏈表，樹，排序等簡單一些的分析。 分析的時候，從簡單的入手，學(xué)會方法。 后續(xù)的各種豆可能讓你分析時間繁雜度。 線性鏈表（順序表和單鏈表） 鏈表循環(huán)鏈表 雙向鏈表 2.線性結(jié)構(gòu)隊列（循環(huán)隊列） 棧 鏈表主要操作：找某一個元素，插入一個（在哪個位置增加），刪除一個（在哪個位置刪除）。棧：查找，插入（位置固定），刪除（位置固定） 隊列：查找，插入（位置固定），刪除（位置固定） 順序表（可以視為一個數(shù)組） 單鏈表： （刪除） （插入） 倒置： （查找） 循環(huán)鏈表 雙向鏈表 棧： （

2、插入刪除查找） 隊列 （插入刪除查找） 循環(huán)隊列的實現(xiàn)，并不是像上面的圖那樣，實現(xiàn)了一個循環(huán)的樣子。 3.二叉樹 基本概念 二叉樹是每個節(jié)點(diǎn)最多有兩個子樹的有序樹。二叉樹常被用于實現(xiàn)二叉查找樹和二叉堆。值得注意的是，二叉樹不是樹的特別情形。 二叉樹是每個結(jié)點(diǎn)最多有兩個子樹的有序樹。尋常根的子樹被稱作“左子樹（left subtree）和“右子樹（right subtree）。二叉樹常被用作二叉查找樹和二叉堆或是二叉排序樹。二叉樹的每個結(jié)點(diǎn)至多只有二棵子樹(不存在出度大于2的結(jié)點(diǎn))，二叉樹的子樹有左右之分，次序不能顛倒。 二叉樹不是樹的一種特別情形，盡管其與樹有大量相像之處，但樹和二叉樹有兩個主

3、要區(qū)別： 1. 樹中結(jié)點(diǎn)的最大度數(shù)沒有限制，而二叉樹結(jié)點(diǎn)的最大度數(shù)為2； 2. 樹的結(jié)點(diǎn)無左、右之分，而二叉樹的結(jié)點(diǎn)有左、右之分。 二叉樹是遞歸定義的，其結(jié)點(diǎn)有左右子樹之分，規(guī)律上二叉樹有五種基本形態(tài)： (1)空二叉樹如圖(a)； (2)只有一個根結(jié)點(diǎn)的二叉樹如圖(b)； (3)只有左子樹如圖(c)； (4)只有右子樹如圖(d)； (5)完全二叉樹如圖(e) 注意：盡管二叉樹與樹有大量相像之處，但二叉樹不是樹的特別情形 性質(zhì) (1) 在非空二叉樹中，第i層的結(jié)點(diǎn)總數(shù)不超過 , i=1； (2) 深度為h的二叉樹最多有2h-1個結(jié)點(diǎn)(h=1)，最少有h個結(jié)點(diǎn)； (3) 對于任意一棵二叉樹，假如其

4、葉結(jié)點(diǎn)數(shù)為N0，而度數(shù)為2的結(jié)點(diǎn)總數(shù)為N2，則N0=N2+1； (4) 具有n個結(jié)點(diǎn)的完全二叉樹的深度為 (5)有N個結(jié)點(diǎn)的完全二叉樹各結(jié)點(diǎn)假如用順序方式存儲，則結(jié)點(diǎn)之間有如下關(guān)系： 若I為結(jié)點(diǎn)編號則假如I1，則其父結(jié)點(diǎn)的編號為I/2； 假如2*IN，則無左兒子； 假如2*I+1N，則無右兒子。 (6)給定N個節(jié)點(diǎn)，能構(gòu)成h(N)種不同的二叉樹。h(N)為卡特蘭數(shù)的第N項。h(n)=C(2*n，n)/(n+1)。 （7）設(shè)有i個枝點(diǎn)，I為所有枝點(diǎn)的道路長度總和，J為葉的道路長度總和J=I+2i 存儲結(jié)構(gòu) 順序存儲表示 二叉樹可以用數(shù)組或線性表來存儲，而且假如這是滿二叉樹，這種方法不會浪費(fèi)空間。

5、用這種緊湊排列，假如一個結(jié)點(diǎn)的索引為i，它的子結(jié)點(diǎn)能在索引2i+1和2i+2找到，并且它的父節(jié)點(diǎn)（假如有）能在索引floor(i-1)/2)找到（假設(shè)根節(jié)點(diǎn)的索引為0）。這種方法更有利于緊湊存儲和更好的訪問的局部性，特別是在前序遍歷中。然而，它需要連續(xù)的存儲空間，這樣在存儲高度為h的n個結(jié)點(diǎn)組成的一般普通樹時將會浪費(fèi)好多空間。一種最極壞的狀況下假如深度為h的二叉樹每個節(jié)點(diǎn)只有右孩子需要占用2的h次冪減1，而實際卻只有h個結(jié)點(diǎn)，空間的浪費(fèi)太大，這是順序存儲結(jié)構(gòu)的一大缺點(diǎn)。 /* 二叉樹的順序存儲表示 */ #define MAX_TREE_SIZE 100 /* 二叉樹的最大節(jié)點(diǎn)數(shù) */ typ

6、edef TElemType SqBiTreeMAX_TREE_SIZE; /* 0號單元存儲根節(jié)點(diǎn) */ typedef struct int level,order; /* 節(jié)點(diǎn)的層，本層序號(按滿二叉樹計算) */ position; 二叉鏈表存儲表示 /* 二叉樹的二叉鏈表存儲表示 */ typedef struct BiTNode TElemType data; struct BiTNode *lchild,*rchild; /* 左右孩子指針 */ BiTNode,*BiTree; 遍歷算法 二叉樹的遍歷三種方式，如下： （1）前序遍歷（DLR），首先訪問根結(jié)點(diǎn)，然后遍歷左子樹，結(jié)

7、果遍歷右子樹。簡記根-左-右。 （2）中序遍歷（LDR），首先遍歷左子樹，然后訪問根結(jié)點(diǎn)，結(jié)果遍歷右子樹。簡記左-根-右。 （3）后序遍歷（LRD），首先遍歷左子樹，然后遍歷右子樹，結(jié)果訪問根結(jié)點(diǎn)。簡記左-右-根。 例1：如上圖所示的二叉樹，若按前序遍歷，則其輸出序列為。若按中序遍歷，則其輸出序列為。若按后序遍歷，則其輸出序列為。 前序：根A，A的左子樹B，B的左子樹沒有，看右子樹，為D，所以A-B-D。再來看A的右子樹，根C，左子樹E，E的左子樹F，E的右子樹G，G的左子樹為H，沒有了終止。連起來為C-E-F-G-H,結(jié)果結(jié)果為ABDCEFGH 中序：先訪問根的左子樹,B沒有左子樹，其有右子

8、樹D，D無左子樹，下面訪問樹的根A，連起來是BDA。 再訪問根的右子樹，C的左子樹的左子樹是F，F(xiàn)的根E，E的右子樹有左子樹是H，再從H出發(fā)找到G，到此C的左子樹終止，找到根C，無右子樹，終止。連起來是FEHGC, 中序結(jié)果連起來是BDAFEHGC 后序：B無左子樹，有右子樹D，再到根B。再看右子樹，最下面的左子樹是F，其根的右子樹的左子樹是H，再到H的根G，再到G的根E，E的根C 無右子樹了，直接到C，這時再和B找它們其有的根A，所以連起來是DBFHGECA 深度優(yōu)先遍歷 在深度優(yōu)先中，我們希望從根結(jié)點(diǎn)訪問最遠(yuǎn)的結(jié)點(diǎn)。和圖的深度優(yōu)先探尋不同的是，不需記住訪問過的每一個結(jié)點(diǎn)，由于樹中不會有環(huán)。

9、 廣度優(yōu)先遍歷 和深度優(yōu)先遍歷不同，廣度優(yōu)先遍歷會先訪問離根節(jié)點(diǎn)最近的節(jié)點(diǎn)。 完全二叉樹，滿二叉樹 1.滿二叉樹：一棵深度為k，且有個節(jié) 點(diǎn)稱之為滿二叉樹 2.完全二叉樹：深度為k，有n個節(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個節(jié)點(diǎn)都與深度為k 的滿二叉樹中，序號為1至n的節(jié)點(diǎn)對應(yīng)時，稱之為完全二叉樹 4.樹 基本概念 樹（tree）是包含n（n0）個結(jié)點(diǎn)的有窮集，其中： （1）每個元素稱為結(jié)點(diǎn)（node）； （2）有一個特定的結(jié)點(diǎn)被稱為根結(jié)點(diǎn)或樹根（root）。 （3）除根結(jié)點(diǎn)之外的其余數(shù)據(jù)元素被分為m（m0）個互不相交的集合T1，T2，Tm-1，其中每一個集合Ti（1=0）棵互不相交的樹的集合稱為森

10、林； 存儲 父節(jié)點(diǎn)表示法 /* 樹節(jié)點(diǎn)的定義 */#define MAX_TREE_SIZE 100typedef struct TElemType data; int parent; /* 父節(jié)點(diǎn)位置域 */ PTNode;typedef struct PTNode nodesMAX_TREE_SIZE; int n; /* 節(jié)點(diǎn)數(shù) */ PTree; 孩子鏈表表示法 /*樹的孩子鏈表存儲表示*/typedef struct CTNode / 孩子節(jié)點(diǎn) int child; struct CTNode *next; *ChildPtr;typedef struct ElemType data； / 節(jié)點(diǎn)的數(shù)據(jù)元素 ChildPtr firstchild； / 孩子鏈表頭指針 CTBox;typedef struct CTBox nodesMAX_TREE_SIZE； int n, r； / 節(jié)點(diǎn)數(shù)和根節(jié)點(diǎn)的位置 CTree; 5.森林 6.森林、樹與二叉樹的轉(zhuǎn)換 將樹轉(zhuǎn)換為二叉樹 樹中每個結(jié)點(diǎn)最多只有一個最左邊的孩子(長子)和一個右鄰的兄弟。依照這種關(guān)系很自然地就能將樹轉(zhuǎn)換成相應(yīng)的二叉樹： 在所有兄弟結(jié)點(diǎn)之間加一連線； 對每個結(jié)點(diǎn)，除了保存與其長子的連線外，去掉該結(jié)點(diǎn)與其它孩子的連線。 注意： 由于樹根沒有兄弟，故樹轉(zhuǎn)化為二叉樹后，二叉樹的根結(jié)點(diǎn)的右子樹必為空。 2）將一個