原题
能否同一棵二叉搜索树
给定一个插入序列就可以唯一确定一棵二叉搜索树。然而,一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{2, 1, 3}和{2, 3, 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 ; } }