判断两颗二叉树是否相似的两种方法

名称:判断两个二叉树是否相似

10余年的永吉网站建设经验,针对设计、前端、开发、售后、文案、推广等六对一服务,响应快,48小时及时工作处理。网络营销推广的优势是能够根据用户设备显示端的尺寸不同,自动调整永吉建站的显示方式,使网站能够适用不同显示终端,在浏览器中调整网站的宽度,无论在任何一种浏览器上浏览网站,都能展现优雅布局与设计,从而大程度地提升浏览体验。成都创新互联从事“永吉网站设计”,“永吉网站推广”以来,每个客户项目都认真落实执行。

说明:此处的两个方法一个是非递归,一个是递归算法。其实两个算法的本质思路是一样的就是,判断位置相同的两个结点是否同时为空或同时不为空。只是具体的实现不一样。

对于层次遍历法:此处不小心用错了,本应该用队列来当作排列下一层元素的。歪打正着,此处用栈也可以,只是判断的结点顺序不一样。队列的话,是从每一层的左端到右端。栈的话,是从右端到左端。在此处都没影响。我去,有发现一点,要从右到左访问一层的元素的话,应该用栈。

对于递归,看起来比非递归要简单不少。基本的思路很简单,要注意的是,在程序需要从子树接收返回是否相似的信息。这样的话,有一个问题,就是必须等树完全判断完才可以最终返回。不想上面的,过程中发现不一样就可以立即返回了。

//层次遍历法判断两棵树是否相似
bool IsSemblable1(BiTree T1,BiTree T2)
{
  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);
      }
      else if( p1->lchild != NULL || p2->lchild != NULL)  //如果p1的左子树为空,但是p2的左子树不为空,或者相反
        return false;
      if(p1->rchild != NULL && p2->rchild != NULL)   //如果p1和p2的右子树都不为空时
      {
        _sta1.push(p1->rchild);
        _sta2.push(p2->rchild);
      }
      else if(p1->rchild != NULL || p2->rchild != NULL)  //如果p1的右子树为空,但是p2的右子树不为空,或者相反
        return false;
      //访问完两棵树的当前结点后,置空让下一次循环弹出栈中元素(此处其实直接弹出元素也行)
      p1 = NULL;
      p2 = NULL;
    }
    else if(p1 != NULL || p2 != NULL)    //当前节点有一个为空
      return false;
    else
    {
      //弹出两个树的栈顶元素
      p1 = _sta1.top();
      p2 = _sta2.top();
      _sta1.pop();
      _sta2.pop();
    }
  }
  return true;
}
//递归判断两棵树是否相似
bool IsSemblable2(BiTree T1,BiTree T2)
{
  bool leftS = false,rightS = false;   //用来接受子树返回的信息
  if(T1 == NULL && T2 == NULL)    //两个结点都为空
    return true;
  else if(T1 == NULL || T2 == NULL)  //有一个结点不为空
    return false;
  else
  {
    int leftS = IsSemblable2(T1->lchild,T2->lchild);  //递归左子树
    int rightS = IsSemblable2(T1->rchild,T2->rchild);  //递归右子树
    return leftS && rightS ;  //返回两个子树的信息
  }
}

总结

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,谢谢大家对创新互联的支持。如果你想了解更多相关内容请查看下面相关链接


本文名称:判断两颗二叉树是否相似的两种方法
文章起源:http://myzitong.com/article/psssss.html