构造二叉排序树与前序遍历、中序遍历、后序遍历的递归和非递归实现

前序遍历、中序遍历、后序遍历的递归和非递归实现

前序遍历顺序:根->左->右。
中序遍历顺序:左->根->右。
后序遍历顺序:左->右->根。
前序和中序遍历都是先一路向下遍历节点至最左下角的节点，将这一路上的节点入栈。前序遍历入栈时就要打印节点的值；然后出栈一个节点，中序遍历此时才打印该节点的值，然后指针指向该节点的右孩子。这是转向最外层while循环的下一次循环，将右孩子所在的右子树一路向下遍历节点至最左下角的节点，将这一路上的节点入栈，后面的操作与前面相同。
因为前序遍历顺序是根->左->右，所以入栈时就要先打印节点的值（根节点的值）；中序遍历顺序是左->根->右，所以所有节点都入栈完成后，再出栈的节点就是最左孩子或根节点，这时才打印节点的值。
后序遍历需要两个栈，一个栈暂时存储遍历的节点，另一个栈存储最终后序遍历顺序的节点指针。初始暂存栈先存入根节点。然后暂存栈出栈根节点，根节点入结果栈。然后将右孩子节点出栈，右孩子节点入结果栈。将右孩子所在右子树入暂存栈，然后一一出栈将右子树节点入结果栈。然后将左孩子节点出栈，左孩子节点入结果栈。将左孩子所在左子树入暂存栈，然后一一出栈将左子树节点入结果栈。最终结果栈中节点按从栈顶往下分别是左子树节点、左孩子节点、右子树节点、右孩子节点、根节点。最后从结果栈中将节点一一出栈打印即可。

C/C++实现

# include <iostream>
# include <vector>
# include <stack>

using namespace std;

struct treenode {
    int val;
    treenode *leftchild, *rightchild;

    treenode(int x) : val(x), leftchild(nullptr), rightchild(nullptr) {}
};

class Solution {
public:
    treenode *build_binary_sort_tree(vector<int> &nums) {
        if (nums.empty())
            return nullptr;
        treenode *root = new treenode(nums[0]);
        treenode *temp;
        int n = nums.size();
        for (int i = 1; i < n; i++) {
            temp = root;
            while (temp) {
                if (temp->val >= nums[i] && !temp->leftchild) {
                    treenode *newnode = new treenode(nums[i]);
                    temp->leftchild = newnode;
                    break;
                } else if (temp->val < nums[i] && !temp->rightchild) {
                    treenode *newnode = new treenode(nums[i]);
                    temp->rightchild = newnode;
                    break;
                } else if (temp->val >= nums[i])
                    temp = temp->leftchild;
                else if (temp->val < nums[i])
                    temp = temp->rightchild;
            }
        }
        return root;
    }

    void preorder_print_tree_recursive(treenode *root) {
        if (!root)
            return;
        cout << root->val << " ";
        preorder_print_tree_recursive(root->leftchild);
        preorder_print_tree_recursive(root->rightchild);
    }

    void inorder_print_tree_recursive(treenode *root) {
        if (!root)
            return;
        inorder_print_tree_recursive(root->leftchild);
        cout << root->val << " ";
        inorder_print_tree_recursive(root->rightchild);
    }

    void postorder_print_tree_recursive(treenode *root) {
        if (!root)
            return;
        postorder_print_tree_recursive(root->leftchild);
        postorder_print_tree_recursive(root->rightchild);
        cout << root->val << " ";
    }

    void preorder_print_tree(treenode *root) {
        //前序遍历是根->左->右
        if (!root)
            return;
        stack<treenode *> nodes;
        treenode *temp = root;
        while (temp || !nodes.empty()) {
            //前序遍历是根左右,先打印根及其一系列左子树中的左孩子节点,并全部进栈
            while (temp) {
                cout << temp->val << " ";
                nodes.push(temp);
                temp = temp->leftchild;
            }
            // 出栈节点要么是叶子节点(上一个节点的左孩子)要么是根
            // 由于根和左孩子已经打印过,现在就看有无右子树,有的话内层while再循环一次将右孩子的子树上所有左孩子和左子树的根节点全部进栈,进栈时就打印
            if (!nodes.empty()) {
                temp = nodes.top();
                nodes.pop();
                temp = temp->rightchild;
            }
        }
    }

    void inorder_print_tree(treenode *root) {
        //中序遍历是左->根->右
        if (!root)
            return;
        stack<treenode *> nodes;
        treenode *temp = root;
        while (temp || !nodes.empty()) {
            // 开始第一个循环时root的左子树的所有左孩子和左子树的根节点全部进栈
            while (temp) {
                nodes.push(temp);
                temp = temp->leftchild;
            }
            // 出栈,出栈的节点要么是叶子节点(上一个节点的左孩子)要么是根
            // 所以先打印,然后看有无右孩子,有的话内层while再次将右孩子的子树上所有左孩子和左子树的根节点全部进栈
            if (!nodes.empty()) {
                temp = nodes.top();
                nodes.pop();
                cout << temp->val << " ";
                temp = temp->rightchild;
            }
        }
    }

    void postorder_print_tree(treenode *root) {
        stack<treenode *> nodes, results;
        if (!root)
            return;
        nodes.push(root);
        while (!nodes.empty()) {
            // 根节点先入result栈,然后左孩子和右孩子入nodes栈,下一次循环,右孩子入result栈,右子树节点全部入nodes栈
            // 右子树节点入栈完后,左孩子入result栈,然后左子树节点全部入nodes栈
            // 最后result栈中从顶到下依次为左子树、左孩子、右子树、右孩子、根
            treenode *temp = nodes.top();
            nodes.pop();
            results.push(temp);
            if (temp->leftchild)
                nodes.push(temp->leftchild);
            if (temp->rightchild)
                nodes.push(temp->rightchild);
        }
        // result栈保存最后后序遍历顺序的节点,依次取出打印即可
        while (!results.empty()) {
            treenode *temp2 = results.top();
            cout << temp2->val << " ";
            results.pop();
        }
    }
};

int main() {
    vector<int> a = {5, 3, 2, 4, 7, 6, 8};
    //前序结果:5324768
    //中序结果:2345678
    //后序结果:2436875
    Solution s;
    treenode *root = s.build_binary_sort_tree(a);
    s.preorder_print_tree(root);
    cout << endl;
    s.preorder_print_tree_recursive(root);
    cout << endl;
    s.inorder_print_tree(root);
    cout << endl;
    s.inorder_print_tree_recursive(root);
    cout << endl;
    s.postorder_print_tree(root);
    cout << endl;
    s.postorder_print_tree_recursive(root);
    cout << endl;
    return 0;
}