题解 | #二叉排序树#

二叉排序树的建树，以及各类遍历统一用非递归算法实现

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int _val) : val(_val), left(NULL), right(NULL) { }
};

TreeNode* createBinaryTree(TreeNode* root, int data) {
    if (root == NULL) {
        TreeNode* node = new TreeNode(data);
        return node;
    }
    TreeNode* tmpNode = root;
    TreeNode* preNode;
    while (tmpNode) {
        if (data < tmpNode->val) {
            preNode = tmpNode;
            tmpNode = tmpNode->left;
        }
        else if (data > tmpNode->val){
            preNode = tmpNode;
            tmpNode = tmpNode->right;
        }
        else {
            return root;
        }
    }
    if (preNode->val < data) preNode->right = new TreeNode(data);
    else preNode->left = new TreeNode(data);
    return root;
}

void preOrderVer2(TreeNode* root) {
    stack<TreeNode*> sck;
    while (!sck.empty() || root != NULL) {
        if (root) {
            cout << root->val << " ";
            sck.push(root);
            root = root->left;
        }
        else {
            TreeNode* tmpNode = sck.top();
            sck.pop();
            root = tmpNode->right;
        }
    }
    cout << endl;
}

//非递归算法
//1、沿着根节点的左孩子，依次入栈，直到左孩子为空，说明已经找到可以输出的结点。
//2、栈顶元素出栈并访问，若其右孩子为空，则继续执行2，若其右孩子不空，将右子树转执行1。

void inOrderVer2(TreeNode* root) {
    stack<TreeNode*> sck;
    while (!sck.empty() || root != NULL) {
        if (root) {
            sck.push(root);
            root = root->left;
        }
        else {
            TreeNode* tmpNode = sck.top();
            sck.pop();
            cout << tmpNode->val << " ";
            root = tmpNode->right;
        }
    }
    cout << endl;
}

void lastOrderVer2(TreeNode* root) {
    stack<TreeNode*> sck;
    vector<int> vec;
    while (!sck.empty() || root != NULL) {  
        if (root) {
            vec.push_back(root->val);
            sck.push(root);
            root = root->right;
        }
        else {
            TreeNode* tmpNode = sck.top();
            sck.pop();
            root = tmpNode->left;
        }
    }
    for (int i = vec.size() - 1; i >= 0; i--) {  //根右左 ---> 左右根
        cout << vec[i] << " ";
    }
    cout << endl;
}

int main() 
{
    int N;
    while (cin >> N) {
        TreeNode* root = NULL;
        int data;
        while (N--) {
            cin >> data;
            root = createBinaryTree(root, data);
        }
        preOrderVer2(root);
        inOrderVer2(root);
        lastOrderVer2(root);
    }
    return 0;
}