前序、後續將二元樹線索化
a. 問題分析
我們需要實現一個二元樹的前序線索化。線索化是一種將二元鏈表中的空指針域改為指向該節點在某種遍歷次序下的前驅節點或後繼節點的方法。這樣，我們就可以通過前序、中序或後序中的任何一個節點來開始，而不僅僅是從根節點開始。
b. 演算法設計
我們的演算法首先會建立一個二元樹，然後對其進行線索化。線索化的過程是透過一個遞迴函式實現的，該函式會遍歷每一個節點，並檢查其左右子節點是否存在。如果不存在，則將其左/右指標指向前一個/後一個節點。最後，我們會進行一個中序遍歷來檢查線索化是否成功。
以下是線索化的程式碼片段：
// 建立線索的函式
void createThread(Node* p) {
if (p == NULL) { // 如果節點為空，直接返回
return;
}
createThread(p->left); // 遞迴處理左子樹
if (!p->left) { // 如果左子節點為空，將左指標指向前一個節點，並將左線索標記設為1
p->left = pre;
p->ltag = 1;
}
if (pre && !pre->right) { // 如果前一個節點的右子節點為空，將其右指標指向當前節點，並將右線索標記設為1
pre->right = p;
pre->rtag = 1;
}
pre = p; // 更新前一個節點
createThread(p->right); // 遞迴處理右子樹
}
c. 資料結構設計
我們使用一個結構體來表示二元樹的節點，該結構體包含一個資料欄位和兩個指標欄位，分別指向左子節點和右子節點。此外，我們還添加了兩個標記欄位，用於標記左右指標是否被線索化。
以下是資料結構的程式碼片段：
// 定義二元樹節點的結構體
struct Node {
int data; // 節點的資料
Node* left; // 左子節點
Node* right; // 右子節點
int ltag, rtag; // 左右線索標記
};
d. 調試過程
我們首先創建一個二元樹，並對其進行線索化。然後，我們進行一次中序遍歷來檢查線索化是否成功。如果遍歷的結果與預期的結果一致，那麼我們就可以認為線索化是成功的。
以下是調試過程的代碼片段：
int main() {
// 創建二元樹
Node n1, n2, n3, n4, n5;
n1 = {1, &n2, &n3, 0, 0};
n2 = {2, &n4, &n5, 0, 0};
n3 = {3, NULL, NULL, 0, 0};
n4 = {4, NULL, NULL, 0, 0};
n5 = {5, NULL, NULL, 0, 0};
// 對二元樹進行線索化
createThread(&n1);
// 中序遍歷線索二元樹
inOrder(&n1);
return 0;
}
e. 輸出結果
程式的輸出結果應該是二元樹的中序遍歷結果。在我們的例子中，輸出結果應該是 4 2 5 1 3。我們創建的二元樹的中序遍歷結果就是這個序列。
f. 原始碼
#include<iostream>
using namespace std;
// 定義二元樹節點的結構體
struct Node {
int data; // 節點的數據
Node* left; // 左子節點
Node* right; // 右子節點
int ltag, rtag; // 左右線索標記
};
// 定義全域變數pre，用於儲存前一個節點
Node* pre = NULL;
// 建立線索的函數
void createThread(Node* p) {
if (p == NULL) { // 如果節點為空，直接返回
return;
}
createThread(p->left); // 遞迴處理左子樹
if (!p->left) { // 如果左子節點為空，將左指標指向前一個節點，並將左線索標記設為1
p->left = pre;
p->ltag = 1;
}
if (pre && !pre->right) { // 如果前一個節點的右子節點為空，將其右指標指向當前節點，並將右線索標記設為1
pre->right = p;
pre->rtag = 1;
}
pre = p; // 更新前一個節點
createThread(p->right); // 遞迴處理右子樹
}
// 中序走訪線索二元樹的函數
void inOrder(Node* p) {
while (p) {
while (!p->ltag) { // 找到最左邊的節點
p = p->left;
}
cout << p->data << " "; // 輸出節點數據
while (p->rtag) { // 如果右指標是線索，直接跳到後繼節點
p = p->right;
cout << p->data << " ";
}
p = p->right; // 處理右子樹
}
}
int main() {
// 建立二元樹
Node n1, n2, n3, n4, n5;
n1 = {1, &n2, &n3, 0, 0};
n2 = {2, &n4, &n5, 0, 0};
n3 = {3, NULL, NULL, 0, 0};
n4 = {4, NULL, NULL, 0, 0};
n5 = {5, NULL, NULL, 0, 0};
// 對二元樹進行線索化
createThread(&n1);
// 中序走訪線索二元樹
inOrder(&n1);
return 0;
}
圖的鄰接矩陣和鄰接表的儲存
a. 問題分析
我們的目標是在C++中實現圖的鄰接矩陣和鄰接表的存儲。這涉及到兩種不同的資料結構：陣列（用於鄰接矩陣）和鏈表（用於鄰接表）。
b. 演算法設計
鄰接矩陣
我們使用一個二維陣列adj[MAX][MAX]來儲存圖的鄰接矩陣。每個元素adj[i][j]表示從節點i到節點j是否存在一條邊。如果存在，則adj[i][j] = 1，否則adj[i][j] = 0。
for (i = 1; i <= max_edges; i++) {
cin >> origin >> destin;
if ((origin == -1) && (destin == -1))
break;
if (origin >= n || destin >= n || origin < 0 || destin < 0) {
i--;
} else {
adj[origin][destin] = 1;
}
}
鄰接表
我們使用一個鏈結串列陣列list<int> *adj來儲存圖的鄰接表。每個元素adj[i]是一個鏈結串列，儲存了所有與節點i相鄰的節點。
void Graph::addEdge(int v, int w) {
adj[v].push_back(w);
}
c. 資料結構設計
鄰接矩陣
我們使用一個二維陣列int adj[MAX][MAX]來儲存鄰接矩陣。MAX是圖中節點的最大數量。
鄰接表
我們使用一個鏈結串列陣列list<int> *adj來儲存鄰接表。V是圖中節點的數量。
d. 除錯過程
在實作和除錯程式碼的過程中，我們首先確保了輸入的邊是有效的。如果輸入的邊無效（例如，如果它引用了一個不存在的節點），我們會提示使用者並讓他們重新輸入。
在新增邊到鄰接矩陣或鄰接表時，我們使用了錯誤檢查來確保我們不會嘗試存取陣列或鏈結串列的越界索引。
e. 輸出結果
最後，我們可以印出鄰接矩陣或鄰接表，以驗證我們的程式碼是否正確。對於鄰接表，我們遍歷每個節點的鏈結串列，並印出所有相鄰的節點。
void Graph::printGraph() {
for (int v = 0; v < V; v++) {
cout << "\n Adjacency list of vertex " << v << "\n head ";
for (auto x : adj[v])
cout << "-> " << x;
printf("\n");
}
}
f. 原始碼
鄰接矩陣儲存
#include<iostream>
#define MAX 20
using namespace std;
int adj[MAX][MAX];
int n;
void create_graph() {
int i, max_edges, origin, destin;
cout << "Enter number of nodes : ";
cin >> n;
max_edges = n * (n - 1);
for (i = 1; i <= max_edges; i++) {
cout << "Enter edge " << i << " (-1 -1 to quit) : ";
cin >> origin >> destin;
if ((origin == -1) && (destin == -1))
break;
if (origin >= n || destin >= n || origin < 0 || destin < 0) {
cout << "Invalid edge!\n";
i--;
} else {
adj[origin][destin] = 1;
}
}
}
鄰接表儲存
#include<iostream>
#include<list>
using namespace std;
class Graph {
int V;
list<int> *adj;
public:
Graph(int V);
void addEdge(int v, int w);
void printGraph();
};
Graph::Graph(int V) {
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w) {
adj[v].push_back(w);
}
void Graph::printGraph() {
for (int v = 0; v < V; v++) {
cout << "\n Adjacency list of vertex " << v << "\n head ";
for (auto x : adj[v])
cout << "-> " << x;
printf("\n");
}
}
何時一樽酒，重與細論文。