資料結構實機實驗報告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;
}