144-17

判断两树相似，相似是指，两个树都存在对应的左子树或右子树

递归方法

当两个结点都是空时：return 1;

当两个结点有一个为空时：return 0;

当两个都不为空时，开始递归，并返回左右子树的&&值

#include <stdio.h>
#include <stdlib.h>

typedef struct node{
    int data;
    struct node *lchild,*rchild;
}TreeNode,*Tree;

void CreateTree(Tree &T)        //先序创建二叉树，中序后序创建和递归遍历一样，只修改位置 
{
    int x;
    scanf("%d",&x);
    if(x==-1)
    {
        T=NULL;
        return;    
    }
    else
    {
        T=(TreeNode*)malloc(sizeof(TreeNode));
        T->data=x;
        printf("输入%d的左结点:",x);
        CreateTree(T->lchild);
        printf("输入%d的右结点:",x);
        CreateTree(T->rchild);
    }
}

int Judge(Tree T1,Tree T2)
{
    int left,right;
    if(T1==NULL && T2==NULL)
        return 1;
    else if(T1==NULL || T2==NULL)
        return 0;
    else
    {
        left=Judge(T1->lchild,T2->lchild);
        right=Judge(T1->rchild,T2->rchild);
        return left&&right; 
    }    
}

int main()
{
    Tree T1,T2;
    CreateTree(T1);
    CreateTree(T2);
    if(Judge(T1,T2))
        printf("两树相似");    
    return 0;    
}