判断两颗二叉树是否相似的两种方法
名称:判断两个二叉树是否相似
说明:此处的两个方法一个是非递归，一个是递归算法。其实两个算法的本质思路是一样的就是，判断位置相同的两个结点是否同时为空或同时不为空。只是具体的实现不一样。
对于层次遍历法：此处不小心用错了，本应该用队列来当作排列下一层元素的。歪打正着，此处用栈也可以，只是判断的结点顺序不一样。队列的话，是从每一层的左端到右端。栈的话，是从右端到左端。在此处都没影响。我去，有发现一点，要从右到左访问一层的元素的话，应该用栈。
对于递归，看起来比非递归要简单不少。基本的思路很简单，要注意的是，在程序需要从子树接收返回是否相似的信息。这样的话，有一个问题，就是必须等树完全判断完才可以最终返回。不想上面的，过程中发现不一样就可以立即返回了。
//层次遍历法判断两棵树是否相似
boolIsSemblable1(BiTreeT1,BiTreeT2)
{
stack_sta1,_sta2;//用来存放下一层元素的容器，此处栈和队列都行
BiTNode*p1=T1,*p2=T2;//p1用来跟踪T1,p2用来跟踪T2
while((_sta1.empty()==false||p1!=NULL)&&(_sta2.empty()==false||p2!=NULL))
{
if(p1!=NULL&&p2!=NULL)//如果p1和p2都不为空时
{
if(p1->lchild!=NULL&&p2->lchild!=NULL)//如果p1和p2的左子树都不为空时
{
_sta1.push(p1->lchild);
_sta2.push(p2->lchild);
}
elseif(p1->lchild!=NULL||p2->lchild!=NULL)//如果p1的左子树为空，但是p2的左子树不为空，或者相反
returnfalse;
if(p1->rchild!=NULL&&p2->rchild!=NULL)//如果p1和p2的右子树都不为空时
{
_sta1.push(p1->rchild);
_sta2.push(p2->rchild);
}
elseif(p1->rchild!=NULL||p2->rchild!=NULL)//如果p1的右子树为空，但是p2的右子树不为空，或者相反
returnfalse;
//访问完两棵树的当前结点后，置空让下一次循环弹出栈中元素（此处其实直接弹出元素也行）
p1=NULL;
p2=NULL;
}
elseif(p1!=NULL||p2!=NULL)//当前节点有一个为空
returnfalse;
else
{
//弹出两个树的栈顶元素
p1=_sta1.top();
p2=_sta2.top();
_sta1.pop();
_sta2.pop();
}
}
returntrue;
}
//递归判断两棵树是否相似
boolIsSemblable2(BiTreeT1,BiTreeT2)
{
boolleftS=false,rightS=false;//用来接受子树返回的信息
if(T1==NULL&&T2==NULL)//两个结点都为空
returntrue;
elseif(T1==NULL||T2==NULL)//有一个结点不为空
returnfalse;
else
{
intleftS=IsSemblable2(T1->lchild,T2->lchild);//递归左子树
intrightS=IsSemblable2(T1->rchild,T2->rchild);//递归右子树
returnleftS&&rightS;//返回两个子树的信息
}
}
总结
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，谢谢大家对毛票票的支持。如果你想了解更多相关内容请查看下面相关链接