[C++知识库]PAT是否是同一颗二叉搜索树 C++实现

题目链接 7-4 是否同一棵二叉搜索树 (25 分)

运行结果

运行代码

#include<iostream>
#include<vector>

using namespace std;

//结点
struct Node
{
	int Data;
	Node* Left;
	Node* Right;
};
typedef Node* Position;

class BinTree
{
public:
	BinTree();
	~BinTree();
	Position& GetRoot();
	void Insert(Position& Root, const int& X);
	void Destroy(Position& Root);

private:
	Position Root;
};

BinTree::BinTree() : Root{ nullptr } {}

void BinTree::Destroy(Position& Root)
{
	if (!Root)
		return;
	Destroy(Root->Left);
	Destroy(Root->Right);
	delete Root;
	Root = nullptr;
}

Position& BinTree::GetRoot()
{
	return Root;
}

BinTree::~BinTree()
{
	Destroy(Root);
}

void BinTree::Insert(Position& Root, const int& X)
{
	if (!Root) {
		Root = new Node;
		Root->Data = X;
		Root->Left = nullptr;
		Root->Right = nullptr;
		return;
	}
	if (X > Root->Data)
		Insert(Root->Right, X);
	else if (X < Root->Data)
		Insert(Root->Left, X);

}

bool IsSameTree(Position T1Root, Position T2Root)
{
	if (!T1Root && !T2Root)
		return true;
	if (T1Root && T2Root)
		if (T1Root->Data != T2Root->Data)
			return false;
		else 
			return IsSameTree(T1Root->Left, T2Root->Left) && IsSameTree(T1Root->Right, T2Root->Right);
	else
		return false;
}

int main()
{
	int N, L;
	vector<bool> IsSame{};
	while (cin >> N) {
		if (N != 0) {
			cin >> L;
			int X;
			BinTree T1;
			for (int i = 0; i < N; ++i) {
				cin >> X;
				T1.Insert(T1.GetRoot(), X);
			}
			for (int i = 0; i < L; ++i) {
				BinTree T2;
				for (int j = 0; j < N; ++j) {
					cin >> X;
					T2.Insert(T2.GetRoot(), X);
				}
				IsSame.push_back(IsSameTree(T1.GetRoot(), T2.GetRoot()));
			}
		}
		else
			break;
	}
	for (int i = 0; i < IsSame.size() - 1; ++i) {
		if (IsSame[i])
			cout << "Yes" << endl;
		else
			cout << "No" << endl;
	}
	if (IsSame.back())
		cout << "Yes";
	else
		cout << "No";
	return 0;
}