二叉树前中后序遍历的递归和非递归实现

#include <stack>
#include <iostream>

using namespace std;

struct Node {
    int data;
    Node *left, *right;

    explicit Node(int data) {
        this->data = data;
        left = right = nullptr;
    }
};

/**
 * 1) Create an empty stack nodeStack and push root node to stack.
 * 2) Do following while nodeStack is not empty.
 *     a) Pop an item from stack and print it.
 *     b) Push right child of popped item to stack
 *     c) Push left child of popped item to stack
 *
 * Right child is pushed before left child to make sure that left subtree is processed first.
 */
void preOrder(Node *root) {
    if (!root)
        return;
    // Create an empty stack and push root to it
    stack<Node *> s;
    s.push(root);

    /**
     * Pop all items one by one. Do following for every popped item
     *     a) print it
     *     b) push its right child
     *     c) push its left child
     * Note that right child is pushed first so that left is processed first
     */
    while (!s.empty()) {
        // Pop the top item from stack and print it
        Node *node = s.top();
        s.pop();
        cout << node->data << " ";

        // Push right and left children of the popped node to stack
        if (node->right)
            s.push(node->right);
        if (node->left)
            s.push(node->left);
    }
}

/**
 *  1) Create an empty stack S.
 *  2) Initialize current node as root
 *  3) Push the current node to S and set current = current->left until current is NULL
 *  4) If current is NULL and stack is not empty then
 *      a) Pop the top item from stack.
 *      b) Print the popped item, set current = popped_item->right
 *      c) Go to step 3.
 *  5) If current is NULL and stack is empty then we are done.
 */
void inOrder(Node *root) {
    stack<Node *> s;
    while (root || !s.empty()) {
        while (root) {
            s.push(root);
            root = root->left;
        }
        root = s.top();
        s.pop();
        cout << root->data << " ";
        root = root->right;
    }
}


void postOrderTowStack(Node *root) {
    if (!root)
        return;

    stack<Node *> s1;
    stack<Node *> s2;
    Node *node;

    s1.push(root);
    while (!s1.empty()) {
        node = s1.top();
        s1.pop();
        s2.push(node);
        if (node->left)
            s1.push(node->left);
        if (node->right)
            s2.push(node->right);
    }

    while (!s2.empty()) {
        node = s2.top();
        s2.pop();
        cout << node->data << " ";
    }
}

/**
 * 1.1 Create an empty stack
 * 2.1 Do following while root is not NULL
 *     a) Push root's right child and then root to stack.
 *     b) Set root as root's left child.
 *
 * 2.2 Pop an item from stack and set it as root.
 *     a) If the popped item has a right child and the right child
 *        is at top of stack, then remove the right child from stack,
 *        push the root back and set root as root's right child.
 *     b) Else print root's data and set root as NULL.
 *
 * 2.3 Repeat steps 2.1 and 2.2 while stack is not empty.
 */
void postOrder(Node *root) {
    if (!root)
        return;
    stack<Node *> s;
    do {
        while (root) {
            if (root->right)
                s.push(root->right);
            s.push(root);
            root = root->left;
        }
        root = s.top();
        s.pop();

        if (root->right && !s.empty() && s.top() == root->right) {
            s.pop();
            s.push(root);
            root = root->right;
        } else {
            cout << root->data << " ";
            root = nullptr;
        }

    } while (!s.empty());
}


void preOrderRecursive(Node *root) {
    if (!root)
        return;
    cout << root->data << " ";
    preOrderRecursive(root->left);
    preOrderRecursive(root->right);
}

void inOrderRecursive(Node *root) {
    if (!root)
        return;
    inOrderRecursive(root->left);
    cout << root->data << " ";
    inOrderRecursive(root->right);
}

void postOrderRecursive(Node *root) {
    if (!root)
        return;
    postOrderRecursive(root->left);
    postOrderRecursive(root->right);
    cout << root->data << " ";
}

int main() {
    Node *root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);

    cout << "前序遍历(递归)结果是：\n";
    preOrderRecursive(root);
    cout << endl;

    cout << "中序遍历(递归)结果是：\n";
    inOrderRecursive(root);
    cout << endl;

    cout << "后续遍历(递归)结果是：\n";
    postOrderRecursive(root);
    cout << endl;

    cout << "------------------\n";
    cout << "前序遍历结果是：\n";
    preOrder(root);
    cout << endl;

    cout << "中序遍历结果是：\n";
    inOrder(root);
    cout << endl;

    cout << "后续遍历(双栈)结果是：\n";
    postOrderTowStack(root);
    cout << endl;

    cout << "后续遍历结果是：\n";
    postOrder(root);
    cout << endl;

    return 0;
}

结果是

前序遍历(递归)结果是：
1 2 4 5 3 
中序遍历(递归)结果是：
4 2 5 1 3 
后续遍历(递归)结果是：
4 5 2 3 1 
------------------
前序遍历结果是：
1 2 4 5 3 
中序遍历结果是：
4 2 5 1 3 
后续遍历(双栈)结果是：
4 5 2 3 1 
后续遍历结果是：
4 5 2 3 1