【题目来源】 https://www.acwing.com/problem/content/3598/ 【题目描述】 二叉排序树，也称为二叉查找树。 可以是一颗空树，也可以是一颗具有如下特性的非空二叉树： 1.若左子树非空，则左子树上所有节点关键字值均不大于根节点的关键字值； 2.若右子树非空，则右子树上所有节点关键字值均不小于根节点的关键字值； 3.左、右子树本身也是一颗二叉排序树。 现在给你 N 个关键字值各不相同的节点。 要求你将这些节点按顺序插入一个初始为空树的二叉排序树中。 每次成功插入一个节点后，求其相应的父亲节点的关键字值，如果没有父亲节点，则输出 −1。 【输入格式】 第一行包含整数 N，表示待插入的节点数。 第二行包含 N 个互不相同的正整数，表示要顺序插入节点的关键字值。 【输出格式】 N 行。 【输入样例】 5 2 5 1 3 4 【输出样例】 -1 2 2 5 3 【数据范围】 1≤N≤100， 节点关键字值取值范围 [1,10^8]。 【算法分析】 ● 二叉排序树（Binary Sort Tree，BST），又称二叉搜索树。二叉排序树或者是一棵空树，或者是具有下列性质的二叉树。 （1）若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； （2）若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； （3）它的左、右子树也分别为二叉排序树。 ● 二叉排序树遵循“左小右大”规则，树中没有相同关键字的结点。 ● 中序遍历一棵二叉排序树可以得到一个结点值递增的有序序列。 ● 东方博宜OJ 2195：二叉排序树：https://blog.csdn.net/hnjzsyjyj/article/details/164402681 【算法代码】
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int lch[maxn],rch[maxn];
int val[maxn];
int tot;
int new_node(int x) {
tot++;
val[tot]=x;
lch[tot]=0;
rch[tot]=0;
return tot;
}
int insert(int u,int x) {
if(x<val[u]) {
if(lch[u]==0) {
lch[u]=new_node(x);
return val[u];
} else insert(lch[u],x);
} else {
if(rch[u]==0) {
rch[u]=new_node(x);
return val[u];
} else insert(rch[u],x);
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n,x,root;
cin>>n;
for(int i=1; i<=n; i++) {
cin>>x;
if(i==1) {
root=new_node(x);
cout<<-1<<"\\n";
} else cout<<insert(root,x)<<"\\n";
}
return 0;
}
/*
in:
5
2 5 1 3 4
out:
-1
2
2
5
3
*/
【参考文献】 https://blog.csdn.net/hnjzsyjyj/article/details/164402681 https://blog.csdn.net/hnjzsyjyj/article/details/164403599 https://blog.csdn.net/hnjzsyjyj/article/details/163743086 https://blog.csdn.net/hnjzsyjyj/article/details/154818899
