中国大学MOOC-陈越、何钦铭-数据结构-2018秋 04-树4 是否同一棵二叉搜索树 （25 分）

#include "pch.h"
#include <iostream>

using namespace std;

typedef class TreeNode * Tree;
class TreeNode {
public:
	int value;
	Tree left, right;
	int flag;
};

Tree MakeTree(int N);
Tree Insert(Tree tree, int value);
Tree NewNode(int value);
int Check(Tree tree, int value);
int Judge(Tree tree, int N);
void Reset(Tree tree);
void FreeTree(Tree tree);
int main() {

	int N, L, i;
	Tree tree;

	cin >> N;
	while (N) {

		cin >> L;

		tree = MakeTree(N);

		for (i = 0; i < L; i++) {

			if (Judge(tree, N)) cout << "Yes" << endl;
			else cout << "No" << endl;

			Reset(tree);

		}

		FreeTree(tree);

		cin >> N;
	}

	return 0;

}

Tree MakeTree(int N)
{
	Tree root;
	int i, value;

	cin >> value;
	root = NewNode(value);

	for (i = 1; i < N; i++) {

		cin >> value;
		root = Insert(root, value);

	}

	return root;
}

Tree Insert(Tree tree, int v)
{
	if (!tree) tree = NewNode(v);
	else {
		if (v > tree->value) tree->right = Insert(tree->right, v);
		else tree->left = Insert(tree->left, v);
	}

	return tree;
}

Tree NewNode(int v)
{
	Tree root = new TreeNode;

	root->value = v;
	root->left = root->right = NULL;
	root->flag = 0;

	return root;
}

int Check(Tree tree, int v)
{
	if (tree->flag) {
		if (v < tree->value) return Check(tree->left, v);
		else if (v > tree->value) return Check(tree->right, v);
		else return 0;
	}
	else {
		if (v == tree->value) {
			tree->flag = 1;
			return 1;
		}
		else return 0;
	}
}

int Judge(Tree tree, int N)
{
	int i, v, flag = 0;//0代表目前还一致，1代表已经出现了不一致

	cin >> v;

	if (v != tree->value) flag = 1;
	else tree->flag = 1;

	for (i = 1; i < N; i++) {

		cin >> v;
		if ((!flag) && (!Check(tree, v))) flag = 1;

	}

	if (flag) return 0;
	else return 1;
}

void Reset(Tree tree)
{
	if (tree->left) Reset(tree->left);
	if (tree->right) Reset(tree->right);

	tree->flag = 0;
}

void FreeTree(Tree tree)
{
	if (tree->left) FreeTree(tree->left);
	if (tree->right) FreeTree(tree->right);

	delete tree;
}