判断能否是同一棵二叉搜索树。多组数据该怎么修改代码

C语言 码拜 7年前 (2015-11-25) 664次浏览
原题
能否同一棵二叉搜索树
给定一个插入序列就可以唯一确定一棵二叉搜索树。然而,一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{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 ;
    }
}

CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明判断能否是同一棵二叉搜索树。多组数据该怎么修改代码
喜欢 (0)
[1034331897@qq.com]
分享 (0)