題目描述

對應給定的一個序列可以唯一確定一棵二叉排序樹。然而，一棵給定的二叉排序樹卻可以由多種不同的序列得到。例如分別按照序列{3,1,4}和{3,4,1}插入初始為空的二叉排序樹，都得到一樣的結果。你的任務書對于輸入的各種序列，判斷它們是否能生成一樣的二叉排序樹。

輸入

輸入包含若干組測試數據。每組數據的第1行給出兩個正整數N (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 <stdio.h> #include<stdlib.h> #include<string.h> using namespace std; typedef int status; typedef struct BNode {int data;BNode *lchild,*rchild; }*BiTree; status Search(BiTree &T,int key,BiTree f,BiTree &p)//二叉排序樹的查找； //p指向數據元素的結點，f指向雙親的結點； {if(!T){p=f;//樹為空，則數據元素指向雙親結點，return 0;}else if(key==T->data){p=T;return 1;}else if(key<T->data)return Search(T->lchild,key,T,p);//查找樹的左子樹elsereturn Search(T->rchild,key,T,p);//查找樹的右字樹； } status Insert(BiTree &T,int key)//二叉排序樹元素的插入； {BiTree p,s;if(!Search(T,key,NULL,p)){s=new BNode;s->data=key;//插入的結點一定是樹的葉子結點;s->lchild=s->rchild=NULL;if(!p)T=s;//第一個結點（根結點）；else if(key<p->data)T/p->lchild=s;elseT/p->rchild=s;return 1;}return 0; } int judge(BiTree &T,BiTree &T1)//判斷是否為同一顆二叉排序樹； {if(!T&&!T1)return 1;if(T&&T1)if(T->data==T1->data)if(judge(T->lchild,T1->lchild)&&judge(T->rchild,T1->rchild))return 1;return 0; } int main() {int n,num;BiTree T,T1;while(~scanf("%d",&n)&&n){int m;scanf("%d",&m);T=NULL;//對樹初始化處理；for(int i=0;i<n;i++){scanf("%d",&num);Insert(T,num);//二叉排序樹的元素插入；}while(m--){int flag=0;T1=NULL;//對樹初始化處理；for(int i=0;i<n;i++){scanf("%d",&num);Insert(T1,num);}flag=judge(T,T1);if(flag)printf("Yes\n");elseprintf("No\n");}}return 0; }

總結

以上是生活随笔為你收集整理的数据结构实验之查找一：二叉排序树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。