【POJ No. 1577 / UVA No. 1525】落叶 Falling Leaves

【POJ No. 1577 / UVA No. 1525】落叶 Falling Leaves

POJ题目地址

【题意】

一棵字母二叉树如下图所示。

一棵字母二叉树可以是两者之一：

• ①空树；
• ②有一个根节点，每个节点都以一个字母作为数据，并且有指向左子树和右子树的指针，左右子树也是字母二叉树。

二叉树的树叶是一个左右子树都为空的节点。在上图的实例中有5个树叶节点，分别为B、D、H、P和Y。

字母二叉搜索树是每个节点满足下述条件的字母二叉树：

① 按字母序，根节点的数据在左子树的所有节点的数据之后；

② 根节点的数据在右子树的所有节点的数据之前。

在一棵字母二叉搜索树上删除树叶，并将被删除的树叶列出；重复这一过程，直到树为空。例如，从左边的树开始，产生树的序列如下图所示，最后产生空树。

删除的树叶序列如下：

BDHPY
CM
GQ
K
1
2
3
4

给定一个字母二叉搜索树的树叶删除序列，输出树的先序遍历。

【输入输出】

输入：

输入包含多个测试用例。每个测试用例都是一行或多行大写字母序列，每行都给出按上述描述步骤从二叉搜索树中删除的树叶，每行给出的字母都按字母升序排列。在测试用例之间以一行分隔，该行仅包含一个星号“*”。在最后一个测试用例后给出一行，该行仅给出一个符号“$”。在输入中没有空格或空行。

输出：

对于每个测试用例，都有唯一的二叉搜索树，单行输出该树的先序遍历。

【样例】

【算法设计】

由题目可知，最后一个字母一定为树根，先输入的字母在树的深层，可以逆序建树。读入字母序列后用字符串存储，然后逆序创建二叉搜索树，将小的字母插入左子树中，将大的字母插入右子树中。输出该树的先序遍历序列：根、左子树、右子树。

【算法实现】

#include
#include
#include

using namespace std;

struct data{
	
	int l , r;
	char c;
}tree[110];

int cnt = 1;

void insert(int t , char ch){
	
	if(!tree[t].c){
		tree[t].c = ch;
		return;
	}
	
	if(ch < tree[t].c){
		
		if(!tree[t].l){
			tree[++cnt].c = ch;
			tree[t].l = cnt;
		}
		else{
			insert(tree[t].l , ch);
		}
	}
	if(ch > tree[t].c){
		
		if(!tree[t].r){
			tree[++cnt].c = ch;
			tree[t].r = cnt;
		}
		else{
			insert(tree[t].r , ch);
		}
	}
}

void preorder(int t){
	
	if(!tree[t].c){
		
		return;
	}
	cout << tree[t].c;
	preorder(tree[t].l);
	preorder(tree[t].r);
}

int main(){
	
	string s1 , s;
	while(1){
		
		s = "";
		memset(tree , 0 ,sizeof(tree));
		while(cin >> s1 && s1[0] != '*' && s1[0] != '$'){
			
			s += s1;
		}
		
		for(int i = s.length() - 1; i >= 0 ; i --){
			
			insert(1, s[i]);
		}
		preorder(1);
		
		cout << endl;
		if(s1[0] == '$'){
			
			break;
		}
	}
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80