PAT甲级1064 Complete Binary Search Tree (30分)：[C++题解]完全二叉搜索树BST

本文主要是介绍PAT甲级1064 Complete Binary Search Tree (30分)：[C++题解]完全二叉搜索树BST，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

- 题目分析
- 题目链接

题目分析

思路: 第一步，构造含有n个结点的完全二叉树；第二步，将n个数值填入，使其满足二叉搜索树的性质。

对于第一步：

完全二叉树用一维数组可以存下，不过从根结点的下标是1. 对于一个下标为x的结点，左儿子是2x，右儿子是2x+1，它的父节点坐标 $\lfloor \frac{x}{2}\rfloor$ 。

对于第二步：

满足二叉搜索树的性质？就是左子树的值小于根结点，根结点的值小于等于右子树。换个等价的说法，BST的中序遍历是递增的。所以把给定的n个数值，从小到大排序，这就是二叉搜索树的中序遍历的顺序，之后中序遍历构造好的完全二叉树，边遍历边填入即可。

本题让输出完全BST的层序遍历，就是数组按序输出。

ac代码

#include<bits/stdc++.h>
using namespace std;const int N = 1010;
int n;
int w[N];//表示权值
int tree[N]; //树中的结点// u是结点编号，从1开始
void dfs(int u , int & k){  //中序遍历if(u*2 <= n)  dfs(u*2, k);tree[u] = w[k++];if(u*2 + 1 <= n) dfs(u*2+1 , k);
}
int main(){cin>> n;for(int i= 0 ;i< n; i++) cin>>w[i];sort(w,w+n);int k = 0;dfs(1,k); //中序遍历完全二叉树cout<<tree[1];for(int i=2;i<=n;i++) cout<<" "<<tree[i];
}