二叉排序樹的定義是：或者是一棵空樹，或者是具有下列性質的二叉樹： 若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值； 若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值； 它的左、右子樹也分別為二叉排序樹。 今天我們要判斷兩序列是否為同一二叉排序樹 Input
開始一個數n，(1<=n<=20) 表示有n個需要判斷，n= 0 的時候輸入結束。 接下去一行是一個序列，序列長度小于10，包含(0~9)的數字，沒有重復數字，根據這個序列可以構造出一顆二叉排序樹。 接下去的n行有n個序列，每個序列格式跟第一個序列一樣，請判斷這兩個序列是否能組成同一顆二叉排序樹。(數據保證不會有空樹) Output
Example Input
2 123456789 987654321 432156789 0 Example Output
NO NO Hint
Author
因為要判斷是不是同一二叉排序樹，所以就判斷是否等于它本身。
#include<stdio.h>#include<stdlib.h>#include<string.h>struct node{ int data; struct node *l, *r;};struct node *creat(struct node *root, char 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 = 0;void judge(struct node *root1, struct node *root2){ if(root1 == NULL || root2 == NULL) { return; } if(root1 && root2) { if(root1 -> data != root2 -> data) return; else { x++; judge(root1 -> l, root2 -> l); judge(root1 -> r, root2 -> r); } }}int main(){ int n, len, i, j; char a[22], b[22]; while(scanf("%d", &n) != EOF) { if(n == 0) break; struct node *root1 = NULL;//劃重點 scanf("%s", a); len = strlen(a); for(i = 0; i < len; i++) root1 = creat(root1, a[i]); for(i = 0; i < n; i++) { x = 0;//劃重點 struct node *root2 = NULL;//劃重點 scanf("%s", b); for(j = 0; j < len; j++) { root2 = creat(root2, b[j]); } judge(root1, root2); if(x == len) printf("YES/n"); else printf("NO/n"); } } return 0;}新聞熱點
疑難解答
