完全二叉搜索树
欢迎观看我的博客，如有问题交流，欢迎评论区留言，一定尽快回复！（大家可以去看我的专栏，是所有文章的目录）
文章字体风格：
红色文字表示：重难点
蓝色文字表示：思路以及想法
如果大家觉得有帮助的话，感谢大家帮忙点赞！收藏！转发！
完全二叉搜索树
- 完全二叉树的定义
- 二叉搜索树的定义
- 完全二叉搜索树
- 例题—进阶实验4-3.3 完全二叉搜索树
完全二叉树的定义
倒数第二层以上都排满，最后一层从左到右一次排序，可以不排满
二叉搜索树的定义
根节点的左孩子小于根节点的值
根节点的右孩子大于根节点的值
完全二叉搜索树
既是完全二叉树，又是搜索树
例题—进阶实验4-3.3 完全二叉搜索树
原题链接
本题，我们要构建二叉搜索树，所以我们需要得知所给数据的全部的值，因为得知道所给的所有值，才能进行排序平衡二叉树
所以我们就把所给的数据排序
cin >> n;
for(int i = 1;i<=n;i++){
cin >> in[i];
}
sort(in+1,in+1+n);
然后我们再思考一下，所给一些数据，以随意一个节点作为根节点，都可以构建平衡二叉树，所以这道题，是根据完全二叉树的性质，去构建平衡二叉树，也就是根据完全二叉树的性质，去找根节点。
如何根据完全二叉树的性质，去找根节点呢，我们看图分析
我们已经知道，二叉搜索树的中序遍历是有序的了，那么我们就通过中序遍历的过程，给各个节点从小到大的数值赋值就好了~~~
但是怎么保证是完全二叉树呢？
可以这样，因为我们用数组存储，节点1一定是中序遍历的起始点，因为节点1是存储的是头结点，然后进行中序遍历，直到if(i>n)return;return后回到上一个递归函数，此时该节点一定就可以进行赋值了，且赋的值是，所给节点最小的值的节点（所以还需要 提前准备一下，把所给节点进行排序）
void dfs(int i){
if(i>n)
return;
dfs(2*i);
res[i] = in[++len];
dfs(2*i+1);
}
#include <iostream>
#include <algorithm>
using namespace std;
int in[1001];//中序遍历
int res[1001];//层序遍历，即结果数组
int n,len;
void dfs(int i){
if(i>n)
return;
dfs(2*i);
res[i] = in[++len];
dfs(2*i+1);
}
int main(){
cin >> n;
for(int i = 1;i<=n;i++){
cin >> in[i];
}
sort(in+1,in+1+n);
dfs(1);
for(int i = 1;i<=n;i++){
if(i==1)
cout << res[i];
else
cout << " " << res[i];
}
return 0;
}