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

问题 B: 二叉搜索树

题目描述

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

输入

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

输出

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

样例输入 Copy

6
45021
12045
54120
45021
45012
21054
50412
0

样例输出 Copy

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;
}

最后

以上就是温柔吐司为你收集整理的算法笔记-问题 B: 二叉搜索树的全部内容，希望文章能够帮你解决算法笔记-问题 B: 二叉搜索树所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。