7-1 是否同一棵二叉搜索树 (25分)
程序员文章站
2024-01-17 18:15:34
...
分析:
关键点是创建搜索二叉树和比较是否为同一棵树。
首先创建,一开始树为空,就要动态分配一个结点,把Data放入,左右置为空。
如果x比根结点的值小,则左子树等于左子树的创建(递归下去)。如果x比根结点的值大,则右子树等于右字数的创建(递归下去)。
然后是比较,我采用的方法是把两棵树都先创建好,然后如果两棵树都空,则返回1,表示两棵树相同。如果所指结点的数据不同返回0,表示两树不相等,其他情况返回两棵树左孩子和右孩子的比较情况。
#include<stdio.h>
#include<stdlib.h>
typedef struct TNode* BinTree;
struct TNode{
int Data;
BinTree Left;
BinTree Right;
};
BinTree Insert( BinTree BST, int x )
{
if(!BST){
BST=(BinTree)malloc(sizeof(struct TNode));
BST->Data=x;
BST->Left=BST->Right=NULL;
}
else{
if(x<BST->Data) BST->Left=Insert( BST->Left, x );
else if(x>BST->Data) BST->Right=Insert( BST->Right, x );
}
return BST;
}
int Compare(BinTree BTS,BinTree B)
{
if(!BTS && !B) return 1;
if(BTS->Data!=B->Data) return 0;
else return (Compare(BTS->Left,B->Left)&&Compare(BTS->Right,B->Right));
}
int main()
{
int n,l,i,x,j;
scanf("%d",&n);
while(n!=0){
BinTree BST=NULL,B=NULL;
scanf("%d",&l);
for(i=0;i<n;i++){
scanf("%d",&x);
BST = Insert(BST, x);
}
for(i=0;i<l;i++){
for(j=0;j<n;j++){
scanf("%d",&x);
B = Insert(B, x);
}
if(Compare(BST,B)) printf("Yes\n");
else printf("No\n");
B=NULL;
}
free(BST);
free(B);
scanf("%d",&n);
}
return 0;
}
上一篇: 06-图3 六度空间