樹和二叉樹樹的概念

存儲結構和運算樹和二叉樹的性質二叉樹的概念第五章二叉樹的五種基本形態：空樹N只含根結點NL右子樹為空NR左子樹為空NRL左右子樹均不為空樹E

ADBCF

rootleftdataright結點結構:二叉鏈表先（根）序的遍歷算法

DLR中（根）序的遍歷算法

LDR后（根）序的遍歷算法

LRD先右后左的遍歷算法

RLDRDLDRLABCGFHEID

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

前序遍歷遞歸算法

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

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

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

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

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

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

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

ABCDEFGHIJKqGTAGHFEDCBABCDEFGHIJK按層遍歷樹

二叉樹的應用二叉搜索樹堆

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

BTreeNode*left;

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

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

其雙親結點的相應指針域改為“指向被刪除結點的左子樹或右子樹”。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）被刪除的結點有左右子樹被刪結點前驅結點以其前驅替代之，然后再刪除該前驅結點左子樹中“最右下”的結點（左指針可能不為空）

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

是ri

的左孩子r2i+1

是ri

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

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

調整為堆哈夫曼樹

最優樹的定義如何構造最優樹

抽象數據類型圖的定義圖的存儲結構圖的遍歷dfsbfs最小生成樹普里姆克魯斯卡爾拓撲排序第七章圖的存儲表示鄰接矩陣存儲表示圖的鄰接表存儲表示有向圖的十字鏈表存儲表示邊集數組存儲表示Aij={0(i,j)VR1(i,j)VR圖的鄰接矩陣存儲表示矩陣的元素為有向圖的鄰接矩陣為非對稱矩陣有向網的鄰接矩陣為非對稱矩陣Aij={∞(i,j)VRw(i,j)VR網的鄰接矩陣存儲表示矩陣的元素為指向下一個有相同弧尾的結點指向下一個有相同弧頭的結點有向圖的十字鏈表存儲表示

弧的結點結構弧尾位置弧頭位置相關信息指向該頂點的第一條入弧指向該頂點的第一條出弧頂點的結點結構頂點信息數據圖的遍歷

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

構造網的一棵最小生成樹，即:在

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

拓撲排序

問題:假設以有向圖表示一個工程的施工圖或程序的數據流圖，則圖中不允許出現回路。

檢查有向圖中是否存在回路的方法之一，是對有向圖進行拓撲排序。對有向圖進行如下操作：

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

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

以順序表或線性鏈表表示靜態查找表順序查找表

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

若以有序表表示靜態查找表，則查找過程可以基于“折半”進行。索引順序表的查找過程：1）由索引確定記錄所在區間；2）在順序表的某個區間內進行查找。索引可以根據查找表的特點來構造。

索引順序查找的過程也是一個“縮小區間”的查找過程。B-樹查找1．定義2．查找過程3．插入操作4．查找性能的分析動態查找表

在

m

階的B-樹上，每個非終端結點可能含有：

n

個關鍵字

Ki（1≤i≤n）n<m

或n

個指向記錄的指針

Di（1≤i≤n）

n+1

個指向子樹的指針

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

非葉結點中的多個關鍵字均自小至大有序排列，即：K1<K2<…<Kn；

Ai-1所指子樹上所有關鍵字均小于Ki；

Ai所指子樹上所有關鍵字均大于Ki；查找樹的特性平衡樹的特性樹中所有葉子結點均不帶信息，且在樹中的同一層次上；根結點或為葉子結點，或至少含有兩棵子樹；其余所有非葉結點均至少含有

m/2

棵子樹，至多含有m

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

平衡

的多路

查找

樹：root50157184382026435662788996散列查找

哈希表動態查找表

對數字的關鍵字可有下列構造方法：

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

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

內部排序的過程是一個逐步擴大記錄的有序序列長度的