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