• 欢迎访问废江's博客 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏本站吧

04-树6 Complete Binary Search Tree

浙大mooc 站点默认 1个月前 (11-12) 16次浏览 已收录 1个评论

A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:

The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
Both the left and right subtrees must also be binary search trees.
A Complete Binary Tree (CBT) is a tree that is completely filled, with the possible exception of the bottom level, which is filled from left to right.

Now given a sequence of distinct non-negative integer keys, a unique BST can be constructed if it is required that the tree must also be a CBT. You are supposed to output the level order traversal sequence of this BST.

Input Specification:
Each input file contains one test case. For each case, the first line contains a positive integer N (≤1000). Then N distinct non-negative integer keys are given in the next line. All the numbers in a line are separated by a space and are no greater than 2000.

Output Specification:
For each test case, print in one line the level order traversal sequence of the corresponding complete binary search tree. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.

Sample Input:
10
1 2 3 4 5 6 7 8 9 0
Sample Output:
6 3 8 1 5 7 9 0 2 4

题意:给出n个节点,我们需要把它放在完全二叉树里面,并且保持二叉搜索树的性质,之后层次遍历输出这颗完全二叉搜索树的所有节点

思路:我们把给定的节点排好序放在一个数组里,因为我们要把这些书放在一颗完全二叉树里面,所以给我们n的节点,我们肯定可以求出左子树有多少个,这样就知道这个二叉树的根了,及数组里面前n个是左子树,n+1是根节点,因为它要满足搜索二叉树的性质,即左子树的节点小于跟节点,之后便是递归求根节点的下面的左子树的根节点和右子树的根节点,递归就可以完成,这一题花了我大约两个多小时,主要还是递归那个函数不会写,收获很多,这题我肯定要写个总结了

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int tree[1001];
int value[1001];
int k=0;//k为tree的数组下标
//思路理一遍,我们先把读入的数据排好放在一个数组里,接着递归去找根节点。。。
int seekroot(int n) { //给二叉树的n个节点,返回其最大左子树的个数
	int i;
	for ( i = 1; n >=pow(2, i) - 1; i++) {
	}
	if((n-(pow(2,i-1)-1))<=pow(2,i-2))
		return (pow(2, i - 1) - 1) / 2 + (n - pow(2, i - 1) + 1);
	else
		return (pow(2, i - 1) - 1) / 2 + pow(2, i - 2);
}
void solve(int left ,int right ,int root) {
	int leftroot, rightroot;
	int n = right - left + 1;
	if (n == 0) return;
	int l = seekroot(n);//偏移量
	tree[root] = value[left + l];
	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 >> value[i];
	sort(value, value + n);
	solve(0, n - 1, 0);
	//太特么坑的我头破血流。。这个n变了,最后变成了0,找了老半天的bug,因为n我设为了全局变量
	bool flag=0;
	for (int i = 0; i < n; i++) {
		if(flag)
		cout<<" ";
		cout << tree[i] ;
		flag=1;
	}
}

个人博客 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:04-树6 Complete Binary Search Tree
喜欢 (1)
[]
分享 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到
(1)个小伙伴在吐槽