算法笔记-问题 B: 二叉搜索树

81 阅读 0 评论 54 点赞

我是靠谱客的博主温柔吐司，这篇文章主要介绍算法笔记-问题 B: 二叉搜索树，现在分享给大家，希望可以做个参考。

问题 B: 二叉搜索树

题目描述

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

输入

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

输出

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

样例输入 Copy

复制代码

样例输出 Copy

复制代码

1
2
3
4
5
6
NO
NO
YES
NO
NO
NO

代码：

复制代码

#include <bits/stdc++.h>

using namespace std;
const int maxn = 10000;
int n, d;
struct node{
    int data;
    node *lchild, *rchild;
};

/*插入*/
void insert(node* &root, int data){
    if(root == NULL){
        root = new node;
        root->data = data;
        root->lchild = root->rchild = NULL;
        return;
    }
    if(data == root->data) return;/*关键！！这里默认二叉排序树不允许有重复键值*/
    if(data<root->data) insert(root->lchild, data);
    else insert(root->rchild, data);
}

/*先序*/
void preOrder(node* root, vector<int> &vi){
    if(root == NULL) return;
    vi.push_back(root->data);
    preOrder(root->lchild, vi);
    preOrder(root->rchild, vi);
}

/*中序*/
void inOrder(node* root, vector<int> &vi){
    if(root == NULL) return;
    inOrder(root->lchild, vi);
    vi.push_back(root->data);
    inOrder(root->rchild, vi);
}

/*后序*/
void postOrder(node* root, vector<int> &vi){
    if(root == NULL) return;
    postOrder(root->lchild, vi);
    postOrder(root->rchild, vi);
    vi.push_back(root->data);
}

int main(){
    int n;
    while(scanf("%d", &n)!=EOF){
        node* root = NULL;
        vector<int> pre, in, post;
        for(int i=0; i<n; i++){
            int data;
            scanf("%d", &data);
            insert(root, data);
        }
        preOrder(root, pre);
        inOrder(root, in);
        postOrder(root, post);
        for(int i=0; i<pre.size(); i++){
            printf("%d ", pre[i]);
        }
        printf("n");
        for(int i=0; i<in.size(); i++){
            printf("%d ", in[i]);
        }
        printf("n");
        for(int i=0; i<post.size(); i++){
            printf("%d ", post[i]);
        }
        printf("n");
    }
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <bits/stdc++.h>

using namespace std;
const int maxn = 10000;
int n, d;
struct node{
    int data;
    node *lchild, *rchild;
};

/*插入*/
void insert(node* &root, int data){
    if(root == NULL){
        root = new node;
        root->data = data;
        root->lchild = root->rchild = NULL;
        return;
    }
    if(data == root->data) return;/*关键！！这里默认二叉排序树不允许有重复键值*/
    if(data<root->data) insert(root->lchild, data);
    else insert(root->rchild, data);
}

/*先序*/
void preOrder(node* root, vector<int> &vi){
    if(root == NULL) return;
    vi.push_back(root->data);
    preOrder(root->lchild, vi);
    preOrder(root->rchild, vi);
}

/*中序*/
void inOrder(node* root, vector<int> &vi){
    if(root == NULL) return;
    inOrder(root->lchild, vi);
    vi.push_back(root->data);
    inOrder(root->rchild, vi);
}

/*后序*/
void postOrder(node* root, vector<int> &vi){
    if(root == NULL) return;
    postOrder(root->lchild, vi);
    postOrder(root->rchild, vi);
    vi.push_back(root->data);
}

int main(){
    int n;
    while(scanf("%d", &n)!=EOF){
        node* root = NULL;
        vector<int> pre, in, post;
        for(int i=0; i<n; i++){
            int data;
            scanf("%d", &data);
            insert(root, data);
        }
        preOrder(root, pre);
        inOrder(root, in);
        postOrder(root, post);
        for(int i=0; i<pre.size(); i++){
            printf("%d ", pre[i]);
        }
        printf("n");
        for(int i=0; i<in.size(); i++){
            printf("%d ", in[i]);
        }
        printf("n");
        for(int i=0; i<post.size(); i++){
            printf("%d ", post[i]);
        }
        printf("n");
    }
	return 0;
}