7-2 是否同一棵二叉搜索树

7-2 是否同一棵二叉搜索树

给定一个插入序列就可以唯一确定一棵二叉搜索树。然而，一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{2, 1, 3}和{2, 3, 1}插入初始为空的二叉搜索树，都得到一样的结果。于是对于输入的各种插入序列，你需要判断它们是否能生成一样的二叉搜索树。

#include #include #include #include #include using namespace std;struct Node { int val; Node *left; Node *right; Node() { val = 0; left = right = NULL; }};struct BST { Node *root; int cnt, inorder[15]; void init() { root = new Node; cnt = 0; } void insert(int x) { Node *t = root, *fa = root; while (t != NULL) { fa = t; //cout << (t->val) << endl; if (x <= (t->val)) t = (t->left); else t = (t->right); }// cout << "test" << endl; t = new Node; if (x <= fa->val) fa->left = t; else fa->right = t; t->val = x; } void solve(Node *t) { if (t == NULL) return; inorder[++cnt] = (t->val); //cout << inorder[cnt] << endl; solve(t->left); solve(t->right); }}bst, temp;int main() { int n, m, t; while (~scanf("%d", &n) && n) { scanf("%d", &m); bst.init(); for (int i = 1; i <= n; i++) { scanf("%d", &t); bst.insert(t); } bst.solve(bst.root); // for (int i = 2; i <= n + 1; i++) { // cout << bst.inorder[i] << "/"; // } // cout << endl; for (int i = 1; i <= m; i++) { temp.init(); for (int j = 1; j <= n; j++) { scanf("%d", &t); temp.insert(t); } temp.solve(temp.root); // for (int j = 2; j <= n + 1; j++) cout << temp.inorder[j] << "/"; // cout << endl; bool ok = true; for (int j = 2; j <= n + 1; j++) if (bst.inorder[j] != temp.inorder[j]) { ok = false; break; } if (ok) printf("Yes\n"); else printf("No\n"); } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。