博客

若已知两棵二叉树B1和B2皆为空，或者皆不空且B1的左、右子树和B2的左、右子树分别相似，则称二叉树B1和B2相似。试编写算法，判别给定两棵二叉树是否相似。

二叉链表类型定义：

typedef struct BiTNode {
    TElemType data;
    BiTNode  *lchild, *rchild;
} BiTNode, *BiTree;

实现函数如下：

Status Similar(BiTree t1, BiTree t2)
/* 判断两棵二叉树是否相似的递归算法 */
{
    if(!t1 && !t2)//同为空时，两树相似
        return TRUE;
    else if(t1 && t1){
        if(Similar(t1 -> lchild,t2 -> lchild) && Similar(t1 -> rchild,t2 -> rchild))
            //两树都不为空时，判断左右子树是否相似
            return TRUE;
        else
            return FALSE;
    }else//以上两种情况都不符合，就直接返回FALSE
        return FALSE;
}