HDu 3791二叉探索ツリー(BSTの確立)


http://acm.hdu.edu.cn/showproblem.php?pid=3791
題意:標準列をあげます.この列は二叉検索ツリーを構成することができます.それからn個の比較列です.この二つの列が同じ二叉検索ツリーを構成できるかどうかを聞いてください.
構想:二叉探索ツリーの定義をよく理解し、1つの列は二叉探索ツリーを記述することができるが、1つの二叉探索ツリーは通常1つの表現方法だけではない.二叉探索ツリーは、通常、挿入されたノードと現在のルートを比較して挿入位置を判断するが、挿入された左は右の配列に影響を及ぼさないため、シーケンス総数は左ノードと右ノードの配列の組み合わせである.
1つの文字列の各文字の挿入操作によって1本のツリーを構成し、そのツリーを前順に遍歴して遍歴シーケンスを導出し、最後にこのシーケンスを比較すればよい.
注意すべきは2つあります.1つは構造体が混ざりやすいことです.これを見てみると、構造体のポインタに少し慣れていません.ポインタは付与されてから使用できます.
もう1つは挿入操作で、空の場合は新しいノードを作成し、空の場合は左右のサブツリーを拡張し、ルートを処理しないことに注意します.
やはりよく知っていなければなりません.
#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;
const int N = 12;

typedef struct Tree
{
    Tree *left;
    Tree *right;
    int val;
}Tree;

Tree *root;
int stand[N], cmp[N], cnt, len;

Tree *creat(int num)
{
    Tree *node = (Tree*)malloc(sizeof(Tree));
    node->left = NULL;
    node->right = NULL;
    node->val = num;
    return node;
}

Tree *insertt(Tree *node, int num)
{
    if(node == NULL)
    {
        node = creat(num);
    }
    else
    {
        if(num < node->val) node->left = insertt(node->left, num);
        else if (num > node->val) node->right = insertt(node->right, num);
    }
    return node;
}

void preorder(Tree *posttree)
{
    if(posttree != NULL)
    {
        cmp[cnt++] = posttree->val;
        preorder(posttree->left);
        preorder(posttree->right);
    }
}

void build(char *s)
{
    root = NULL;
    len = strlen(s);
    cnt = 0;
    for(int i = 0; i < len; i++)
    {
        int num = s[i]-'0';
        root = insertt(root, num);
    }
}

int main()
{
   // freopen("in.txt", "r", stdin);
    int n;
    char s[N];
    while(~scanf("%d", &n))
    {
        if(n == 0) break;
        scanf("%s", s);
        build(s);
        preorder(root);
        memcpy(stand, cmp, sizeof(cmp));
        while(n--)
        {
            scanf("%s", s);
            build(s);
            preorder(root);
            bool ans = true;
            for(int i = 0; i < len; i++)
            {
                if(stand[i] != cmp[i])
                {
                    ans = false;
                    break;
                }
            }
            if(ans) printf("YES
"); else printf("NO
"); } } }