PAT甲級1064 Complete Binary Search Tree(30分)二叉木配列記憶+二叉木の遍歴C/C++/Python

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

テーマ:
二叉探索ツリー(BST)は、以下の定義を有する二叉ツリーである.

左サブツリーのすべてのノード(存在する場合)のキーワードはルートノードよりも小さい.

右サブツリーのすべてのノード(存在する場合)のキーワードは、ルートノードよりも小さくありません.

その左/右サブツリー自体も二叉探索ツリー(BST)である.

完全二叉木(CBT):
二叉木の深さをhとすると、第h層を除いて、他の各層(1〜h−1)の結点数が最大個数に達し、第h層のすべての結点が連続して最左に集中し、これが完全二叉木である.
ここで、N個のキーワードが与えられ、これらのキーワードのツリーノードからなる特定のツリーが、ツリーであり、完全なツリーであり、完全なツリーである.
入力:第1行N:何個のノード(キーワード)
2行目N個の非負の整数:キーワードシーケンス
アルゴリズムの考え方:

出力は層順に遍歴されるので、この二叉木は配列記憶法が最適である.二叉木の配列順序は層順遍歴の順序であるからである.

配列は、下付き1から始まると、左の子ノードが下付き(2*i)、右の左の子ノードが下付き(2*i+1)の各ノードを表す.

この二叉木をどのように構築しますか?二叉検索ツリーの中順遍歴は、このツリーキーの非降順ソートであることに注意してください.入力したN個の数を降順でない順に並べておくと、このツリーの中順遍歴時の出力シーケンスが得られます.これは、このツリーが既に構築されているとして、このツリーを中順に遍歴し、ルートノードにアクセスする操作を付与ルートノードに置き換えることでこのツリーを構築できます.

は、最後に、二叉木を格納する配列順に遍歴する、すなわち、層順に遍歴する.

C++コードは以下の通りです.

#include
#include
using namespace std;
const size_t MAX_N = 1001;
int NUM;	//     
int A[MAX_N];	//BST        
int BT[MAX_N];	//        ，  BT[0]  ！
size_t ib = 0;	//      BST ， BST[]    
void inorder(size_t i) {
	if (i > NUM)return;	//     ——>      
	inorder(2 * i);		//     
	BT[i] = A[ib++];	//   ( BST        )
	inorder(2 * i + 1);	//     
}
int main() {
	scanf("%d
", &NUM);
	for (size_t i = 0; i < NUM; i++) {
		scanf("%d", &A[i]);
	}
	sort(A, A + NUM);		//       BST         
	inorder(1);		//             
	printf("%d", BT[1]);	//                  ，        。
	for (size_t i = 2; i <= NUM; i++) {
		printf(" %d", BT[i]);
	}puts("");
	system("pause");
	return 0;
}

Python 3コードは以下の通りです.

num = int(input())
A = sorted([int(a) for a in input().split(' ')])
BT = [0 for i in range(num + 1)]
def inOrder( i: int):
    global num,A,BT
    if i <= num:
        inOrder(2 * i)
        BT[i] = A[0];
        A = A[1:]
        inOrder(2 * i + 1)
inOrder(1)
print(' '.join(map(str,BT[1:])))

C言語コードは以下の通りである.
C言語qsortは比較関数を書くので、タイトルの「All the numbers in a line are separated by a space and are no greater than 2000.」に注意してください.すべての要素は[02000]の整数であり、1次元バケツソートでBSTを巡回する問題を解決することができる.

#include
#include
#define FOR(I,S,E) for(int I=(S);I NUM)return;	//     ——>      
	inorder(2 * i);		//     
	BT[i] = pop();		//   ( BST        )
	inorder(2 * i + 1);	//     
}
int main() {
	scanf("%d
", &NUM);
	FOR(i, 0, NUM) {
		int a; scanf("%d", &a);
		push(a);
	}	// Count[a]=m      N    m   a。
	inorder(1);		//             
	printf("%d", BT[1]);	//                  ，        。
	for (size_t i = 2; i <= NUM; i++) {
		printf(" %d", BT[i]);
	}puts("");
	system("pause");
	return 0;
}