求求大佬幫忙看看代碼，小白沒有辦法了。
題目描述：
給定一個插入序列就可以唯一確定一棵二叉搜索樹。然而，一棵給定的二叉搜索樹卻可以由多種不同的插入序列得到。例如分別按照序列{2, 1, 3}和{2, 3, 1}插入初始為空的二叉搜索樹，都得到一樣的結果。于是對于輸入的各種插入序列，你需要判斷它們是否能生成一樣的二叉搜索樹。
輸入格式:
輸入包含若干組測驗資料。每組資料的第1行給出兩個正整數N (≤10)和L，分別是每個序列插入元素的個數和需要檢查的序列個數。第2行給出N個以空格分隔的正整數，作為初始插入序列。最后L行，每行給出N個插入的元素，屬于L個需要檢查的序列。
簡單起見，我們保證每個插入序列都是1到N的一個排列。當讀到N為0時，標志輸入結束，這組資料不要處理。
輸出格式:
對每一組需要檢查的序列，如果其生成的二叉搜索樹跟對應的初始序列生成的一樣，輸出“Yes”，否則輸出“No”。
輸入樣例：
4 2
3 1 4 2
3 4 1 2
3 2 4 1
2 1
2 1
1 2
0
輸出樣例：
Yes
No
No
我的想法：首先建好一棵樹，剩下的樹按照層序遍歷，遍歷結果均為一個字串，將遍歷后的結果進行比較
提交結果：
我的代碼：
#include <iostream>
#include <string>
#include <queue>
#include <stack>
using namespace std;
struct node {
string data;
node* left;
node* right;
node(string x) {
data = x;
left = nullptr;
right = nullptr;
}
};
class BST {
protected:
node* root;
node* rinsert(string x, node* r) {
if (r == nullptr) {
r = new node(x);
}
else {
if (x < r->data) {
r->left = rinsert(x, r->left);
}
else if (x > r->data) {
r->right = rinsert(x, r->right);
}
}
return r;
}
public:
BST() {
root = nullptr;
}
node* insert(string x) {
root=rinsert(x, root);
return root;
}
string ltraverse() {
queue<node*>q;
node* temp = root;
string result;
q.push(temp);
while (!q.empty()) {
temp = q.front();
q.pop();
result += temp->data;
if (temp->left != nullptr)q.push(temp->left);
if (temp->right != nullptr)q.push(temp->right);
}
return result;
}
/*string pretraverse() {
stack<node*>s;
string result;
node* temp = root;
while (temp) {
result += temp->data;
s.push(temp);
temp = temp->left;
while (temp == nullptr && !s.empty()) {
temp = s.top();
s.pop();
temp = temp->right;
}
}
return result;
}*/
};
int main()
{
int N, L, i, j;
string result1, result2, temp;
cin >> N;
BST b1,* pb = nullptr;
while (N != 0) {
cin >> L;
for (i = 0; i < N; i++) {
cin >> temp;
b1.insert(temp);
}
result1 = b1.ltraverse();
for (j = 0; j < L; j++) {
pb = new BST();
for (i = 0; i < N; i++) {
cin >> temp;
(*pb).insert(temp);
}
result2 = (*pb).ltraverse();
if (result1 == result2)cout << "Yes" << endl;
else cout << "No" << endl;
delete pb;
}
cin >> N;
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/93127.html
標籤：C++ 語言