二叉排序树（建树）

Problem Link：http://139.129.36.234/problem.php?id=1274

题目描述

二叉排序树，也称为二叉查找树。先给你N个关键值各不相同的结点，要求那你按顺序插入一个初始为空树的二叉排序中，每次插入成功后，求相应的父节点的关键字值，如果没有父节点，则输出-1.

输入

第一行一个数字N(N<=100),表示待插入节点数。 第二行，N个互不相同的正整数，表示要顺序插入节点的关键字值，这些值不超过10 8

输出

输出一行N个数，分别表示每次插入节点后，该节点对于的父节点的关键字值。

样例输入

5 2 5 1 3 4

样例输出

-1 2 2 5 3

提示

来源

北邮机试真题

AC code：

#include<iostream> #include<algorithm> #include<stdio.h> #include<map> #include<math.h> #include<string.h> #include<queue> #include<vector> #include<set> #define LL long long #define exp 1e-9 #define MAXN 1000010 using namespace std; typedef struct BTNode{ int data; BTNode *lchild; BTNode *rchild; }BTNode; void insertBT(BTNode *&bt,int x) { BTNode *pre,*p; p=bt; int dir=0; if(p==NULL) { bt = (BTNode *)malloc(sizeof(BTNode)); bt->data=x; bt->lchild=NULL; bt->rchild=NULL; printf("-1 "); } else { while(p!=NULL) { pre=p; if(p->data>x) { p=p->lchild; } else { p=p->rchild; } } p = (BTNode *)malloc(sizeof(BTNode)); p->data=x; p->lchild=NULL; p->rchild=NULL; if(pre->data>x) { pre->lchild=p; } else { pre->rchild=p; } printf("%d ",pre->data); } } int main() { // freopen("D:\\in.txt","r",stdin); int n,i,x; scanf("%d",&n); BTNode *bt=NULL; for(i=1;i<=n;i++) { scanf("%d",&x); insertBT(bt,x); } puts(""); return 0; }