POJ 1577二叉探索ツリー
この問題の前でくだらないことをたくさん言った.
二叉探索木を与えたが、葉を削除する順序がおかしい.つまり、木の上の葉の結点を与えて、それからこれらの葉をつかんで、残りの結点の中で葉の結点になったものを与えて、このようにすべての結点がつまみ出されるまで.最後にこの二叉探索ツリーの先順遍歴を要求する
この問題の解決方法は簡単で、彼がくれたものに従って、逆さまに二叉検索ツリーを作ればいいです.
どうしてですか.観察してみると、最後につかんだのはルートノードに違いない.さらに上へ行くと、毎回つかんだノードの間には親子関係がないに違いない.これは明らかだ.すべてのノードが父親のノードより先につまみ出されるのも明らかだ.では、逆順序で二叉探索ツリーを構築する場合、元の二叉探索ツリーと同じです.親子関係のあるノード間の相対的な位置は変化しないからです.
二叉探索木を与えたが、葉を削除する順序がおかしい.つまり、木の上の葉の結点を与えて、それからこれらの葉をつかんで、残りの結点の中で葉の結点になったものを与えて、このようにすべての結点がつまみ出されるまで.最後にこの二叉探索ツリーの先順遍歴を要求する
この問題の解決方法は簡単で、彼がくれたものに従って、逆さまに二叉検索ツリーを作ればいいです.
どうしてですか.観察してみると、最後につかんだのはルートノードに違いない.さらに上へ行くと、毎回つかんだノードの間には親子関係がないに違いない.これは明らかだ.すべてのノードが父親のノードより先につまみ出されるのも明らかだ.では、逆順序で二叉探索ツリーを構築する場合、元の二叉探索ツリーと同じです.親子関係のあるノード間の相対的な位置は変化しないからです.
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define eps 1e-5
#define MAXN 1111
#define MAXM 55555
#define INF 1000000000
using namespace std;
struct Tree
{
char c;
int lch, rch;
void init()
{
lch = rch = 0;
}
}tree[33];
char s[33][33];
int e;
void add(int u, char c)
{
if(c < tree[u].c)
{
if(!tree[u].lch)
{
tree[e].c = c;
tree[u].lch = e++;
}
else add(tree[u].lch, c);
}
else
{
if(!tree[u].rch)
{
tree[e].c = c;
tree[u].rch = e++;
}
else add(tree[u].rch, c);
}
}
void preorder(int u)
{
printf("%c", tree[u].c);
if(tree[u].lch) preorder(tree[u].lch);
if(tree[u].rch) preorder(tree[u].rch);
}
int main()
{
int cnt = 0;
while(scanf("%s", s[cnt++]) != EOF)
{
if(s[cnt - 1][0] == '*' || s[cnt - 1][0] == '$')
{
e = 0;
for(int i = 0; i < 30; i++) tree[i].init();
int n = cnt - 1;
tree[e++].c = s[n - 1][0];
for(int i = n - 2; i >= 0; i--)
{
int len = strlen(s[i]);
for(int j = 0; j < len; j++)
add(0, s[i][j]);
}
preorder(0);
printf("
");
if(s[cnt - 1][0] == '$') break;
cnt = 0;
}
}
return 0;
}