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