首页 > 代码库 > 1064. Complete Binary Search Tree (30)
1064. Complete Binary Search Tree (30)
题意:给出一列数字,可以构成完全二叉搜索树,求构成的完全二叉搜索树的层次遍历
思路:构建树的过程可以看做是不断寻找子树根节点的过程
根据完全二叉树的特征,可以通过确定左子树的子孙节点个数来确定对应的根节点下标
思路:构建树的过程可以看做是不断寻找子树根节点的过程
根据完全二叉树的特征,可以通过确定左子树的子孙节点个数来确定对应的根节点下标
递归构建即可。
代码:
#include<iostream> #include<vector> #include<cmath> #include<algorithm> #include<fstream> using namespace std; vector<int>nodes; /** @parm l,r point for nodes @parm trees store constructed CBT @parm pos position for trees */ void buildCBT(int l,int r,const vector<int> &nodes ,vector<int> &trees,int pos){ if(l>r)return; if(l==r){ trees[pos] = nodes[l]; }else { int sumNode = r - l +1; int level = log((double)sumNode)/log((double)2) +1; int lastLevelNodes = pow((double)2,level-1); int knodes=lastLevelNodes-1;//除去最后一行的节点数 int lastRealNodes = sumNode -knodes; int offset =0; if(lastRealNodes>=lastLevelNodes/2){ offset = lastLevelNodes/2; }else{ offset = lastRealNodes; } int nodeIndex=l+knodes/2 +offset; //cout<<"nodeIndex "<<nodeIndex<<" "<<endl; trees[pos] = nodes[nodeIndex]; //cout<<"trees[pos] "<<trees[pos]<<" "; buildCBT(l,nodeIndex-1,nodes,trees,2*pos); buildCBT(nodeIndex+1,r,nodes,trees,2*pos+1); } } int main(){ ifstream cin("data.txt"); int num; cin>>num; int k; for(int i=0;i<num;++i){ cin>>k; nodes.push_back(k); } vector<int>trees(num+1); sort(nodes.begin(),nodes.end()); buildCBT(0,num-1,nodes,trees,1); for(int i=1;i<trees.size()-1;++i){ cout<<trees[i]<<" "; } cout<<trees[trees.size()-1]<<"\n"; //system("pause"); }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。