データ構造実機実験レポート4——二分木の構築（完全二分木BFS結果）、保存（順序保存とリンク保存）、走査（BFSとDFS）

#include<bits/stdc++.h>
using namespace std;
#define MAX_NODES 1000  // 最大ノード数
// 二分木ノード構造を定義
struct TreeNode {
    char data;
};
// 新しい二分木ノードを作成
TreeNode* createNode(char data) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    newNode->data = data;
    return newNode;
}
// 順次記憶の文字二分木構造
struct SequentialTree {
    TreeNode* nodes[MAX_NODES];
    int size; // ノード数を記録
};
// 順次記憶の文字二分木を初期化
void initSequentialTree(SequentialTree* tree) {
    tree->size = 0;
    for (int i = 0; i < MAX_NODES; i++) {
        tree->nodes[i] = nullptr;
    }
}
// 順次記憶の文字二分木にノードを挿入
void insertNode(SequentialTree* tree, char data) {
    if (tree->size < MAX_NODES) {
        TreeNode* newNode = createNode(data);
        tree->nodes[tree->size] = newNode;
        tree->size++;
    } else {
        printf("この二分木は満杯で、ノードを挿入できません\n");
    }
}
// ルートノードを取得
TreeNode* getRoot(SequentialTree* tree) {
    return tree->nodes[0];
}
// 左子ノードを取得
TreeNode* getLeftChild(SequentialTree* tree, int parentIndex) {
    int leftChildIndex = 2 * parentIndex + 1;
    if (leftChildIndex < tree->size) {//存在するか確認
        return tree->nodes[leftChildIndex];
    }
    return nullptr;
}
// 右子ノードを取得
TreeNode* getRightChild(SequentialTree* tree, int parentIndex) {
    int rightChildIndex = 2 * parentIndex + 2;
    if (rightChildIndex < tree->size) {
        return tree->nodes[rightChildIndex];
    }
    return nullptr;
}
// 先行順走査
void preorderTraversal(struct SequentialTree* tree, int index) {
    if (index >= tree->size || tree->nodes[index]->data == '@') {
        return;
    }
    printf("%c ", tree->nodes[index]->data); // ルートノードにアクセス
    preorderTraversal(tree, 2 * index + 1); // 左部分木を走査
    preorderTraversal(tree, 2 * index + 2); // 右部分木を走査
}
// 中間順走査
void inorderTraversal(struct SequentialTree* tree, int index) {
    if (index >= tree->size || tree->nodes[index]->data == '@') {
        return;
    }
    inorderTraversal(tree, 2 * index + 1); // 左部分木を走査
    printf("%c ", tree->nodes[index]->data); // ルートノードにアクセス
    inorderTraversal(tree, 2 * index + 2); // 右部分木を走査
}
// 後行順走査
void postorderTraversal(struct SequentialTree* tree, int index) {
    if (index >= tree->size || tree->nodes[index]->data == '@') {
        return;
    }
    postorderTraversal(tree, 2 * index + 1); // 左部分木を走査
    postorderTraversal(tree, 2 * index + 2); // 右部分木を走査
    printf("%c ", tree->nodes[index]->data); // ルートノードにアクセス
}
int main() {
    SequentialTree* tree=(SequentialTree*)malloc(sizeof(SequentialTree));
    initSequentialTree(tree);
    char data='a';
    while (1){
        cin>>data;
        if(data=='#'){
            break;
        }
        insertNode(tree,data);
    }
    cout<<"先行順走査結果:"<<endl;
    preorderTraversal(tree,0);
    cout<<endl;
    cout<<"中間順走査結果:"<<endl;
    inorderTraversal(tree,0);
    cout<<endl;
    cout<<"後行順走査結果:"<<endl;
    postorderTraversal(tree,0);
    cout<<endl;
    cout<<"レベル順走査結果:"<<endl;
    for(int i=0;i<tree->size;i++){
        if(tree->nodes[i]->data!='@')
            cout<<tree->nodes[i]->data<<' ';
    }
    cout<<endl;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
// 二分木ノード構造
struct TreeNode {
    char data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char val) : data(val), left(nullptr), right(nullptr) {}
};
// 連鎖記憶域の二分木を作成
TreeNode* createBinaryTree(const string& input) {
    if (input.empty()) {
        return nullptr;
    }
    queue<TreeNode*> nodeQueue;
    TreeNode* root = new TreeNode(input[0]);
    nodeQueue.push(root);
    for (int i = 1; i < input.length(); i += 2) {
        TreeNode* current = nodeQueue.front();
        nodeQueue.pop();
        if (input[i] != '@') {
            current->left = new TreeNode(input[i]);
            nodeQueue.push(current->left);
        }
        if (i + 1 < input.length() && input[i + 1] != '@') {
            current->right = new TreeNode(input[i + 1]);
            nodeQueue.push(current->right);
        }
    }
    return root;
}
// 先行順走査
void preorderTraversal(TreeNode* root) {
    if (root) {
        cout << root->data << " ";
        preorderTraversal(root->left);
        preorderTraversal(root->right);
    }
}
// 中間順走査
void inorderTraversal(TreeNode* root) {
    if (root) {
        inorderTraversal(root->left);
        cout << root->data << " ";
        inorderTraversal(root->right);
    }
}
// 後行順走査
void postorderTraversal(TreeNode* root) {
    if (root) {
        postorderTraversal(root->left);
        postorderTraversal(root->right);
        cout << root->data << " ";
    }
}
// 幅優先探索（レベル順走査）
void breadthFirstTraversal(TreeNode* root) {
    if (!root) {
        return;
    }
    queue<TreeNode*> nodeQueue;
    nodeQueue.push(root);
    while (!nodeQueue.empty()) {
        TreeNode* current = nodeQueue.front();
        nodeQueue.pop();
        cout << current->data << " ";
        if (current->left) {
            nodeQueue.push(current->left);
        }
        if (current->right) {
            nodeQueue.push(current->right);
        }
    }
}
int main() {
    string input;
    cin>>input;
    TreeNode* root = createBinaryTree(input);
    cout << "先行順走査結果: ";
    preorderTraversal(root);
    cout << endl;
    cout << "中間順走査結果: ";
    inorderTraversal(root);
    cout << endl;
    cout << "後行順走査結果: ";
    postorderTraversal(root);
    cout << endl;
    cout << "幅優先探索（レベル順走査）結果: ";
    breadthFirstTraversal(root);
    cout << endl;
    return 0;
}