Data_Structures/04_1.cpp at master · 1-WEEK/Data_Structures · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <iostream>
#include <cstdio>
using namespace std;

typedef struct treeNode* Tree;
struct treeNode{
    int value;
    Tree left, right;
    bool flag;
};

void resetT(Tree T);
Tree newNode(int v);
Tree CreatTree(int n);
bool judge(Tree T, int n);
bool check(Tree T, int v);
Tree insert(Tree T, int v);

int main()
{
    int n, l, i;
    cin >> n;
    while (n) {
        scanf("%d", &l);
        Tree T = CreatTree(n);
        for (i=0; i<l; ++i) {
            if (judge(T, n)) printf("Yes\n");
            else printf("No\n");
            resetT(T);
        }
        scanf("%d", &n);
    }
    return 0;
}
Tree CreatTree(int n) {
    int i, v;
    Tree T;
    scanf("%d", &v);
    T = newNode(v);
    for (i=1; i<n; ++i) {
        scanf("%d", &v);
        T = insert(T, v);
    }
    return T;
}
Tree insert(Tree T, int v)
{
    if (!T) T = newNode(v);
    else {
        if (v> T->value)
            T->right = insert(T->right, v);
        else
            T->left  = insert(T->left, v);
    }
    return T;
}
Tree newNode(int v)
{
    Tree T = new treeNode;
    T->value = v;
    T->flag = false;
    T->left = T->right = NULL;
    return T;
}
void resetT(Tree T)
{
    if (T->left)  resetT(T->left);
    if (T->right) resetT(T->right);
    T->flag = false;
}
bool check(Tree T, int v)
{
    if (T->flag) {
        if ( v < T->value )
            return check(T->left, v);
        else if ( v > T->value )
            return check(T->right, v);
        else
            return false;
    }
    else {
        if ( v==T->value ) {
            T->flag = true;
            return true;
        }
        else
            return false;
    }
}
bool judge(Tree T, int n)
{
    int i, v;
    bool flag = false;
    scanf("%d", &v);
    if (v!=T->value)
        flag = true;
    else
        T->flag = true;
    for (i=1; i<n; ++i) {
        scanf("%d", &v);
        if (!flag && !check(T, v))
            flag = true;
    }
    if (flag)
        return false;
    else
        return true;
}