題目

是對(duì)于輸入的各種插入序列，你需要判斷它們是否能生成一樣的二叉搜索樹(shù)。

輸入格式:

輸入包含若干組測(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)單起見(jiàn)，我們保證每個(gè)插入序列都是1到N的一個(gè)排列。當(dāng)讀到N為0時(shí)，標(biāo)志輸入結(jié)束，這組數(shù)據(jù)不要處理。

輸出格式:

對(duì)每一組需要檢查的序列，如果其生成的二叉搜索樹(shù)跟對(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

幾種方法

分別建兩棵搜索樹(shù)的判別方法
根據(jù)兩個(gè)序列分別建樹(shù)，再判別樹(shù)是否一樣

不建樹(shù)的判別方法

3124 vs 3412
根結(jié)點(diǎn)都是3
{1 2} 3 {4} vs {1 2} 3 {4}
一樣

3124 vs 3241
根結(jié)點(diǎn)都是3
{1 2} 3 {4} vs {2 1} 3 {4}
不一樣

建一棵樹(shù)，再判別其他序列是否與該樹(shù)一致（本文采取該方法）

求解思路

搜索樹(shù)表示

建搜索樹(shù)T

判別一序列是否與搜索樹(shù)T一致

搜索樹(shù)表示

用鏈表表示

typedef struct TreeNode *Tree; struct TreeNode{int v; //結(jié)點(diǎn)信息Tree Left,Right; //兩個(gè)指針int flag; //有沒(méi)有被訪問(wèn)過(guò)的標(biāo)記 };

程序框架搭建

int main() { int N, L, i;Tree T;//讀入N和Lscanf("%d", &N);while (N) {scanf("%d", &L);//根據(jù)第一行序列建樹(shù)TT = MakeTree(N);for (i=0; i<L; i++) {//依據(jù)樹(shù)T分別判別后面的L個(gè)序列是否能與T形成同一搜索樹(shù)并輸出結(jié)果if (Judge(T, N))printf("Yes\n");else printf("No\n");ResetT(T); //清除T中的標(biāo)記flag}FreeTree(T);scanf("%d", &N);}return 0; }

如何建搜索樹(shù)

Tree MakeTree( int N ) { Tree T;int i, V;scanf("%d", &V);T = NewNode(V); //構(gòu)造第一個(gè)結(jié)點(diǎn)for (i=1; i<N; i++) { //讀入N-1個(gè)元素，插入T里面scanf("%d", &V);T = Insert(T, V); //不斷插入結(jié)點(diǎn)}return T; } //新建一個(gè)結(jié)點(diǎn) Tree NewNode( int V ) { Tree T = (Tree)malloc(sizeof(struct TreeNode));T->v = V; //v設(shè)為傳進(jìn)來(lái)的值T->Left = T->Right = NULL; //左右孩子設(shè)為0T->flag = 0; //flag設(shè)為0return T; } //遞歸插入結(jié)點(diǎn) Tree Insert( Tree T, int V ) {if ( !T ) //T如果為空，插入第一個(gè)結(jié)點(diǎn)T = NewNode(V);else {if ( V>T->v ) //要插入的數(shù)比第一個(gè)結(jié)點(diǎn)大，插在右邊T->Right = Insert( T->Right, V );else //否則插在左邊T->Left = Insert( T->Left, V );}return T; }

如何判別

如何判別序列3 2 4 1是否 與樹(shù)T一致？

方法：在樹(shù)T中按順序搜索序列3 2 4 1中的每個(gè)數(shù)
如果每次搜索所經(jīng)過(guò)的結(jié)點(diǎn)在前面均出現(xiàn)過(guò)，則一致
否則（某次搜索中遇到前面未出現(xiàn)的結(jié)點(diǎn)），則不一致

查找序列中的數(shù)在樹(shù)中的位置，如果在查找過(guò)程中發(fā)現(xiàn)某個(gè)數(shù)以前沒(méi)有碰到過(guò)，就是不一致。例如上圖中T是3142，要判斷序列3241，序列第一個(gè)數(shù)3在T中的根結(jié)點(diǎn)找到，flag標(biāo)記為1，序列第二個(gè)數(shù)2在T中要經(jīng)過(guò)3-1-2找到，3之前碰到過(guò)，而1之前沒(méi)碰到過(guò)（flag=0）。所以不一致。

//判別方法：在T中搜索序列中的每一個(gè)整數(shù) int check ( Tree T, int V ) {if ( T->flag ) { //這個(gè)結(jié)點(diǎn)訪問(wèn)過(guò)了if ( V<T->v ) return check(T->Left, V); //往左孩子找else if ( V>T->v ) return check(T->Right, V); //往右孩子找else return 0; //序列里面重復(fù)了，認(rèn)為不一致}else { //沒(méi)被訪問(wèn)過(guò)if ( V==T->v ) { //剛好是要訪問(wèn)的結(jié)點(diǎn)T->flag = 1; //flag設(shè)為1return 1;}else return 0; //碰到了以前沒(méi)見(jiàn)過(guò)的結(jié)點(diǎn)} } //程序的flag和結(jié)點(diǎn)的flag要區(qū)分 int Judge( Tree T, int N ) {int i, V, flag = 0; /* flag: 0代表目前還一致，1代表已經(jīng)不一致*/scanf("%d", &V);if ( V!=T->v ) flag = 1; //發(fā)現(xiàn)不一致else T->flag = 1;for (i=1; i<N; i++) {scanf("%d", &V);if ( (!flag) && (!check(T, V)) ) //不一致時(shí)不用check，但要把數(shù)讀完flag = 1;}if (flag) return 0; //前面發(fā)現(xiàn)過(guò)不一致else return 1; //一致 } void ResetT ( Tree T ) /* 清除T中各結(jié)點(diǎn)的flag標(biāo)記 */ {if (T->Left) ResetT(T->Left); //左子樹(shù)清零if (T->Right) ResetT(T->Right); //右子樹(shù)清零T->flag = 0; //flag清零 } void FreeTree ( Tree T ) /* 釋放T的空間 */ {if (T->Left) FreeTree(T->Left); //釋放左子樹(shù)if (T->Right) FreeTree(T->Right); //釋放右子樹(shù)free(T); //釋放結(jié)點(diǎn) }

提交結(jié)果

總結(jié)

以上是生活随笔為你收集整理的是否同一棵二叉搜索树（c语言实现）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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