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

04-树6 Complete Binary Search Tree

浙大mooc 站点默认 11个月前 (11-12) 150次浏览 已收录 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是根节点,因为它要满足搜索二叉树的性质,即左子树的节点小于跟节点,之后便是递归求根节点的下面的左子树的根节点和右子树的根节点,递归就可以完成,这一题花了我大约两个多小时,主要还是递归那个函数不会写,收获很多,这题我肯定要写个总结了


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

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