前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >判断是否为同一颗二叉搜索树

判断是否为同一颗二叉搜索树

作者头像
用户5513909
发布2023-04-25 11:09:07
1000
发布2023-04-25 11:09:07
举报
文章被收录于专栏:小鱼儿我的学习笔记

方法:建一颗树,在判别其他序列是否与该树一致

判别方法
代码语言:javascript
复制
#include <stdio.h>
#include<stdlib.h>
typedef struct TreeNode *Tree;  //表示二叉搜索树树
struct TreeNode{
    int v;
    Tree Left,Right;
    int flag; //某个节点被访问过flag=0,未被访问flag=1
};

Tree NewNode(int V) //建立新的节点
{
    Tree T;
    T = (Tree)malloc(sizeof(struct TreeNode));
    T->v = V;
    T->Left = T->Right = NULL;
    T->flag = 0;
    return T;
}

Tree Insert(Tree T, int V)  //插入节点
{
    if(!T) T = NewNode(V);
    else{
        if(V>T->v)
            T->Right = Insert(T->Right, V);
        else
            T->Left = Insert(T->Left,V);
    }
    return T;
}

Tree MakeTree(int N)  //建立搜索二叉树
{
    Tree T;
    int i,V;

    scanf("%d",&V);
    T = NewNode(V);
    for(i=1; i<N; i++){
        scanf("%d",&V);
        T = Insert(T,V);
    }
    return T;
}

int check(Tree T,int V)
{
    if(T->flag){
        if(V<T->v) return check(T->Left,V);
        else if(V>T->v) return check(T->Right,V);
        else return 0;
    }
    else{
        if(V==T->v){
            T->flag = 1;
            return 1;
        }
        else return 0;
    }
}

int Judge(Tree T, int N)
{
    int i,V,flag = 0;
    scanf("%d",&V);
    if(V!=T->v) flag = 1;
    else T->flag = 1;
    for(i=1; i<N; i++){
        scanf("%d",&V);
        if((!flag)&&(!check(T,V))) flag = 1;
    }
    if(flag) return 0;
    else return 1;
}
void ResetT(Tree T)
{
    if(T->Left) ResetT(T->Left);
    if(T->Right) ResetT(T->Right);
    T->flag = 0;
}

void FreeTree(Tree T)
{
    if(T->Left) FreeTree(T->Left);
    if(T->Right) FreeTree(T->Right);
    free(T);
}

int main()
{
    int N,L,i;
    Tree T;
    scanf("%d",&N);
    while(N){
        scanf("%d",&L);
        T = MakeTree(N);
        for(i=0;i<L;i++){
            if(Judge(T,N)) printf("Yes\n");
            else printf("No\n");
            ResetT(T);
        }
        FreeTree(T);
        scanf("%d",&N);
    }
    return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020-04-01,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 方法:建一颗树,在判别其他序列是否与该树一致
    • 判别方法
    领券
    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档