题解 | #二叉排序树#

#include<iostream>

using namespace std;

typedef struct node {
    int data;
    struct node* lchild;
    struct node* rchild;
}* BiTree, node;

void firstSearch(node* p);

int main() {
    int n;
    cin >> n;

    int* A = new int[n];
    for (int i = 0; i < n; i++)cin >> A[i];

    node* T = new node;
    if (n > 0) {
        T->data = A[0];
        T->lchild = NULL;
        T->rchild = NULL;
        cout << "-1" << endl;
    }

    for (int i = 1; i < n; i++) {
        node* p;
        node* q;
        q = T;

        while (q != NULL) {
            p = q;
            if (A[i] <= q->data)q = p->lchild;
            else q = p->rchild;
        }

        node* r = new node;
        r->data = A[i];
        r->lchild = NULL;
        r->rchild = NULL;

        if (A[i] <= p->data && p->lchild == NULL) p->lchild = r;
        else if (A[i] > p->data && p->rchild == NULL) p->rchild = r;

        cout << p->data << endl;
    }

    return 0;
}