前序、后续将二叉树线索化

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");
    }
}