C++二叉树前序、中序、后序遍历实现技术咨询

Hey there! Let's work through implementing those three binary tree traversal functions for your C++ project. First, let's clarify a quick detail: your BTree class should have a private TNode* root member (since your constructor initializes it), so we'll build our functions around that. We'll cover both recursive (simple, readable) and iterative (avoids stack overflow for deep trees) implementations for each traversal.

This traversal visits the root node first, then recursively traverses the left subtree, followed by the right subtree.

Recursive Implementation #

First, let's finish the print_pre_order method you started, then add a public no-argument wrapper to use the root:

// Inside BTree class declaration (add these if missing):
// private:
//     TNode* root;
//     void print_pre_order(TNode* r);
// public:
//     void print_pre_order() { print_pre_order(root); }

void BTree::print_pre_order(TNode *r) {
    if (!r) return; // Base case: null node, do nothing
    
    // 1. Visit the root node
    std::cout << r->val << " ";
    // 2. Traverse left subtree
    print_pre_order(r->left);
    // 3. Traverse right subtree
    print_pre_order(r->right);
}

Iterative Implementation (Using Stack) #

Recursion uses the call stack under the hood—we can simulate this manually with a stack container:

void BTree::print_pre_order_iterative() {
    if (!root) return;
    
    std::stack<TNode*> node_stack;
    node_stack.push(root);
    
    while (!node_stack.empty()) {
        TNode* curr = node_stack.top();
        node_stack.pop();
        
        std::cout << curr->val << " ";
        
        // Push right first (stack is LIFO, so left gets processed next)
        if (curr->right) node_stack.push(curr->right);
        if (curr->left) node_stack.push(curr->left);
    }
}

This traversal visits the left subtree first, then the root, then the right subtree. It's commonly used to get nodes in sorted order for a binary search tree.

Recursive Implementation #

Again, we'll use a helper function for the recursive logic, with a public wrapper:

// Inside BTree class:
// private:
//     void print_in_order_helper(TNode* r);
// public:
//     void print_in_order() { print_in_order_helper(root); }

void BTree::print_in_order_helper(TNode *r) {
    if (!r) return;
    
    // 1. Traverse left subtree
    print_in_order_helper(r->left);
    // 2. Visit the root node
    std::cout << r->val << " ";
    // 3. Traverse right subtree
    print_in_order_helper(r->right);
}

Iterative Implementation (Using Stack) #

This one requires us to traverse all the way to the leftmost node first:

void BTree::print_in_order() {
    std::stack<TNode*> node_stack;
    TNode* curr = root;
    
    while (curr || !node_stack.empty()) {
        // Traverse to the leftmost node
        while (curr) {
            node_stack.push(curr);
            curr = curr->left;
        }
        
        curr = node_stack.top();
        node_stack.pop();
        
        std::cout << curr->val << " ";
        
        // Move to the right subtree
        curr = curr->right;
    }
}

This traversal visits the left subtree, then the right subtree, and finally the root node. It's useful for operations like deleting a tree.

Recursive Implementation #

Similar pattern with a helper function:

// Inside BTree class:
// private:
//     void print_post_order_helper(TNode* r);
// public:
//     void print_post_order() { print_post_order_helper(root); }

void BTree::print_post_order_helper(TNode *r) {
    if (!r) return;
    
    // 1. Traverse left subtree
    print_post_order_helper(r->left);
    // 2. Traverse right subtree
    print_post_order_helper(r->right);
    // 3. Visit the root node
    std::cout << r->val << " ";
}

Iterative Implementation (Using Two Stacks) #

Postorder is trickier iteratively—one common approach uses two stacks to reverse the order of nodes:

void BTree::print_post_order() {
    if (!root) return;
    
    std::stack<TNode*> stack1, stack2;
    stack1.push(root);
    
    while (!stack1.empty()) {
        TNode* curr = stack1.top();
        stack1.pop();
        stack2.push(curr);
        
        // Push left first, then right (so right is processed first in stack1)
        if (curr->left) stack1.push(curr->left);
        if (curr->right) stack1.push(curr->right);
    }
    
    // Stack2 now has nodes in postorder order
    while (!stack2.empty()) {
        std::cout << stack2.top()->val << " ";
        stack2.pop();
    }
}

Quick Notes #

• Don't forget to include <iostream> and <stack> headers in your code to use std::cout and std::stack.
• The parent pointer in TNode isn't used for these basic traversals, but it could be useful for more advanced methods like Morris traversal (which avoids stacks entirely).
• Recursive implementations are great for readability, but if your tree is extremely deep (10,000+ nodes), they might cause a stack overflow—use iterative versions in that case.

内容的提问来源于stack exchange，提问作者abc-cba