企业官网建设流程全解析

【题目来源】
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 N=105; int val[N]; vector<int> g[N]; int tot=0; 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(u==0) { u=get_idx(x); return -1; } int &ch=(x<val[u])?g[u][0]:g[u][1]; if(ch==0) { ch=get_idx(x); return val[u]; } else insert(ch,x); } int main() { int n,x,root=0; cin>>n; for(int i=1; i<=n; i++) { cin>>x; cout<<insert(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/163743086
https://blog.csdn.net/hnjzsyjyj/article/details/154818899