第五章:樹和二叉樹

先序遍歷二叉樹的非遞歸算法。

void PreOrderTraverse(BiTree T, void (*Visit)(TElemType)) {//表示用于查找的函數(shù)的指針Stack S; BiTree p = T;InitStack(S);//S模擬工作棧while (p || !StackEmpty(S)) {//S為空且下一個結(jié)點為空，意味著結(jié)束遍歷if (p) {//p有值，則Push進棧為一個工作進程Visit(p->data); Push(S, p); p = p->lchild;//先序遍歷，先Visit} else {
//p為空，則它的上級被Pop出去，成為新的p，再取右孩子。在下一個循環(huán)中如果它的上級沒右孩子，則說明它的上級是葉子結(jié)點（或兩端已經(jīng)工作棧彈出了），則再Pop出它的上級的上級（此時它的上級已經(jīng)無用，工作棧彈出），取它上級的兄弟結(jié)點Pop(S, p); p = p->rchild;}}
}

利用工作棧的思想，過程十分復(fù)雜，多多復(fù)習(xí)，鞏固加深！

層序遍歷二叉樹

void LayerTraverse(BiTree T, void (*Visit)(TElemType)) {Queue Q; BiTree p;InitQueue(Q);EnQueue(Q, T);while (!QueueEmpty(Q)) {DeQueue(Q, p);
//每有一個父母結(jié)點出隊列，就把它的左右孩子放到隊尾排隊，確保一層一層遍歷if (p) {Visit(p->data);EnQueue(Q, p->lchild); EnQueue(Q, p->rchild);}}
}

計算二叉樹中每個結(jié)點的層次

void LevelRecur(BiTree T, int lev) {if (T) {++lev;//準(zhǔn)備遍歷下一層cout << T->data << ' ' << lev << endl;LevelRecur(T->lchild, lev);LevelRecur(T->rchild, lev);//下一層啟動}
}
void Level(BiTree T) {LevelRecur(T, 0);
}

輸出二叉樹根結(jié)點到所有葉子結(jié)點的路徑?

void OutPath(BiTree T, Stack &S) {//使用一個棧存儲路徑，起到回溯的作用if (T) {Push(S, T);if (!T->lchild && !T->rchild)PrintStack(S);//S棧中元素依次輸出，不取出OutPath(T->lchild, S);OutPath(T->rchild, S);Pop(S, T);//該節(jié)點左右孩子搜索完，則出棧，不再計入路徑中}
}

由擴展的先序序列，即波蘭式，建立二叉樹?

void CreateBiTree(BiTree &T) {// 讀入擴展的先序序列，假定數(shù)據(jù)元素為字符型，#表示NULLchar ch; scanf("%c", &ch);if (ch == '#') T = NULL;else {T = new BiTNode; T->data = ch;CreateBiTree(T->lchild);//依次建立二叉樹CreateBiTree(T->rchild);}
}

先根遍歷樹，孩子鏈表實現(xiàn)

void PreOrderRecur(CTree T, int loc, void (*Visit)(TElemType)) {if (loc == -1) return;Visit(T.nodes[loc].data);//先查詢根結(jié)點ChildPtr p;for (p = T.nodes[loc].firstchild; p; p = p->next) {PreOrderRecur(T, p->child, Visit);//取出下個孩子，并查詢}
}
void PreOrderTree(CTree T, void (*Visit)(TElemType)) {PreOrderRecur(T, T.root, Visit);
}

計算樹的深度，孩子兄弟鏈表實現(xiàn)

int TreeDepth(CSTree T) {if (!T) return 0;//最簡單情況，遍歷結(jié)束條件CSTree p; int maxh = 0;//maxh為全局變量for (p = T->firstchild; p; p = p->nextsibling) {//到T的下一個孩子，并且遍歷其孩子的兄弟int h = TreeDepth(p);//當(dāng)前遍歷結(jié)點的深度if (h > maxh) maxh = h;}return maxh + 1;
}

構(gòu)造huffman樹

typedef unsigned int WeightType;
typedef struct {TElemType data;WeightType weight; // 葉子權(quán)值的類型int parent, lchild, rchild; // 三叉靜態(tài)鏈表
} HTNode, *HuffmanTree;
void CreateHuffmanTree(HuffmanTree &HT, int n) {int m = 2*n-1; // 最終將得到2n-1個結(jié)點HT = new HTNode[m];for (i=0; i<n; ++i) {cin >> HT[i].data >> HT[i].weight;HT[i].lchild = HT[i].rchild = HT[i].parent = -1;//-1即示意為為null}//輸入結(jié)點值for (i=n; i<m; ++i) {Select(HT, i-1, s1, s2); HT[s1].parent=HT[s2].parent=i;HT[i].weight = HT[s1].weight + HT[s2].weight;//兩個結(jié)點的父母的權(quán)值為它們加和HT[i].lchild=s1; HT[i].rchild=s2; HT[i].parent = -1;}
}const unsigned int MAX_WEIGHT = UINT_MAX;
void Select(HuffmanTree HT, int s, int &l, int &r) {// 本函數(shù)的作用是從HT[0..s]中找到權(quán)值最小的兩個結(jié)點WeightType WL = MAX_WEIGHT, WR = MAX_WEIGHT;for (i=0; i<=s; ++i) {if (HT[i].parent == -1) {if (HT[i].weight < WL) {WR = WL; WL = HT[i].weight; r=l; l=i;} else if (HT[i].weight < WR) {WR = HT[i].weight; r=i;}}}
}

第六章：圖

深度優(yōu)先遍歷DFS

bool visited[MAX_VERTEX_NUM];
void DFS(Graph G, int v) {//類似于先根遍歷Visit(v); visited[v] = true;for (int w=AdjVex(G, v); w != -1; w=AdjVex(G, v, w)) {if (!visited[w])DFS(G, w);}
}
void DFSTraverse(Graph G) {for (int v=0; v<G.vexnum; ++v)visited[v] = false;//初始化visited表for (int v=0; v<G.vexnum; ++v)if (!visited[v])DFS(G, v);//如果沒有查找到?jīng)]遍歷過的，則彈出工作棧，返回上一級
}
int AdjVex(MGraph G, int v, int w=-1) {//鄰接矩陣for (int j=w+1; j<G.vexnum; ++j)if (G.arcs[v][j] != INFINITY) return j;//找找它可能的出路return -1;
}int AdjVex(ALGraph G, int v, int w=-1) {//鄰接表ArcNode *p = G.vertices[v].firstarc;if (w != -1) {while (p && p->adjvex != w) p = p->nextarc;if (p) p = p->nextarc;}return p ? p->adjvex : -1;
}

廣度優(yōu)先搜索BFS

bool visited[MAX_VERTEX_NUM];
void BFS(Graph G, int v) {//類似于層序遍歷Visit(v); visited[v] = true;Queue Q; InitQueue(Q); EnQueue(Q, v);while (!QueueEmpty(Q)) {DeQueue(Q, v);for (int w=AdjVex(G, v); w != -1; w=AdjVex(G, v, w)) {if (!visited[w]) {Visit(w); visited[w] = true; EnQueue(Q, w);}}}
}
void BFSTraverse(Graph G) {for (int v=0; v<G.vexnum; ++v)visited[v] = false;//初始化for (int v=0; v<G.vexnum; ++v)if (!visited[v])BFS(G, v);
}

利用DFS求簡單路徑

bool visited[MAX_VERTEX_NUM];
bool DFS_SimplePathRecur(Graph G, int vi, int vj, Stack &S) {Push(S, vi); visited[vi] = true;//S存儲過往路徑if (vi == vj) {Print(S); return true;}for (int w=AdjVex(G, vi); w != -1; w=AdjVex(G, vi, w)) {if (!visited[w]) {if (DFS_SimplePathRecur(G, w, vj, S))return true;}}Pop(S, vi); visited[vi] = false; return false;
}
void DFS_SimplePath(Graph G, int vi, int vj) {Stack S; InitStack(S);for (int v=0; v<G.vexnum; ++v)visited[v] = false;if (DFS_SimplePathRecur(G, vi, vj, S))cout << "Found a path" << endl;
}

使用Prim算法，得出最小生成樹

void Prim(MGraph G, int v0) {// 用于存儲F集合的兩個數(shù)組：鄰接頂點和最小邊int adjvex[MAX_VERTEX_NUM], lowcost[MAX_VERTEX_NUM];for (int j=0; j<G.vexnum; ++j) {if (j!=v0) {adjvex[j] = v0;lowcost[j] = G.arcs[v0][j];}}lowcost[v0] = INFINITY;for (int i=0; i<G.vexnum-1; ++i) { // 循環(huán)n-1次int k = MinEdge(lowcost, G.vexnum);//該頂點的連接的最小邊printf("(%d, %d): %d\n", k, adjvex[k], lowcost[k]);lowcost[k] = INFINITY;for (int j=0; j<G.vexnum; ++j) {if (G.arcs[k][j] < lowcost[j]) {adjvex[j] = k;lowcost[j] = G.arcs[k][j];}}}
}

得出拓?fù)渑判?/p>

void TopologicalSort(ALGraph G) {//思路找頭結(jié)點，并刪除它和它連接的路徑，繼續(xù)下一個int InDegree[MAX_VERTEX_NUM];FindInDegree(G, InDegree);Stack S; InitStack(S);for (int i=0; i<G.vexnum; ++i)if (!InDegree[i]) Push(S, i);int count = 0; // 統(tǒng)計輸出頂點的個數(shù)while (!StackEmpty(S)) {int i; Pop(S, i); ++count;cout << G.vertices[i].data << endl; ArcNode *p;for (p=G.vertices[i].firstarc; p; p=p->nextarc) {k = p->adjvex;if (!(--InDegree[k])) Push(S, k);}}if (count<G.vexnum)cout << "The graph has loop" << endl;
}void FindInDegree(ALGraph G, int *InDegree) {for (int i=0; i<G.vexnum; ++i) InDegree[i] = 0;for (int i=0; i<G.vexnum; ++i) {for (ArcNode *p=G.vertices[i].firstarc; p; p=p->nextarc) {InDegree[p->adjvex]++;}}
}

第七章：查找表

二分查找（折半查找）靜態(tài)表

int Search_Bin(StaticSearchTable ST, KeyType key) {//其中ST為從小到大的順序表int low=1, high=ST.length;while (low <= high) {mid = (low + high) / 2;if (key == ST.data[mid].key) return mid;else if (key < ST.data[mid].key) high = mid - 1;//取前一半else low = mid + 1;//取后一半}return 0;
}

二叉查找樹的查找方法（遞歸算法）

BiTree Search_BST(BiTree T, KeyType key) {//題外話：對二叉查找樹進行中序遍歷可得到有序數(shù)列if (!T || key == T->data.key)return T;else if (key < T->data.key)//此時的左右孩子被賦予了更多意義return Search_BST(T->lchild, key);elsereturn Search_BST(T->rchild, key);
}

二叉查找樹的查找方法（非遞歸算法）

bool SearchBST(BiTree T, KeyType key, BiTree &p, BiTree &f) {// 若查找到key，則返回true，此時p指向等于key的// 結(jié)點，f是p的雙親（若p等于根結(jié)點，則f為NULL）// 若查找不到key，則返回false，此時p為NULL，f// 指向查找過程中最后一個比較的結(jié)點f = NULL; p = T;while (p && key != p->data.key) {f = p;//保存f，則允許了回溯到父母結(jié)點的操作if (key < p->data.key) p = p->lchild;//向左走呢，還是向右走呢？else p = p->rchild;}if (!p) return false;else return true;
}

二叉查找樹的插入

bool InsertBST(BiTree &T, KeyType key) {BiTree p, f;bool found = SearchBST(T, key, p, f);if (found) return false;//查找成功，則不插入；
//反之，在查找失敗的查找路徑上最后一個結(jié)點的左或右插入BiTree t = new BiTNode;t->data.key = key; t->lchild = t->rchild = NULL;if (!f) T = t;//如果二叉樹為空，則插入第一條數(shù)據(jù)else if (key < f->data.key) f->lchild = t;else f->rchild = t;return true;
}

二叉查找樹的刪除

bool DeleteBST(BiTree &T, KeyType key) {BiTree p, f;bool found = SearchBST(T, key, p, f);if (!found) return false;if (p->lchild && p->rchild) {//有左右孩子的條件BiTree q = p, t = p->rchild;//將結(jié)點替代為右子樹上最小的結(jié)點（也可為左子樹上最大的結(jié)點）while (t->lchild) { q = t; t = t->lchild; }//一直向左子樹查找，找到“最左”的t，即最小p->data = t->data;//替代if (q != p) q->lchild = t->rchild;//q為t的雙親，由于t無左子樹，則只需要將t的右子樹接到q上即可完成交接t的轉(zhuǎn)移。else q->rchild = t->rchild; delete t;//如果p是t的雙親，則直接插上} else {BiTree q = p->lchild ? p->lchild : p->rchild;if (!f) T = q;else if (p == f->lchild) f->lchild = q;else f->rchild = q; delete p;}return true;
}

寫出判別一顆二叉樹是否為二叉排序樹的算法，設(shè)二叉排序樹中不存在關(guān)鍵字值相同的結(jié)點。

elemType arr[MAXN]; // 存放中序遍歷結(jié)果
int k=0; // 記錄訪問過的結(jié)點數(shù)
void Inorder_Traversal (TreeNode? T){if (!T) return;Inorder_Traversal (T?>left);arr [k] = T?>val; // 記錄結(jié)點值k++;Inorder_Traversal (T?>right, arr);
}bool Is_Binary_Sort_Tree(TreeNode? T){Inorder_Traversal (T); // 先中序遍歷for (int i=1; i<k; i++)if (arr [ i ] <= arr[i?1]) // 判斷是否遞增return false ;return true;
}

第八章：排序

簡單排序

void SelectSort(SqTable &L) {for (int i=1; i<L.len; ++i) {int j=i;for (int k=L.len; k>i; --k)if (L.r[k].key < L.r[j].key) j=k;if (i!=j) {// 這里我們將L.r[i]和L.r[j]交換// 另一種做法是將L.r[i..j-1]各個后移一位，然后令L.r[i]=L.r[j]RcdType tmp = L.r[i]; L.r[i] = L.r[j]; L.r[j] = tmp;}}
}

冒泡排序

void BubbleSort(SqTable &L) {bool change = true;for (int i=n; i>=2 && change; --i) {// 這里我們設(shè)置一個標(biāo)記，如果j從1到i-1循環(huán)中沒有發(fā)生元素的互換// 說明整個序列已經(jīng)是有序的了，無需考慮更小的ichange = false;for (int j=1; j<=i-1; ++j) {if (L.r[j].key > L.r[j+1].key) {RcdType tmp = L.r[j]; L.r[j] = L.r[j+1]; L.r[j+1] = tmp;change = true;}}}
}

插入排序

void InsertSortSub(SqTable &L, int low, int high) {// 這個子函數(shù)對L.r[low..high]做簡單插入排序for (int i=low+1; i<=high; ++i)if (L.r[i].key < L.r[i-1].key) {RcdType tmp = L.r[i];for (int j=i-1; tmp.key < L.r[j].key && j>=low; --j)L.r[j+1] = L.r[j]; // 元素后移L.r[j+1] = tmp;      // 插入到合適位置}
}
void InsertSort(SqTable &L) {InsertSortSub(L, 1, L.len);
}

希爾排序

void ShellSortSub(SqTable &L, int dk) {// 一趟增量為dk的插入排序for (int i=dk+1; i<=L.len; ++i) {if (L.r[i].key < L.r[i-dk].key) {RcdType tmp = L.r[i];for (int j=i-dk; tmp.key < L.r[j].key && j>=1; j-=dk)L.r[j+dk] = L.r[j];L.r[j+dk] = tmp;}}
}
void ShellSort(SqTable &L, int delta[], int k) {// delta是每趟排序的增量值for (int i=0; i<k; ++i)ShellSortSub(L, delta[i]);
}

快速排序

void QSort(SqTable &L, int low, int high) {// 對L[low..high]進行快速排序if (low < high) {int pivotloc = Partition(L, low, high);QSort(L, low, pivotloc-1);QSort(L, pivotloc+1, high);}
}
void QuickSort(SqTable &L) {QSort(L, 1, L.len);
}
int Partition(SqTable &L, int low, int high) {// 選擇一個樞軸，將L.r[low..high]分為兩部分// 返回樞軸最后所在的位置，以便進一步劃分// 劃分以后，在樞軸之前（之后）的元素都小于（大于）或等于樞軸int pivotloc = low; // 樞軸可以任意選取，例如取第一個位置RcdType tmp = L.r[pivotloc];KeyType pivotkey = tmp.key;while (low<high) {while (low<high && L.r[high].key>=pivotkey) --high;L.r[low] = L.r[high];while (low<high && L.r[low].key<=pivotkey) ++low;L.r[high] = L.r[low];}L.r[low] = tmp;return low;
}

堆排序

void HeapAdjust(SqTable &L, int s, int m) {// 已知L.r[s..m]中除了L.r[s]以外，都滿足大頂堆的定義// 本函數(shù)通過調(diào)整，使得L.r[s..m]成為一個大頂堆RcdType tmp = L.r[s];for (int i=2*s; i<=m; i*=2) { // 每次向下一層if (i<m && L.r[i].key<L.r[i+1].key) ++i;if (tmp.key >= L.r[i].key) break; // 已經(jīng)找到合適的位置L.r[s] = L.r[i]; s = i; // 與孩子換位}L.r[s] = tmp;
}
void HeapSort(SqTable &L) {int i; RcdType tmp;for (i=L.len/2; i>0; --i)HeapAdjust(L, i, L.len); // 構(gòu)造初始大頂堆for (i=L.length; i>1; --i) {tmp = L.r[i];L.r[i] = L.r[1];L.r[1] = tmp; // 將最大的關(guān)鍵字放到L.r[i]HeapAdjust(L, 1, i-1); // 對L.r[1..i-1]調(diào)用篩選法重新調(diào)整為堆}
}

歸并排序

void Merge(RcdType* Rs, RcdType* Rt, int s, int m, int t) {// 已知Rs[s..m]和Rs[m+1..t]都是有序表，將它們歸并存儲到Rt[s..t]int i,j,k;for (i=s, j=m+1, k=s; i<=m && j<=t; ++k) {//兩表的排序在此處if (Rs[i].key <= Rs[j].key) Rt[k] = Rs[i++];else Rt[k] = Rs[j++];}for (; i<=m; ++i, ++k) Rt[k] = Rs[i];//當(dāng)一個有序表取完時，剩下直接安進去for (; j<=t; ++j, ++k) Rt[k] = Rs[j];
}
void MSort(RcdType* Rs, RcdType* Rt, int low, int high) {//遞歸算法if (low < high) {//low=high時，無需歸并int mid = (low+high)/2;MSort(Rs, Rt, low, mid); MSort(Rs, Rt, mid+1, high);Merge(Rs, Rt, low, mid, high);for (int i=low; i<=high; ++i) Rs[i] = Rt[i];//將Rt復(fù)制到Rs上}
}
void MergeSort(SqTable &L) {RcdType* tmp = new RcdType[L.len+1];MSort(L.r, tmp, 1, L.len);delete []tmp;
}

基數(shù)排序

const int RADIX = 128; // 每個“基本關(guān)鍵字”的取值范圍，稱為基數(shù)
const int KEY_LENGTH = 5; // 共有5個“基本關(guān)鍵字”
typedef char KeyType[KEY_LENGTH]; // 關(guān)鍵字類型為長度為5的字符串
void RadixPass(RcdType *R, RcdType *T, int n, int k) {int j; int count[RADIX];for (j=0; j<RADIX; ++j) count[j] = 0;for (j=1; j<=n; ++j) count[R[j].key[k]]++;for (j=1; j<RADIX; ++j) count[j] = count[j-1] + count[j];for (j=n; j>0; --j) {int p = R[j].key[k]; T[count[p]] = R[j]; count[p]--;}for (j=1; j<=n; ++j) R[j] = T[j];
}
void RadixSort(SqTable &L) {RcdType *tmp = new RcdType[L.len+1];for (int k = KEY_LENGTH-1; k>=0; --k)RadixPass(L.r, tmp, L.len, k);delete []tmp;
}

ps：對于C++語言，有以下便捷操作

提供sort函數(shù)，一般用快速排序?qū)崿F(xiàn)，不穩(wěn)定

提供stable_sort函數(shù)，一般用歸并排序?qū)崿F(xiàn)，穩(wěn)定

提供priority_queue數(shù)據(jù)結(jié)構(gòu)，即堆?

---

萬字文章，整理不易，寫了整整一天半，點個贊權(quán)當(dāng)支持一下

這是上一卷內(nèi)容：

數(shù)據(jù)結(jié)構(gòu)經(jīng)典算法總復(fù)習(xí)（上卷）-CSDN博客

加油諸位！