题解 | #二叉排序树#

#include<iostream>
using namespace std;
typedef struct node {
    int num;
    struct node* left, * right;
    node(int n) :num(n), left(NULL), right(NULL) {}
}TreeNode, * Tree;
void Insert(Tree &root, int num,int &ans) {
    if (root == NULL) {
        root = (Tree)malloc(sizeof(TreeNode));
        root->left = NULL;
        root->right = NULL;
        root->num = num;
        ans = -1;
        return;
    }
    else if(root != NULL){
        int tag = 0;
        if (num < root->num) {
            if (root->left == NULL)
                tag = 1;
            Insert(root->left, num,ans);
            if (tag){
                 ans = root->num;
                return;
            }
        }
        else {
            if (root->right == NULL)
                tag = 1;
            Insert(root->right, num,ans);
            if (tag){
                ans = root->num;
                return;
            }
        }
    }
}
int main()
{
    int n, num,ans;
    while (cin >> n ) {
        Tree root = NULL;
        for (int i = 0; i < n; ++i) {
            cin >> num;
            Insert(root, num,ans);
            cout << ans << endl;
        }
    }
}