二叉搜索树

tiger

二叉搜索树

二叉搜索树是二叉树的一种

它具有4条性质

1.              若左子树不为空，则其左子树上的结点的值全都小于其根节点

2.              若右子树不为空，则其右子树上的结点的值全都大于其根节点

3.              二叉搜索树的左右子树本身都是单独的一个完整的二叉搜索树

4.              数值最大的节点没有左孩子，数值最小的节点没有右儿子

（后文中，n是节点个数，h为高度）

例题：3507

信息学基地 (singera.cn)

题目描述

判断两序列是否为同一二叉搜索树序列

输入

开始一个数n，(1<=n<=20) 表示有n个需要判断，n= 0 的时候输入结束。
接下去一行是一个序列，序列长度小于10，包含(0~9)的数字，没有重复数字，根据这个序列可以构造出一颗二叉搜索树。
接下去的n行有n个序列，每个序列格式跟第一个序列一样，请判断这两个序列是否能组成同一颗二叉搜索树。

输出

如果序列相同则输出YES，否则输出NO

样例输入1

2
567432   A
543267   B
576342   C
0

样例输出1

YES
NO

提示/说明

每个序列长度不超过20

标签

普及+/提高 其他 二叉搜索树，BST

解题思路：

1.    假设输入的A串为中序遍历，构造出二叉搜索树，存储前序遍历，中序遍历，后序遍历，和层次遍历

2.    依次判断B,C串

3.    输出

4.    参考代码

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. struct BiNode
   
4. {
   
5.     char data;
   
6.     BiNode *lchild;
   
7.     BiNode *rchild;
   
8. };
   
9. char a[20];
   
10. int num;
    
11. void create(BiNode *&root,char ch)
    
12. {
    
13.     if(root==NULL)//为空直接插入
    
14.     {
    
15.         root=(BiNode*)malloc(sizeof(BiNode));
    
16.         root->data=ch;
    
17.         root->lchild=NULL;
    
18.         root->rchild=NULL;
    
19.     }
    
20.     else
    
21.     {
    
22.         if(ch < root->data)
    
23.             create(root->lchild,ch);
    
24.         else
    
25.             create(root->rchild,ch);
    
26.     }
    
27. }
    
28. void pre(BiNode *root)//前序遍历
    
29. {
    
30.     if(root!=NULL)
    
31.     {
    
32.         a[num++]=root->data;
    
33.         pre(root->lchild);
    
34.         pre(root->rchild);
    
35.     }
    
36. }
    
37. int main()
    
38. {
    
39.     char str1[20],str2[20];
    
40.     int n;
    
41.     while(~scanf("%d",&n))
    
42.     {
    
43.         num=0;
    
44.         char b[20],c[20];
    
45.         BiNode *root;
    
46.         root=NULL;
    
47.         scanf("%s",str1);
    
48.         for(int i=0; str1[i]; i++)
    
49.             create(root,str1[i]);
    
50.         pre(root);
    
51.         strcpy(b,a);///将第一棵树前序遍历序列保存在b中
    
52.         for(int i=0; i<n; i++)
    
53.         {
    
54.             num=0;
    
55.             int flag=0;
    
56.             BiNode *bt;
    
57.             bt=NULL;
    
58.             scanf("%s",str2);
    
59.             for(int i=0; str2[i]; i++)
    
60.                 create(bt,str2[i]);
    
61.             pre(bt);
    
62.             strcpy(c,a);///将第二棵树前序遍历序列保存在c中
    
63.             if(strcmp(b,c)!=0)
    
64.                 printf("NO\n");
    
65.             else
    
66.                 printf("YES\n");
    
67.         }
    
68.     }
    
69.     return 0;
    
70. }

复制代码