樹和二叉樹樹的概念

樹和二叉樹樹的概念

存儲(chǔ)結(jié)構(gòu)和運(yùn)算樹和二叉樹的性質(zhì)二叉樹的概念第五章二叉樹的五種基本形態(tài)：空樹N只含根結(jié)點(diǎn)NL右子樹為空NR左子樹為空NRL左右子樹均不為空樹E

ADBCF

rootleftdataright結(jié)點(diǎn)結(jié)構(gòu):二叉鏈表先（根）序的遍歷算法

DLR中（根）序的遍歷算法

LDR后（根）序的遍歷算法

LRD先右后左的遍歷算法

RLDRDLDRLABCGFHEID

A,B,C,D,E,F,G,H,I層次遍歷序列:

前序遍歷遞歸算法

voidPreorder(BTreeNode*BT){if(BT!=NULL){cout<<BT->data<<'';//D訪問根結(jié)點(diǎn)

Preorder(BT->left);//L遍歷左子樹

Preorder(BT->right);//R遍歷右子樹

}}由二叉樹的先序和中序序列建樹先序序列中序序列左子樹左子樹右子樹右子樹根根建立二叉樹

以字符串的形式定義一棵二叉樹

采用廣義表表示的輸入法定義一棵二叉樹ABCDEFGABCEDFGrootABCEDFG

二叉鏈表(孩子-兄弟）存儲(chǔ)樹的遍歷樹的遍歷可有三條搜索路徑:先根(次序)遍歷:后根(次序)遍歷:按層次遍歷:

ABCDEFGHIJKqGTAGHFEDCBABCDEFGHIJK按層遍歷樹

二叉樹的應(yīng)用二叉搜索樹堆

哈夫曼第六章二叉搜索樹的定義1．定義2．查找算法3．插入算法4．刪除算法5．查找性能的分析二叉鏈表作為二叉搜索樹的存儲(chǔ)結(jié)構(gòu)structBTreeNode{ElemTypedata;

BTreeNode*left;

BTreeNode*right;};“插入”操作在查找不成功時(shí)才進(jìn)行；二叉搜索樹的插入算法若二叉搜索樹為空樹，則新插入的結(jié)點(diǎn)為根結(jié)點(diǎn)；否則，新插入的結(jié)點(diǎn)必為一個(gè)葉子結(jié)點(diǎn)，其插入位置由查找過程得到。（1）被刪除的結(jié)點(diǎn)是葉子；（2）被刪除的結(jié)點(diǎn)只有左子樹

或者只有右子樹；（3）被刪除的結(jié)點(diǎn)既有左子樹，也有右子樹。二叉搜索樹的刪除算法可分三種情況討論：（1）被刪除的結(jié)點(diǎn)是葉子結(jié)點(diǎn)其雙親結(jié)點(diǎn)相應(yīng)指針域改為“空”（2）被刪除的結(jié)點(diǎn)只有單支子樹

其雙親結(jié)點(diǎn)的相應(yīng)指針域改為“指向被刪除結(jié)點(diǎn)的左子樹或右子樹”。p

右子樹為空只需重接它的左子樹s=p->left;p->left=q;delete(s);pqs=p->right;p->right=q;delete(s);qp左子樹為空只需重接它的右子樹ps=p->left;p->left=q;delete(s);s=p->right;p->right=q;delete(s);qq（3）被刪除的結(jié)點(diǎn)有左右子樹被刪結(jié)點(diǎn)前驅(qū)結(jié)點(diǎn)以其前驅(qū)替代之，然后再刪除該前驅(qū)結(jié)點(diǎn)左子樹中“最右下”的結(jié)點(diǎn)（左指針可能不為空）

（3）被刪除的結(jié)點(diǎn)有左右子樹以其后繼替代之，然后再刪除后繼結(jié)點(diǎn)右子樹中“最左下”的結(jié)點(diǎn)（左指針可能不為空）堆是滿足下列性質(zhì)的數(shù)列{r1,r2,…，rn}：或(小頂堆)(大頂堆)對(duì)于完全二叉樹r2i

是ri

的左孩子r2i+1

是ri

的右孩子structHeap{ElemTypeheap[HeapMaxSize];intsize;};

//HeapMaxSize事先定義的全局常量堆的順序存儲(chǔ)類型如何“建堆”？兩個(gè)問題:如何“篩選”？完全二叉樹

調(diào)整為堆哈夫曼樹

最優(yōu)樹的定義如何構(gòu)造最優(yōu)樹

抽象數(shù)據(jù)類型圖的定義圖的存儲(chǔ)結(jié)構(gòu)圖的遍歷dfsbfs最小生成樹普里姆克魯斯卡爾拓?fù)渑判虻谄哒聢D的存儲(chǔ)表示鄰接矩陣存儲(chǔ)表示圖的鄰接表存儲(chǔ)表示有向圖的十字鏈表存儲(chǔ)表示邊集數(shù)組存儲(chǔ)表示Aij={0(i,j)VR1(i,j)VR圖的鄰接矩陣存儲(chǔ)表示矩陣的元素為有向圖的鄰接矩陣為非對(duì)稱矩陣有向網(wǎng)的鄰接矩陣為非對(duì)稱矩陣Aij={∞(i,j)VRw(i,j)VR網(wǎng)的鄰接矩陣存儲(chǔ)表示矩陣的元素為指向下一個(gè)有相同弧尾的結(jié)點(diǎn)指向下一個(gè)有相同弧頭的結(jié)點(diǎn)有向圖的十字鏈表存儲(chǔ)表示

弧的結(jié)點(diǎn)結(jié)構(gòu)弧尾位置弧頭位置相關(guān)信息指向該頂點(diǎn)的第一條入弧指向該頂點(diǎn)的第一條出弧頂點(diǎn)的結(jié)點(diǎn)結(jié)構(gòu)頂點(diǎn)信息數(shù)據(jù)圖的遍歷

從圖中某個(gè)頂點(diǎn)出發(fā)游歷圖，訪遍圖中其余頂點(diǎn)，并且使圖中的每個(gè)頂點(diǎn)僅被訪問一次的過程。深度優(yōu)先搜索dfs廣度優(yōu)先搜索bfs(連通網(wǎng)的)最小生成樹

構(gòu)造網(wǎng)的一棵最小生成樹，即:在

e條帶權(quán)的邊中選取n-1條邊（不構(gòu)回路），使“權(quán)值之和”為最小。算法二：（克魯斯卡爾算法）算法一：（普里姆算法）abcdegf195141827168213ae12dcbgf71485316217121819克魯斯卡爾算法：abcdegf195141827168213ae12dcbgf7148531621所得生成樹權(quán)值和=14+8+3+5+16+21=67普里姆算法G=(V,E)T=(U,TE)

拓?fù)渑判?/p>

問題:假設(shè)以有向圖表示一個(gè)工程的施工圖或程序的數(shù)據(jù)流圖，則圖中不允許出現(xiàn)回路。

檢查有向圖中是否存在回路的方法之一，是對(duì)有向圖進(jìn)行拓?fù)渑判?。?duì)有向圖進(jìn)行如下操作：

