http://poj.org/problem?id=1577
【题意】
有一颗二叉搜索树，每次操作都把二叉搜索树的叶子从左到右揪掉（露出来的父节点就变成了新的叶子结点）
先给出了揪掉的叶子序列（多个字符串）
给出这课二叉搜索树先序遍历的结果
【思路】
最后揪掉的肯定是根，最后揪掉的是最先插入的，倒着建立二叉搜索树就可以。
【AC】
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue> using namespace std;
struct node{
int num;
node *lef;
node *rig;
};
const int maxn=1e3+;
string str[maxn];
int cur; node *work(){
node *rt=(node *)malloc(sizeof(node));
rt->num=str[cur-][]-'A';
rt->lef=NULL;
rt->rig=NULL;
for(int i=cur-;i>=;i--){
int len=str[i].length();
for(int j=;j<len;j++){
node *now=rt;
while(){
if(str[i][j]-'A'<now->num){
if(now->lef) now=now->lef;
else{
node *nd=(node *)malloc(sizeof(node));
nd->num=str[i][j]-'A';
nd->lef=NULL;
nd->rig=NULL;
now->lef=nd;
break;
}
}else{
if(now->rig) now=now->rig;
else{
node *nd=(node *)malloc(sizeof(node));
nd->num=str[i][j]-'A';
nd->lef=NULL;
nd->rig=NULL;
now->rig=nd;
break;
}
}
}
}
}
return rt;
}
void preorder(node *rt){
if(rt==NULL) return;
printf("%c",rt->num+'A');
preorder(rt->lef);
preorder(rt->rig);
free(rt);
}
int main(){
cur=;
while(cin>>str[cur]){
if(str[cur][]=='*'||str[cur][]=='$'){
node *rt=work();
preorder(rt);
puts("");
if(str[cur][]=='$') break;
else cur=;
}else{
cur++;
}
}
return ;
}