A1168 Cartesian Tree (30分)

小根堆+中序 = 层序

1. 原文

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

2. 解析思路

小根堆，根一定是最小的，从[left,right]中取最小值(记录索引index)，即为根值，遍历[left,index-1],[index+1,right]，即可得到树

进行层次遍历

3. 代码

#include<cstdio>
#include<queue>
using namespace std;
struct node{
	int data;
	node *lchild,*rchild;
};
node* init(int x){
	node *root = new node;
	root->data = x;
	root->lchild = root->rchild = NULL;
	return root;
}
int in[40]={};
void create(node* &root,int left,int right){
	if (left>right)
	{
		return;
	}
	int min = 1<<30;
	int idx = 0;
	for (int i = left; i <= right; ++i)
	{
		if (in[i]<min)
		{
			min = in[i];
			idx = i;
		}
	}
	root = init(min);
	create(root->lchild,left,idx-1);
	create(root->rchild,idx+1,right);
}
int key = 0;
void level(node *root){
	queue<node*> q;
	q.push(root);
	while(!q.empty()){
		node *top = q.front();
		q.pop();
		if (key>0)
		{
			printf(" ");
		}
		key++;
		printf("%d",top->data);

		if (top->lchild!=NULL)
		{
			q.push(top->lchild);
		}
		if (top->rchild!=NULL)
		{
			q.push(top->rchild);
		}
	}

}
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&in[i]);
	}
	node *root = NULL;
	create(root,1,n);
	level(root);
	printf("\n");
}