對(duì)應(yīng)給定的一個(gè)序列可以唯一確定一棵二叉排序樹。然而，一棵給定的二叉排序樹卻可以由多種不同的序列得到。例如分別按照序列{3,1,4}和{3,4,1}插入初始為空的二叉排序樹，都得到一樣的結(jié)果。你的任務(wù)書對(duì)于輸入的各種序列，判斷它們是否能生成一樣的二叉排序樹。 Input
輸入包含若干組測(cè)試數(shù)據(jù)。每組數(shù)據(jù)的第1行給出兩個(gè)正整數(shù)N (n < = 10)和L，分別是輸入序列的元素個(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ù)不要處理。 Output
對(duì)每一組需要檢查的序列，如果其生成的二叉排序樹跟初始序列生成的二叉排序樹一樣，則輸出”Yes”，否則輸出”No”。 Example Input
4 2 3 1 4 2 3 4 1 2 3 2 4 1 2 1 2 1 1 2 0 Example Output
Yes No No Hint
Author xam
#include<stdio.h>#include<string.h>#include<stdlib.h>struct node{ int data; struct node *l, *r;};struct node *creat(struct node *root, int number){ if(root == NULL) { root = (struct node *) malloc (sizeof(struct node)); root -> data = number; root -> l = NULL; root -> r = NULL; } else { if(root -> data > number) root -> l = creat(root -> l, number); else root -> r = creat(root -> r, number); } return root;};int x;void judge(struct node *root1, struct node *root2){ if(root1 && root2) { if(root1 -> data == root2 -> data) { x++; judge(root1 -> l, root2 -> l);//別忘了遞歸。。。 judge(root2 -> r, root2 -> r); } else return; } if(root1 == NULL || root2 == NULL) return;}int main(){ int n, l, i, j, number; while(scanf("%d", &n) != EOF) { if(n == 0) break; scanf("%d", &l); struct node *root1 = NULL;//NULL不能忘了 for(i = 0; i < n; i++) { scanf("%d", &number); root1 = creat(root1, number); } for(i = 0; i < l; i++) { struct node *root2 = NULL;//同上 x = 0; for(j = 0; j < n; j++) { scanf("%d", &number); root2 = creat(root2, number); } judge(root1, root2); if(x == n) printf("Yes/n"); else printf("No/n"); } } return 0;}新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
