POJ 1577二叉探索ツリー

2051 ワード

この問題の前でくだらないことをたくさん言った.
二叉探索木を与えたが、葉を削除する順序がおかしい.つまり、木の上の葉の結点を与えて、それからこれらの葉をつかんで、残りの結点の中で葉の結点になったものを与えて、このようにすべての結点がつまみ出されるまで.最後にこの二叉探索ツリーの先順遍歴を要求する
この問題の解決方法は簡単で、彼がくれたものに従って、逆さまに二叉検索ツリーを作ればいいです.
どうしてですか.観察してみると、最後につかんだのはルートノードに違いない.さらに上へ行くと、毎回つかんだノードの間には親子関係がないに違いない.これは明らかだ.すべてのノードが父親のノードより先につまみ出されるのも明らかだ.では、逆順序で二叉探索ツリーを構築する場合、元の二叉探索ツリーと同じです.親子関係のあるノード間の相対的な位置は変化しないからです.
#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; }