PAT 1167 Cartesian Tree

1167 Cartesian Tree (30 分)

A Cartesian tree is a binary tree constructed from a sequence of distinct numbers. The tree is heap-ordered, and an inorder traversal returns the original sequence. For example, given the sequence { 8, 15, 3, 4, 1, 5, 12, 10, 18, 6 }, the min-heap Cartesian tree is shown by the figure.

Your job is to output the level-order traversal sequence of the min-heap Cartesian tree.

Input Specification:

Each input file contains one test case. Each case starts from giving a positive integer N (≤30), and then N distinct numbers in the next line, separated by a space. All the numbers are in the range of int.

Output Specification:

For each test case, print in a line the level-order traversal sequence of the min-heap Cartesian tree. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the beginning or the end of the line.

Sample Input:

10
8 15 3 4 1 5 12 10 18 6
           

Sample Output:

1 3 5 8 4 6 15 10 12 18
           

思路：

 给了最小堆的中序，我们发现最小的数肯定为根，如例子中1为根，在1的左侧的四个数中的最小值3为1的左树的根，也就是1的左儿子，我们发现我们可以用递归的思路通过中序得到一颗唯一的二叉树。再通过层次遍历输出，层次遍历采用队列实现。

#include<bits/stdc++.h>
using namespace std;
int z[32];
int lson[32];
int rson[32];
int dep[32];
int q[32];
int work(int l, int r)
{
	if (r < l)return 0;
	int mi = 999999999;
	int id = 0;
	for (int i = l; i <= r; ++i)
	{
		if (z[i] < mi)
		{
			mi = z[i];
			id = i;
		}
	}
	lson[id] = work(l, id - 1);
	rson[id] = work(id + 1, r);
	return id;
}
int main()
{
	int n; cin >> n;
	for (int i = 1; i <= n; ++i)
	{
		cin >> z[i];
	}
	int root = work(1, n);
	int hd = 1;
	int tl = 1;
	q[tl++] = root;
	while (hd < tl)
	{
		if (lson[q[hd]] != 0)q[tl++] = lson[q[hd]];
		if (rson[q[hd]] != 0)q[tl++] = rson[q[hd]];
		cout << z[q[hd]];
		hd++;
		if (hd != tl)
		{
			cout << " ";
		}
	}
}