本文主要是介绍PAT甲级1064 Complete Binary Search Tree (30分):[C++题解]完全二叉搜索树BST,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
文章目录
- 题目分析
- 题目链接
题目分析
思路: 第一步,构造含有n个结点的完全二叉树;第二步,将n个数值填入,使其满足二叉搜索树的性质。
对于第一步:
完全二叉树用一维数组可以存下,不过从根结点的下标是1. 对于一个下标为x的结点,左儿子是2x,右儿子是2x+1,它的父节点坐标 ⌊ x 2 ⌋ \lfloor \frac{x}{2}\rfloor ⌊2x⌋。
对于第二步:
满足二叉搜索树的性质? 就是左子树的值小于根结点,根结点的值小于等于右子树。 换个等价的说法,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];
}
题目链接
PAT甲级1064 Complete Binary Search Tree (30分)
这篇关于PAT甲级1064 Complete Binary Search Tree (30分):[C++题解]完全二叉搜索树BST的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!