浙大机试OJ——二叉搜索树

傷城~ 2022-05-19 14:38 207阅读 0赞

### **|题目描述：** ###

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

### **|输入描述:** ###

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

### **输出描述:** ###

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

### 示例1 ###

### 输入 ###

2
    567432
    543267
    576342
    0

### 输出 ###

YES
    NO

### |解题思路： ###

前序遍历和中序遍历可以唯一确定一棵二叉树，对于二叉排序树，相同元素的二叉排序树中序遍历一定相同，而不同元素二叉排序树使用前序遍历就可以发现不相同，所以只需要前序遍历两个二叉树，比较两者是否相同就可以判断。

### |具体代码： ###

#include<bits/stdc++.h>
    using namespace std;
    
    struct node{
        int x;
        node * lchild;
        node* rchild;
    }Tree[1000];
     
    int size = 0;
     
    node * create(){
        Tree[size].lchild = Tree[size].rchild = NULL;
        return &Tree[size++];
    }
     
    node * build(node* tree, int x){
        if(tree == NULL){
            tree = create();
            tree->x = x;
            return tree;
        }else if(x > tree->x){
            tree->rchild = build(tree->rchild,x);
        }else if(x < tree->x){
            tree->lchild = build(tree->lchild,x);
        }
        return tree;
    }
     
    int count=0;
    void preorder(node* tree, int a[]){
        if(tree == NULL) return;
        a[count++] = tree->x;
        a[count] = 0;
        before(tree->lchild,a);
        before(tree->rchild,a);
    }
     
    int main(){
        int n;
        while(cin >> n && n!=0){
            string s;
            cin >> s;
            node* tree = NULL;
            for(int i=0; i<s.size(); i++){
                tree=build(tree,s[i]-'0');
            }
            for(int i=0; i<n; i++){
                string s1;
                node* tree1 = NULL;
                cin >> s1;
                for(int i=0; i<s1.size(); i++){
                    tree1=build(tree1,s1[i]-'0');
                }
                int a[50],b[50];
                preorder(tree,a);
                count=0;
                preorder(tree1,b);
                count=0;
                int flag=1;
                for(int i=0; i<s.size(); i++){
                    if(a[i] != b[i])
                        flag = 0;
                }
                if(flag) cout << "YES" << endl;
                else cout << "NO" << endl;
            }
        }
        return 0;
    }

--------------------

关于二叉树的问题还是挺容易出现的，对这个知识点掌握得还不好，继续加油吧！ヾ(◍°∇°◍)ﾉﾞ