题解 | #二叉排序树#

#include <iostream>
#include <algorithm>
#include "string"
using namespace std;
const int N=100010;
typedef struct Binary_Node{
    int dad;
    int val;
    struct Binary_Node *lchild;
    struct Binary_Node *rchild;
}*BTree,Binary_Node;
int n;
int a[N];

int BST_insert(BTree &T,int x,int father){
    if(T==NULL){
        T= (BTree)malloc(sizeof(Binary_Node));
        T->dad=father;
        T->val=x;
        T->lchild=T->rchild=NULL;
        return 1;
    } else
    if(x<T->val){
        return BST_insert(T->lchild,x,T->val);
    } else if(x>T->val){
        return BST_insert(T->rchild,x,T->val);
    }
    return 0;
}
BTree BST_search(BTree T,int x){
    while(T!=NULL && x!=T->val){
        if(x<T->val)
            T=T->lchild;
        else
            T=T->rchild;
    }
    return T;
}

int main() {
    cin >>n;
    BTree  T=NULL;
    for(int i=0;i<n;i++){
        int x;
        scanf("%d",&x);
        a[i] =x;
        BST_insert(T,x,-1);
    }
    for(int i=0;i<n;i++){
        BTree idx=BST_search(T,a[i]);
        printf("%d\n",idx->dad);
    }
    return 0;
}