| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2212 人关注过本帖
标题:是否是同一棵二叉搜索树:多组数据输入该怎么办啊
只看楼主 加入收藏
令狐少侠56
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:320
专家分:175
注 册:2014-4-10
结帖率:58.18%
收藏
 问题点数:0 回复次数:1 
是否是同一棵二叉搜索树:多组数据输入该怎么办啊
原题
是否同一棵二叉搜索树
给定一个插入序列就可以唯一确定一棵二叉搜索树。然而,一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{2, 1, 3}和{2, 3, 1}插入初始为空的二叉搜索树,都得到一样的结果。于是对于输入的各种插入序列,你需要判断它们是否能生成一样的二叉搜索树。

图片附件: 游客没有浏览图片的权限,请 登录注册

我的结果是对的,可我不知道这样的多组数据该怎么处理。。。
程序代码:
#include <stdio.h>
#include <stdlib.h>


typedef struct BSTNode* BinTree ;
struct BSTNode
{
    int Data ;
    struct BSTNode* Left ;
    struct BSTNode* Right ;
} ;


BinTree Insert( int x , BinTree  BST )
{
    if( BST==NULL )
    {
        BST=(BinTree) malloc( sizeof(struct BSTNode) ) ;
        BST->Data = x ;
        BST->Left = NULL ;
        BST->Right = NULL ;
    }
    else
    {
        if( x<BST->Data  )
            BST->Left=Insert( x , BST->Left  ) ;
        else //二叉树元素不重复,不含相等的情况
            BST->Right = Insert(x , BST->Right ) ;
    }

    return BST ;
}


BinTree Build( int N )//改二叉搜索树不含重复序列
{
    BinTree Insert( int x , BinTree  BST ) ;
    int i , x ;
    BinTree  BST ;

    BST = NULL ;
    for(i=0 ; i<N ; i++)
    {
        scanf("%d",&x);
        BST=Insert(  x , BST ) ;
    }    
    return BST ;
}

int SameBST( BinTree OrangeBST , BinTree BST )
{
    if(BST==NULL&&OrangeBST==NULL)//两边都为空
        return 1 ;
    if( BST->Data != OrangeBST->Data )//根节点数据不同
        return 0 ;
    if( (BST->Left==NULL&&OrangeBST->Left!=NULL) || (BST->Left!=NULL&&OrangeBST->Left==NULL) )//一边左子树为空另一棵左子树非空
        return 0 ;
    if( BST->Left!=NULL && OrangeBST->Left!=NULL && BST->Left->Data!=OrangeBST->Left->Data)//两边左子树非空但元素不同
        return 0 ;
    if(  BST->Left!=NULL&&OrangeBST->Left!=NULL && BST->Left->Data == OrangeBST->Left->Data)//两边左子树都非空并且元素相同,判断右子树
        return SameBST( OrangeBST->Right , BST->Right  ) ;

}


void InOrderTraversal( BinTree BST )
{
    if(BST)
    {
        InOrderTraversal( BST->Left ) ;
        printf("%d ",BST->Data ) ;
        InOrderTraversal( BST->Right  ) ;
    }
}


int main()
{
    int i ;
    int N,L ; //每个序列插入元素的个数N , 需要检查的序列个数L
    BinTree  OrangeBST ;
//    BinTree  BST1,BST2 ;//不知道有几个待测量搜索树,定义变量个数未知,指针数组
    BinTree  NeedCompareBST[10] ;
    
    while(1)
    {    
        scanf("%d",&N) ;    
        if(N!=0)
        {
            scanf("%d",&L) ;
            OrangeBST = Build(  N ) ; //InOrderTraversal( OrangeBST ) ; printf("\n");
            for(i=0 ; i<L ; i++  )
            {
                NeedCompareBST[i] = Build( N ) ;             
                //InOrderTraversal( NeedCompareBST[i] ) ; printf("\n");                
            }
            for(i=0 ; i<L ; i++)
            {
                if( SameBST( OrangeBST , NeedCompareBST[i] ) )
                        printf("Yes\n") ;
                else
                    printf("No\n");
            }
        }
        else return 0 ;
    }

}

输入一组数据之后就会输出结果
图片附件: 游客没有浏览图片的权限,请 登录注册


[此贴子已经被作者于2015-11-23 10:26编辑过]

2015-11-22 18:58
令狐少侠56
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:320
专家分:175
注 册:2014-4-10
收藏
得分:0 
问题好像不是数据的输入输出,  return SameBST( OrangeBST->Right , BST->Right  ) ;错了
2015-11-23 12:30
快速回复:是否是同一棵二叉搜索树:多组数据输入该怎么办啊
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.016561 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved