欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

7-1 是否同一棵二叉搜索树 (25分)

程序员文章站 2024-01-17 18:15:34
...

7-1 是否同一棵二叉搜索树 (25分)
分析:
关键点是创建搜索二叉树和比较是否为同一棵树。
首先创建,一开始树为空,就要动态分配一个结点,把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;
}
相关标签: 笔记 数据结构