是否同一棵二叉搜索樹

1.題目描述：

給定一個(gè)插入序列就可以唯一確定一棵二叉搜索樹。然而，一棵給定的二叉搜索樹卻可以由多種不同的插入序列得到。例如分別按照序列{2, 1, 3}和{2, 3, 1}插入初始為空的二叉搜索樹，都得到一樣的結(jié)果。于是對(duì)于輸入的各種插入序列，你需要判斷它們是否能生成一樣的二叉搜索樹。

輸入格式:
輸入包含若干組測(cè)試數(shù)據(jù)。每組數(shù)據(jù)的第1行給出兩個(gè)正整數(shù)N (≤10)和L，分別是每個(gè)序列插入元素的個(gè)數(shù)和需要檢查的序列個(gè)數(shù)。第2行給出N個(gè)以空格分隔的正整數(shù)，作為初始插入序列。最后L行，每行給出N個(gè)插入的元素，屬于L個(gè)需要檢查的序列。

簡(jiǎn)單起見，我們保證每個(gè)插入序列都是1到N的一個(gè)排列。當(dāng)讀到N為0時(shí)，標(biāo)志輸入結(jié)束，這組數(shù)據(jù)不要處理。

輸出格式:
對(duì)每一組需要檢查的序列，如果其生成的二叉搜索樹跟對(duì)應(yīng)的初始序列生成的一樣，輸出“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

2.思路分析

//輸入數(shù)據(jù)的分析：給出 數(shù)據(jù)個(gè)數(shù) 還有幾行數(shù)據(jù)。 然后第一行是標(biāo)準(zhǔn)數(shù)據(jù) 接下來 L 行是與其做對(duì)比的 是否構(gòu)成 二叉搜索樹
//操作：建立二叉搜索樹 用中序遍歷 輸出的序列是 遞增序列。
//判斷是否為 同一顆 二叉搜索樹 1.0 版本為 將其 葉節(jié)點(diǎn)值相加 如果相等 則是（驗(yàn)證結(jié)果為失敗）
// 2.0 版本 用先序遍歷輸出的值如果都相等 則 可以證明 其 為相同的 二叉搜索樹。

3.上碼

```cpp 在這里插入代碼片//輸入數(shù)據(jù)的分析：給出 數(shù)據(jù)個(gè)數(shù) 還有 幾行數(shù)據(jù) 然后第一行是標(biāo)準(zhǔn)數(shù)據(jù) 接下來 L 行是與其做對(duì)比的 是否構(gòu)成 二叉搜索樹 //思路：根據(jù)標(biāo)準(zhǔn)數(shù)據(jù)建立二叉搜索樹，然后根據(jù)輸入的數(shù)據(jù)也建立 二叉搜索樹 然后比較 葉節(jié)點(diǎn)的 值 是否 相等 如果不相等 則輸出 NO, 相等則輸出 YES //操作：建立二叉搜索樹 用中序遍歷 輸出的序列是 遞增序列。 //判斷是否為 同一顆 二叉搜索樹 1.0 版本為 將其 葉節(jié)點(diǎn)值相加 如果相等 則是（驗(yàn)證結(jié)果為失敗） // 2.0 版本 用先序遍歷輸出的值如果都相等 則 可以證明 其 為相同的 二叉搜索樹。 #include<bits/stdc++.h> using namespace std; int N,flag; typedef struct TNode *Ptrtree; typedef struct TNode{int Data;Ptrtree left;Ptrtree right; }tnode; //開辟一個(gè)結(jié)點(diǎn)空間 Ptrtree creatNode(){Ptrtree node = new TNode;node->left = NULL;node->right = NULL;return node; } //建立二叉搜索樹 Ptrtree insert(Ptrtree root,int x){if(root == NULL){//將插入的操作視為 查找的時(shí)的操作,插入的地點(diǎn)視為 查找失敗的地點(diǎn) 在查找失敗的地點(diǎn) 插入一個(gè)結(jié)點(diǎn)root = (Ptrtree)malloc(sizeof(struct TNode));root->left = NULL;root->right = NULL;root->Data = x;return root;}if(root->Data > x){root->left = insert(root->left,x);}else if(root->Data < x){root->right = insert(root->right,x);}else{return NULL;}return root; }Ptrtree creatTree(int A[],Ptrtree root){root = NULL;int i;for(i = 0; i < N; i++){root = insert(root,A[i]);}return root; } //求取一顆二叉搜索樹的根節(jié)點(diǎn) int Rootnode(Ptrtree root){if(root == NULL){return 0;}if(root->left == NULL && root->right == NULL){ //如果 一個(gè)結(jié)點(diǎn)的左右結(jié)點(diǎn)都為 空 則說明其為葉節(jié)點(diǎn) return root->Data; //將其的值 返回到遞歸那部分 }return Rootnode(root->left) + Rootnode(root->right); //將其 根節(jié)點(diǎn) 之和求出來 } // 先序遍歷驗(yàn)證建立 二叉搜索樹 是否正確。 void Preliminary(Ptrtree root1,Ptrtree root2){if(root1 && root2){//防止遞歸遍歷到 其中一個(gè) 樹是空。、if(root1->Data != root2->Data) flag = 0;Preliminary(root1->left,root2->left);Preliminary(root1->right,root2->right); } }int main(){int i,j,L,a1[100];cin>>N>>L;// Ptrtree root; // root = creatTree(a1,root);//cout<<temp<<endl;//先把標(biāo)準(zhǔn)建立起來 然后再建立需要比較的 不是同一個(gè) 就輸出 NO；while(N!=0){//輸入 標(biāo)準(zhǔn)的 二叉搜索樹for(i = 0; i < N; i++)cin>>a1[i];Ptrtree root;root = creatTree(a1,root); for(i = 0; i < L; i++ ){int a2[10]={0};for(j = 0; j < N; j++){cin>>a2[j];}Ptrtree root2;root2 = creatTree(a2,root2);flag = 1;Preliminary(root,root2);if(flag == 1)cout<<"Yes"<<endl;elsecout<<"No"<<endl; }cin>>N>>L;} } ## 4。踩的坑PTA上的第一個(gè)點(diǎn) 一直過不去 很無腦 ，原來是 題目 沒有看仔細(xì) 人家讓 的是多次輸入 直到 N的輸入為0 為止 才結(jié)束。 加油 陌生人。(sample 換順序。 //有Yes，有No：根不同，子樹根不同。 //樹有單邊、有雙子樹 // 這個(gè)問題是 要多次輸入 ) 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的7-4 是否同一棵二叉搜索树 (25 分)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。