用户注册



邮箱:

密码:

用户登录


邮箱:

密码:
记住登录一个月忘记密码?

发表随想


还能输入:200字
云代码 - c++代码库

是否同一棵二叉搜索树

2017-11-24 作者:芙蓉妹妹举报

[c++]代码库

#include<bits/stdc++.h>
using namespace std;
typedef struct TreeNode * Tree;
struct TreeNode
{
    int data;
    Tree left, right;
    int flag;
};
Tree NewNode(int V)
{
    Tree T = (Tree)malloc(sizeof(struct TreeNode));
    T->data = V;
    T->left = T->right = NULL;
    T->flag = 0;
    return T;
}

Tree Insert(Tree T,int V)//二叉排序树的插入方式
{
    if(T)
    {
        if(V > T->data)
            T->right = Insert(T->right,V);
        else
            T->left = Insert(T->left,V);
    }
    else
        T = NewNode(V);
    return T;
}

Tree MakeTree(int N)
{
    Tree R;
    int i, V;
    cin>>V;
    R = NewNode(V);
    for( i = 1; i < N; i ++)
    {
        cin>>V;
        R = Insert(R,V);
    }
    return R;
}

int check(Tree T,int V)
{
    if(T->flag)//如果当前节点查找过了
    {
        if(V < T->data)
            return check(T->left,V);//此时要查找的数小于该节点的数,去左边查找
        else if(V > T->data)
            return check(T->right,V);//大于该节点的数,去右边查找
        else
            return 0;//如果相等则不一致
    }
    else//如果当前节点没查找过
    {
        if(V == T->data)//如果是要查找的节点则标记为查找过
        {
            T->flag=1;
            return 1;
        }
        else return 0;//如果当前节点没被查找过还不是要查找的节点,则不一致
    }
}

int judge(Tree T,int N)
{
    int i, V, flag = 1;
    cin>>V;
    if(V == T->data)
        T->flag = 1;   //1代表目前还一致
    else
        flag = 0;
    for( i =1 ; i < N ; i ++)
    {
        cin>>V;
        if(flag&&(!check(T,V)))
            flag=0;//如果check不一致,则整棵树不一致
    }
    if(flag)
        return 1;
    else
        return 0;
}

void ResetFlag(Tree T)

{
    if( T -> left)
        ResetFlag(T->left);
    if( T -> right)
        ResetFlag(T->right);
    T->flag = 0;
}
void TreeFree(Tree T)
{
    if( T -> left)
        TreeFree(T->left);
    if( T -> right)
        TreeFree(T->right);
    free(T);
    T=NULL;
}

int main ()
{
    Tree T;//初始化数
    int N, L, i;
    cin>>N;
    while(N)
    {
        cin>>L;
        T = MakeTree(N);//建本次事例的初始化对比树
        for ( i = 0; i < L; i ++ )
        {
            if (judge(T,N))
                cout<<"Yes"<<endl;
            else
                cout<<"No"<<endl;
            ResetFlag(T);//清楚判断过程中flag标记
        }
        TreeFree(T);//清楚本次事例的对比数
        cin>>N;
    }
}


分享到:
更多

网友评论    (发表评论)

共1 条评论 1/1页

发表评论:

评论须知:

  • 1、评论每次加2分,每天上限为30;
  • 2、请文明用语,共同创建干净的技术交流环境;
  • 3、若被发现提交非法信息,评论将会被删除,并且给予扣分处理,严重者给予封号处理;
  • 4、请勿发布广告信息或其他无关评论,否则将会删除评论并扣分,严重者给予封号处理。