首页 > 其他 > 详细

04-树4 是否同一棵二叉搜索树

时间:2018-10-19 13:18:17      阅读:143      评论:0      收藏:0      [点我收藏+]

给定一个插入序列就可以唯一确定一棵二叉搜索树。然而,一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{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


 1 #include<stdio.h> 
 2 #include<stdlib.h>
 3 
 4 typedef struct TNode *PtrToTNode;
 5 struct TNode{
 6     int Data;
 7     PtrToTNode Right, Left;
 8 };
 9 typedef PtrToTNode Tree;
10 
11 //二叉搜索树插入函数 
12 Tree Insert(Tree BST, int data){
13     if(!BST){
14         BST = (Tree)malloc(sizeof(struct TNode));
15         BST->Data = data;
16         BST->Left = BST->Right = NULL;
17     }
18     else{
19         if(BST->Data < data){
20             BST->Right = Insert(BST->Right, data);
21         }
22         else if(BST->Data > data){
23             BST->Left = Insert(BST->Left, data);
24         }
25     }
26     return BST;
27 }
28 
29 //递归地判断BST1和BST2每个结点是否相等 
30 bool CompareBST(Tree BST1, Tree BST2){
31     bool flag;
32     if(!BST1 && !BST2) flag = true;
33     else if(BST1->Data == BST2->Data){
34         flag = (CompareBST(BST1->Left, BST2->Left) && CompareBST(BST1->Right, BST2->Right));
35     }
36     else flag = false;
37     return flag;
38 }
39  
40 int main( ){
41     while(1){
42         int N, L, data;
43         scanf("%d", &N);
44         if(N==0) break;         //根据题意,当N==0时跳出循环 
45         scanf("%d", &L);
46         Tree BST1 = NULL;
47         for(int i=0; i<N; i++){           
48             scanf("%d", &data);
49             BST1 = Insert(BST1, data);
50         }
51         while(L--){
52             Tree BST2 = NULL;
53             for(int i=0; i<N; i++){
54                 scanf("%d", &data);
55                 BST2 = Insert(BST2, data);
56             }
57             if(CompareBST(BST1, BST2)) printf("Yes\n");
58             else printf("No\n");
59         }
60     }
61     return 0;
62 }

 

04-树4 是否同一棵二叉搜索树

原文:https://www.cnblogs.com/shin0324/p/9815705.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!