申論題

從定義二元樹節點開始：

#include <iostream>
#include <queue>

// Node definition
struct Node {
    char data;
    Node* left;
    Node* right;
    Node(char data) : data(data), left(nullptr), right(nullptr) {}
};

// Binary tree class
class BinaryTree {
public:
    Node* root;

    BinaryTree() : root(nullptr) {}

    // Pre-order traversal
    void preOrder(Node* node) {
        if (node == nullptr) return;
        std::cout << node->data << " ";
        preOrder(node->left);
        preOrder(node->right);
    }

    // In-order traversal
    void inOrder(Node* node) {
        if (node == nullptr) return;
        inOrder(node->left);
        std::cout << node->data << " ";
        inOrder(node->right);
    }

    // Post-order traversal
    void postOrder(Node* node) {
        if (node == nullptr) return;
        postOrder(node->left);
        postOrder(node->right);
        std::cout << node->data << " ";
    }

    // Level-order traversal
    void levelOrder(Node* node) {
        if (node == nullptr) return;
        std::queue<Node*> queue;
        queue.push(node);
        
        while (!queue.empty()) {
            Node* current = queue.front();
            queue.pop();
            std::cout << current->data << " ";
            if (current->left != nullptr) queue.push(current->left);
            if (current->right != nullptr) queue.push(current->right);
        }
    }
};

int main() {
    // Construct the tree as per the diagram
    BinaryTree tree;
    tree.root = new Node('A');
    tree.root->left = new Node('B');
    tree.root->right = new Node('C');
    tree.root->left->left = new Node('D');
    tree.root->left->right = new Node('E');
    tree.root->right->left = new Node('F');
    tree.root->left->left->left = new Node('G');
    tree.root->left->left->right = new Node('H');
    tree.root->right->left->right = new Node('I');

    // Perform the traversals
    std::cout << "Preorder: ";
    tree.preOrder(tree.root);
    std::cout << std::endl;

    std::cout << "Inorder: ";
    tree.inOrder(tree.root);
    std::cout << std::endl;

    std::cout << "Postorder: ";
    tree.postOrder(tree.root);
    std::cout << std::endl;

    std::cout << "Levelorder: ";
    tree.levelOrder(tree.root);
    std::cout << std::endl;

    return 0;
}
這段代碼創建了一個簡單的二元樹，並使用你提供的圖表填充它。然後，它分別以 pre-order、in-order、post-order 和 level-order 順序遍歷樹。每個遍歷函數都是二元樹類的成員函數，它們遞歸地處理樹的節點，直到達到 nullptr。遍歷結果將按照題目要求的順序輸出。