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

輸入格式:

輸入包含若干組測試數據。每組數據的第1行給出兩個正整數N?(≤)和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

AC代碼

1 #include<stdio.h> 2 #include<stdlib.h> 3 4 5 typedef struct TreeNode *BT; 6 struct TreeNode{ 7 int data; 8 BT right; 9 BT left; 10 int flag; 11 12 }; 13 BT insertNode(BT T,int temp){ 14 if(!T){ 15 T = (BT)malloc(sizeof(struct TreeNode)); 16 T->data = temp; 17 T->left = T->right =NULL; 18 T->flag = 0; 19 }else 20 if(temp < T->data){ 21 T->left = insertNode(T->left,temp); 22 }else if(temp > T->data){ 23 T->right = insertNode(T->right,temp); 24 } 25 return T; 26 } 27 28 BT buildTree(int N){ 29 BT T = NULL; 30 int temp; 31 for(int i = 0; i < N; i++){ 32 scanf("%d",&temp); 33 T = insertNode(T,temp); 34 } 35 return T; 36 } 37 int FindandChange(BT T,int temp){ 38 if(!T){ 39 return 0; 40 } 41 if(T->data == temp){ 42 T->flag = 1; 43 return 1; 44 }else 45 if(!T->flag){ 46 return 0; 47 }else if(T->data > temp){ 48 FindandChange(T->left,temp); 49 }else{ 50 FindandChange(T->right,temp); 51 } 52 53 } 54 55 56 void IsSameBST(BT T,int N){ 57 int flag = 1; 58 int temp; 59 for(int i = 0; i < N; i++){ 60 scanf("%d",&temp); 61 if(flag){ 62 flag = FindandChange(T,temp); 63 } 64 } 65 if(flag){ 66 printf("Yes\n"); 67 }else{ 68 printf("No\n"); 69 } 70 } 71 72 73 void reSetflag(BT T){ 74 if(!T){ 75 return; 76 } 77 T->flag = 0; 78 reSetflag(T->left); 79 reSetflag(T->right); 80 } 81 void freeBST(BT T){ 82 if(!T){ 83 return; 84 } 85 freeBST(T->left); 86 freeBST(T->right); 87 free(T); 88 } 89 int main(){ 90 int N,k; 91 scanf("%d",&N); 92 while(N){ 93 scanf("%d",&k); 94 BT T; 95 T = buildTree(N); 96 for(int i = 0; i < k; i++){ 97 IsSameBST(T,N); 98 reSetflag(T); 99 } 100 freeBST(T); 101 scanf("%d",&N); 102 } 103 return 0; 104 }

?

轉載于:https://www.cnblogs.com/jinjin-2018/p/8718648.html

總結

以上是生活随笔為你收集整理的是否同一棵二叉搜索树的全部內容，希望文章能夠幫你解決所遇到的問題。

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