https://pintia.cn/problem-sets/994805342720868352/problems/994805407749357568
完全二叉搜索树
参考慕课讲解:
值得注意的:
①double log(int n) 其实是数学里面的Lg();
所以要做到 log2 n的话使用换底公式是 lg(n)/lg(2)即c语言中的log(n)/log(2);
②如果根结点从0开始,左儿子是 *2+1;
如果根节点从1开始,左儿子是*2
#include<iostream> using namespace std; #include<algorithm> int a[1010],t[1010]; int length(int n) { int h,l; h=(int)(log(n+1)/log(2)); int x=n+1-(int)pow(2,h); x=min(x,(int)pow(2,h-1)); l=(int)pow(2,h-1)-1+x; return l; } void solve(int left,int right,int root) { int n=right-left+1;//n个结点 if(!n)return; int l=length(n);//得到左子树有多少个结点 t[root]=a[left+l]; int leftroot=root*2+1,rightroot=leftroot+1;//孩子在原树中的下标; solve(left,left+l-1,leftroot); solve(left+l+1,right,rightroot); } int main() { int n; cin>>n; for(int i=0;i<n;i++)cin>>a[i]; sort(a,a+n); solve(0,n-1,0); for(int i=0;i<n;i++) if(!i) printf("%d",t[i]); else printf(" %d",t[i]); }
柳婼小姐姐:
性质:二叉搜索树的中序 是递增序列:
可以通过sort得到
#include<iostream> using namespace std;int n; int a[1010],t[1010],cnt=0; #include<algorithm> void inorder(int root) { //通过 中序 还原 层序 二叉搜索树 //可以作为 层序遍历的模板; if(root>=n)return ; inorder(root*2+1);//左儿子 t[root]=a[cnt++]; inorder(root*2+2);//右儿子 //为什么是先 递归左边→→→ 传入数组→→→递归右边 // 和 慕课的层序输出方式相似:in++,if(out) 加入数组同时in++,每次循环结束out++; } int main() { cin>>n; for(int i=0;i<n;i++) cin>>a[i]; sort(a,a+n); inorder(0); printf("%d",t[0]); for(int i=1;i<n;i++) printf(" %d",t[i]); }