POJ 1577 Falling Leaves
发布时间:2020-12-14 05:12:54 所属栏目:大数据 来源:网络整理
导读:Description ? Figure 1 Figure 1 shows a graphical representation of a binary tree of letters. People familiar with binary trees can skip over the definitions of a binary tree of letters,leaves of a binary tree,and a binary search tree of l
Description Figure 1 Figure 1 shows a graphical representation of a binary tree of letters. People familiar with binary trees can skip over the definitions of a binary tree of letters,leaves of a binary tree,and a binary search tree of letters,and go right to The problem.? A binary tree of letters may be one of two things:?
In the graphical representation of a binary tree of letters:?
A leaf in a binary tree is a node whose subtrees are both empty. In the example in Figure 1,this would be the five nodes with data B,D,H,P,and Y.? The preorder traversal of a tree of letters satisfies the defining properties:?
The preorder traversal of the tree in Figure 1 is KGCBDHQMPY.? A tree like the one in Figure 1 is also a binary search tree of letters. A binary search tree of letters is a binary tree of letters in which each node satisfies:? The root‘s data comes later in the alphabet than all the data in the nodes in the left subtree.? The root‘s data comes earlier in the alphabet than all the data in the nodes in the right subtree.? The problem:? Consider the following sequence of operations on a binary search tree of letters? Remove the leaves and list the data removed? Repeat this procedure until the tree is empty? Starting from the tree below on the left,we produce the sequence of trees shown,and then the empty tree? by removing the leaves with data? BDHPY? CM? GQ? K? Your problem is to start with such a sequence of lines of leaves from a binary search tree of letters and output the preorder traversal of the tree. Input
The input will contain one or more data sets. Each data set is a sequence of one or more lines of capital letters.?
The lines contain the leaves removed from a binary search tree in the stages described above. The letters on a line will be listed in increasing alphabetical order. Data sets are separated by a line containing only an asterisk (‘*‘).? The last data set is followed by a line containing only a dollar sign (‘$‘). There are no blanks or empty lines in the input. Output
For each input data set,there is a unique binary search tree that would produce the sequence of leaves. The output is a line containing only the preorder traversal of that tree,with no blanks.
Sample Input BDHPY CM GQ K * AC B $ Sample Output KGCBDHQMPY BAC ? ?棵?叉搜索树,每次揪掉当前所有叶?,作为??输?。 解题思路:
? 输?倒着看。 AC代码:
1 #include<iostream>
2 #include<cstring>
3 #include<algorithm>
4 #include<cstdio>
5 using namespace std; 6 int n; 7 char a[1005]; 8 struct kkk{ 9 int lson,rson;//左儿子、右儿子
10 char qwq;//节点信息
11 }tr[104]; 12 void build(int h,char ch) { 13 if(tr[h].qwq == 0){//根节点
14 tr[h].qwq = ch; 15 return ; 16 } 17 else if(tr[h].qwq > ch) { 18 if(!tr[h].lson) tr[h].lson=n++; 19 build(tr[h].lson,ch); 20 } 21 else if(tr[h].qwq <= ch) { 22 if(!tr[h].rson) tr[h].rson=n++; 23 build(tr[h].rson,ch); 24 } 25 } 26 void ans(int d) {//求先序遍历
27 if(!tr[d].qwq) return ; 28 cout << tr[d].qwq; 29 ans(tr[d].lson); 30 ans(tr[d].rson); 31 } 32 int main() { 33 while(scanf("%s",a)) { 34 char x; n=2; 35 int len = strlen(a); 36 memset(tr,0,sizeof(tr)); 37 while(true) { 38 cin>>x; 39 if(x == ‘*‘||x == ‘$‘) break; 40 a[len++] = x; 41 } 42 for(int i = len-1; i >= 0; i--) build(1,a[i]);//倒着建树
43 ans(1); 44 cout<<endl; 45 if(x == ‘$‘) return 0; 46 } 47 }
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |