TIOJ 1204 樹狀的堆積結構 [Cartesian Tree]

4    75128    poao899    456K    156MS    G++     0.86K     2010-04-10 16:01:38                                  .

第一次寫笛卡兒樹

其實比想像好寫(?



//****************************************

#include<stdio.h>
int top, n, cnt;
struct node{
	node *lch, *rch;
	int val;
}N[10020], *st[10020];
void dfs(node *now){
	if(now==NULL)return;
	printf("%d%c", now->val, ++cnt==n? '\n': ' ');
	dfs(now->lch);
	dfs(now->rch);
}
int main(){
	N[0].val= -1;
	while(~scanf("%d", &n)){
		if(!n) break;
		cnt= 0;
		top= 0; N[0].lch= N[0].rch= NULL;
		for(int i=1; i<=n; i++){
			scanf("%d", &N[i].val);
			N[i].lch= N[i].rch= NULL;
		}
		st[top]= N;
		for(int i=1; i<=n; i++){
			while(top> -1&& st[top]->val>N[i].val){
				N[i].lch= st[top];
				--top;
			}
			st[top]->rch= &N[i];
			st[++top]= &N[i];
		}
		dfs(N[0].rch);
	}
}