当前位置：首页 > news >正文

PAT 1064 Complete Binary Search Tree

news 2025/8/16 11:51:46

在这里插入图片描述

这一题的意思是给出N个key，这N个key是一个完全二叉搜索树的每一个节点的值。
让我们找到这样的一棵完全二叉搜索树的层次遍历序列是什么样的
要想找到题目中要求的二叉搜索树的层次遍历序列。
首先我们应该建成这棵树才能得出层次遍历序列。
那么仅根据题目上知道的一个节点值的序列就能得出这棵树吗？
可以的，这要求我们需要弄明白完全二叉树和二叉搜索树的性质。
首先，如果一棵树是完全二叉树，那么它的节点序列一定是：根（i），则左孩子为（i2+1)，右孩子为（i2+2).
那么有N个节点，那么它的序列就是从0-N-1.
那么我们就不用像之前做树的题一样，用结构体建树，而是用一个数组来建树，数组的索引即为节点，数组的值即为节点值。
于是就可以得到

vector<int> tree(1005);

单单建一棵完全二叉树是不够的，还需要满足二叉搜索树的性质，即左《根《右
那么如何保证这种插入方式呢？
我们对给出的序列进行一个排序，从小到大的排序。
然后对我们建好的树进行中序遍历，按照中序遍历的方式依次插入排好的序列。

void createCBT(int i)
{if(i>=N){return ;}else{createCBT(i*2+1);tree[i]=x[cnt];cnt++;createCBT(i*2+2);}	
}

这样一棵好的完全二叉搜索树就建成了。只需要对它进行层次遍历即可
完整代码如下：

#include <iostream>
#include <limits.h>
#include <cstring>
#include <queue>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
using namespace std;
int N;
int x[1005];
vector<int> tree(1005);
bool cmp(int a,int b)
{return a<b;
}
queue<int> q;
int cnt;
void createCBT(int i)
{if(i>=N){return ;}else{createCBT(i*2+1);tree[i]=x[cnt];cnt++;createCBT(i*2+2);}	
}
void leveorder(int root)
{q.push(root);bool flag=0;while(!q.empty()){int x=q.front();if(flag==0){flag=1;cout<<tree[x];if(x*2+1<N){q.push(x*2+1);}if(x*2+2<N){q.push(x*2+2);} }else{cout<<" "<<tree[x];if(x*2+1<N){q.push(x*2+1);}if(x*2+2<N){q.push(x*2+2);} }q.pop();}
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>N;for(int i=0;i<N;i++){cin>>x[i];}sort(x,x+N,cmp);//对一棵有N个节点的完全二叉树进行中序遍历createCBT(0);leveorder(0);return 0;}