PAT (Advanced Level) 1064 Complete Binary Search Tree

水深无声 2022-04-16 03:47 91阅读 0赞

1064 Complete Binary Search Tree （30 分）

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个非负整数，用他们构建一棵完全二叉排序树，输出这棵树的层序遍历序列。   
分析：用数组CBT在存放完全二叉树，对完全二叉树中的任意一个节点x，其左孩子结点的编号为2x，右孩子编号为2x+1 对一棵二叉排序树来说，其中序遍历序列是递增的，所以先将给定数字从小到大排序，然后对CBT数组表示的二叉树进行中序遍历,并再遍历过程中将数字从小到大填入数组，因为你本来中序遍历出的数就是递增的,上面的过程只是逆向还原二叉排序树  
最这个还原出来的CBT就是二叉排序树层序遍历二叉排序树的顺序 。

用到的知识：

二叉树的中序遍历：

中序遍历：若二叉树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后访问根结点，最后中序遍历右子树。

特点：①. 左----->根------->右

②. 根据中序遍历的结果，再结合前序遍历的root结点去划分root结点的左右子树。

代码实现：

//中序遍历二叉树：左---根---右
    void middleScanf(TreeNode* t)
    {
    	if (t == NULL)
    	{
    		return;
    	}
    	middleScanf(t->left);
    	cout << t->val << " ";
    	middleScanf(t->right);
    }

二叉排序树：  
二叉排序树，又叫二叉查找树，它或者是一棵空树；或者是具有以下性质的二叉树：  
1. 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；  
2. 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；  
3. 它的左右子树也分别为二叉排序树。

例如：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdqaWFuNTMw_size_16_color_FFFFFF_t_70][]

AC代码：

#include <iostream>
    #include <algorithm>
    #define MAXN 2010 
    using namespace std;
    int N, number[MAXN], index = 0; 
    int CBT[MAXN]; //完全二叉树存放的数组 
    void InOrderTraversal(int root) { //中序遍历时赋值
    	if(root > N) return; 
    	InOrderTraversal(2 * root); //遍历左子树
    	CBT[root] = number[index++];
    	InOrderTraversal(2 * root + 1); //遍历右子树 
    }
    int main(){
    	cin >> N;
    	for(int i = 0; i < N; i++) {
    		cin >> number[i];
    	} 
    	sort(number, number + N); //排成有序数组
    	InOrderTraversal(1); //从第一个节点开始遍历
    	for(int j = 1; j <= N; j++) { //层序遍历输出 
    		cout << CBT[j]; 
    		if(j != N) cout << " ";
    	} 
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdqaWFuNTMw_size_16_color_FFFFFF_t_70]: /images/20220416/72ef444dd38149dab92a9836fb485718.png