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

最新推荐文章于 2025-03-03 21:49:11 发布

JinbaoSite0144

最新推荐文章于 2025-03-03 21:49:11 发布

阅读量775

点赞数 1

分类专栏：数据结构-陈越、何钦铭文章标签：遍历数据结构二叉搜索树

本文链接：https://blog.csdn.net/codeforcer/article/details/52780431

版权

数据结构-陈越、何钦铭专栏收录该内容

12 篇文章

订阅专栏

本文介绍了一种算法，该算法通过给定的序列构造二叉搜索树，并比较多个二叉搜索树是否相同。首先根据初始序列构建一棵二叉搜索树作为基准，接着对于每一个后续序列构建相应的二叉搜索树并进行比较。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题意

给你一个序列构造一个二叉搜索树，然后再给你L个序列，对每个序列构造二叉搜索树，问这棵二叉搜索树跟最开始的二叉搜索树是否一样？

解题思路

分别构造二叉搜索树，然后同时对两棵二叉搜索树进行遍历，看是否一样。

参考代码

#include <iostream>
using namespace std;
typedef struct Node{
    int v;
    struct Node *l,*r;
}*tree;
int a[15],b[15];
void Insert(tree &t,int x){
    if (t==NULL){
        t=new Node;
        t->v=x;
        t->l=t->r=NULL;
        return;
    }
    if (x>t->v)
        Insert(t->r,x);
    else
        Insert(t->l,x);
}
bool query(tree t1,tree t2){
    if (t1==NULL && t2==NULL){
        return true;
    }
    else if (t1!=NULL && t2!=NULL){
        if (t1->v!=t2->v) return false;
        else{
            if (query(t1->l,t2->l)==true && query(t1->r,t2->r)==true)
                return true;
            return false;
        }
    }
    return false;
}
int main(){
    int n,l,x;
    while (cin>>n){
        if (n==0) break;
        cin>>l;
        tree t1=NULL,t2=NULL;
        for (int i=0;i<n;i++){
            cin>>x;
            Insert(t1,x);
        }
        for (int i=0;i<l;i++){
            t2=NULL;
            for (int j=0;j<n;j++){
                cin>>x;
                Insert(t2,x);
            }
            if (query(t1,t2)==true) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
    }
    return 0;
}