04-树4 是否同一棵二叉搜索树(25 分)

题目

题目链接

分析

为二叉树结构添加一个flag字段,表示搜索过程中是否走过,初始化为false

根据第一个输入样例建立二叉树,设置一个全局的Isflag,根据后面的样例搜索。

  1. 如果在搜索二叉树里没有找到符合的结点,则一定不能构成同样的二叉树。
  2. 如果在搜索过程中经过flagfalse的结点,表示出错,不能构成同一棵搜索二叉树。
  3. 搜索到结点后,将flag字段置为true,表示已走过这个结点。

AC代码

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
#include "bits/stdc++.h"
using namespace std;
typedef struct TreeNode
{
int data;
bool flag;
TreeNode* left;
TreeNode* right;
TreeNode(int d) {
data = d;
flag = false;
left = right = NULL;
}
}*tree;
void insertNode(tree& root, int x) {
if (root == NULL) {
root = new TreeNode(x);
}
else {
if (x > root->data)
insertNode(root->right, x);
else
insertNode(root->left, x);
}
}
//标记一个全局的判断位,只要有一个节点不正确,就输出false
bool isFlag = true;
//经过的结点都应该是之前已走过的
void findNode(tree root, int x) {
//如果节点为空,那肯定不是同一棵树
if (root == NULL) {
isFlag = false;
return;
}
//走到这个结点,标记已经走过
if (root->data == x) {
root->flag = true;
return ;
}
//走过的结点必须是已走过的
if (root->flag == false) {
isFlag = false;
return;
}
//递归查找
if(root->data < x) {
findNode(root->right, x);
}
else {
findNode(root->left, x);
}
}
//清楚二叉搜索树的Flag标记
void clearTree(tree root) {
if (root == NULL) return;
root->flag = false;//未走过
clearTree(root->left);
clearTree(root->right);
}
int main() {
int n, m, i, j, t;
while (cin >> n && n) {
tree head = NULL;
cin >> m;
for (i = 0; i < n; i++) {
cin >> t;
insertNode(head, t);
}
while (m--) {
for (i = 0; i < n; i++) {
cin >> t;
findNode(head, t);
}
if (isFlag)
cout << "Yes\n";
else
cout << "No\n";
isFlag = true;
clearTree(head);
}
}
return 0;
}

本文标题:04-树4 是否同一棵二叉搜索树(25 分)

文章作者:admin

发布时间:2017年10月16日 - 17:10

最后更新:2017年10月16日 - 17:10

原始链接:https://kxp555.coding.me/2017/10/16/PAT3/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。