データ構造実機実験レポート6——前順序・後順序による二分木のスレッド化、グラフの隣接行列と隣接リストの格納

// スレッドを作成する関数
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); // 右部分木を再帰的に処理
}

// 二分木ノードの構造体を定義
struct Node {
    int data; // ノードのデータ
    Node* left; // 左子ノード
    Node* right; // 右子ノード
    int ltag, rtag; // 左右スレッドマーク
};

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

#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;
}

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

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

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