按照有向圖給出的次序關(guān)系，將圖中頂點(diǎn)排成一個(gè)線性序列，對(duì)于有向圖中沒有限定次序關(guān)系的頂點(diǎn)，則可以人為加上任意的次序關(guān)系。第八章查找

對(duì)查找的操作：1）查詢(檢索)某個(gè)“特定的”數(shù)據(jù)元素是否在查找表中及各種屬性；2）在查找表中插入一個(gè)數(shù)據(jù)元素；3）從查找表中刪去某個(gè)數(shù)據(jù)元素。僅作查詢和檢索操作的查找表。靜態(tài)查找表有時(shí)還需要將“查詢”結(jié)果為“不在查找表中”的數(shù)據(jù)元素插入到表中；或者，從查找表中刪除其“查詢”結(jié)果為“在查找表中”的數(shù)據(jù)元素。動(dòng)態(tài)查找表查找表可分為兩類:1.順序查找2.二分查找3.索引順序靜態(tài)查找表

以順序表或線性鏈表表示靜態(tài)查找表順序查找表

順序查找表的查找算法簡單，但平均查找長度較大，特別不適用于表長較大的查找表。有序查找表

若以有序表表示靜態(tài)查找表，則查找過程可以基于“折半”進(jìn)行。索引順序表的查找過程：1）由索引確定記錄所在區(qū)間；2）在順序表的某個(gè)區(qū)間內(nèi)進(jìn)行查找。索引可以根據(jù)查找表的特點(diǎn)來構(gòu)造。

索引順序查找的過程也是一個(gè)“縮小區(qū)間”的查找過程。B-樹查找1．定義2．查找過程3．插入操作4．查找性能的分析動(dòng)態(tài)查找表

在

m

階的B-樹上，每個(gè)非終端結(jié)點(diǎn)可能含有：

n

個(gè)關(guān)鍵字

Ki（1≤i≤n）n<m

或n

個(gè)指向記錄的指針

Di（1≤i≤n）

n+1

個(gè)指向子樹的指針

Ai（0≤i≤n）多叉樹的特性

非葉結(jié)點(diǎn)中的多個(gè)關(guān)鍵字均自小至大有序排列，即：K1<K2<…<Kn；

Ai-1所指子樹上所有關(guān)鍵字均小于Ki；

Ai所指子樹上所有關(guān)鍵字均大于Ki；查找樹的特性平衡樹的特性樹中所有葉子結(jié)點(diǎn)均不帶信息，且在樹中的同一層次上；根結(jié)點(diǎn)或?yàn)槿~子結(jié)點(diǎn)，或至少含有兩棵子樹；其余所有非葉結(jié)點(diǎn)均至少含有

m/2

棵子樹，至多含有m

棵子樹；B-樹的定義B-樹是一種

平衡

的多路

查找

樹：root50157184382026435662788996散列查找

哈希表動(dòng)態(tài)查找表

對(duì)數(shù)字的關(guān)鍵字可有下列構(gòu)造方法：

若是非數(shù)字關(guān)鍵字，則需先對(duì)其進(jìn)行數(shù)字化處理。1.直接定址法3.數(shù)字分析法5.折疊法4.平方取中法2.除留余數(shù)法處理沖突的方法

“處理沖突”的實(shí)際含義是：為產(chǎn)生沖突的地址尋找下一個(gè)哈希地址。1.開放定址法2.鏈接法基本概念選擇排序:氣泡排序快速排序直接選擇排序堆排序各種排序方法的綜合比較交換排序:歸并排序第九章排序基本概念一、排序的定義二、內(nèi)部排序三、內(nèi)部排序方法的分類內(nèi)部排序的方法

內(nèi)部排序的過程是一個(gè)逐步擴(kuò)大記錄的有序序列長度的