#2
令狐少侠562015-11-23 12:30
|
是否同一棵二叉搜索树
给定一个插入序列就可以唯一确定一棵二叉搜索树。然而,一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{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 ;
}
}
#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编辑过]