HDU 3179 二叉搜索树（树的建立）

二叉搜索树

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 6293 Accepted Submission(s): 2820

Problem Description

判断两序列是否为同一二叉搜索树序列

Input

开始一个数n，(1<=n<=20) 表示有n个需要判断，n= 0 的时候输入结束。
接下去一行是一个序列，序列长度小于10，包含(0~9)的数字，没有重复数字，根据这个序列可以构造出一颗二叉搜索树。
接下去的n行有n个序列，每个序列格式跟第一个序列一样，请判断这两个序列是否能组成同一颗二叉搜索树。

Output

如果序列相同则输出YES，否则输出NO

Sample Input

2 567432 543267 576342 0

Sample Output

YES NO

Source

浙大计算机研究生复试上机考试-2010年

Recommend

notonlysuccess | We have carefully selected several similar problems for you: 3787 3790 3789 3788 1710

我的思路：

建一棵树，上面放有flag，当有其他数组近来匹配时，若经过的节点的flag为0则，不相等，否则，将与该数相等的树的节点的flag设为1。

可以这样建树

struct tree                //声明树的结构
{
    struct tree *left;
    int data;
    struct tree *right;
};

本题代码

  1 #include <iostream>
  2 #include <cstring>
  3 #include <string>
  4 #include <algorithm>
  5 typedef struct treenode *tree;//定义treenode这个结构体是一个指针
  6 struct treenode
  7 {
  8     int v;
  9     tree left, right;//这个结构体指针又含有两个指针
 10     bool f;//用于标记该节点曾经有没有经过
 11 };
 12 using namespace std;
 13 
 14 tree newnode(int x)//新建节点
 15 {
 16     tree t = (tree)malloc(sizeof(treenode));
 17     t->v = x;
 18     t->left = t->right = NULL;
 19     t->f = 0;
 20     return t;//要有返回值
 21 }
 22 
 23 tree insert(tree t,int x)//插入节点
 24 {
 25     if (!t) t = newnode(x);//如果节点为空，建一个节点
 26     else
 27     {
 28         if (x < t->v)
 29         {
 30             t->left = insert(t->left, x);//不能写成t=。。。因为是插入在左边
 31         }
 32         else
 33             t->right = insert(t->right, x);
 34     }
 35     return t;//要有返回值
 36 }
 37 
 38 bool check(tree t, int x)
 39 {
 40     if (!t) return 0;//x在树t中没有出现过
 41     else
 42     {
 43         if (t->v == x)//相等，标记经过该节点
 44         {
 45             t->f = 1;
 46             return 1;
 47         }
 48         else
 49         {
 50             if (t->f == 0) return 0;//经过了一个曾经没经过的节点
 51             else
 52             {
 53                 if (x < t->v)
 54                     return check(t->left, x);
 55                 else
 56                     return check(t->right, x);
 57             }
 58         }
 59     }
 60 }
 61 
 62 void init(tree t)//初始化树上的f
 63 {
 64     if (t)
 65     {
 66         t->f = 0;
 67         init(t->left);
 68         init(t->right);
 69     }
 70 }
 71 
 72 int main()
 73 {
 74     int n;
 75     char a[20];
 76     while (cin >> n && n)
 77     {
 78         tree t = (tree)malloc(sizeof(treenode));//开辟空间建第一个节点
 79         cin >> a;
 80         int l = strlen(a);
 81         t->v = a[0]-'0';
 82         t->left = t->right = NULL;
 83         int i;
 84         for (i = 1; i < l; i++)
 85         {
 86             int x = a[i] - '0';
 87             t = insert(t,x);//插入节点；
 88         }
 89         while (n--)
 90         {
 91             cin >> a;
 92             bool f = 1;
 93             for (i = 0; i < l; i++)
 94             {
 95                 int x = a[i] - '0';
 96                 f = check(t, x);//进入树t检查
 97                 if (!f) break;
 98             }
 99             if (!f) cout << "NO" << endl;
100             else cout << "YES" << endl;
101             init(t);//把树上的f重新设为0
102         }
103         free(t);//释放树
104     }
105     return 0;
106 }