您的位置：首页 > 编程技术 > C语言  >  判断两颗二叉树是否相似的两种方法

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

 更新时间：2020年4月25日 17:26  点击：1870

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

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

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

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

//层次遍历法判断两棵树是否相似
bool IsSemblable1(BiTree T1,BiTree T2)
{
  stack<BiTNode* > _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 ;  //返回两个子树的信息
  }
}

总结

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

[!--infotagslink--]

相关文章

  • C语言实现放烟花的程序

    这篇文章主要为大家详细介绍了C语言实现放烟花的程序，有音乐播放，文中示例代码介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们可以参考一下...2021-02-23

  • C语言中的字符（char）详细讲解

    本篇文章主要介绍C语言中char的知识,并附有代码实例,以便大家在学习的时候更好的理解,有需要的可以看一下...2020-04-25

  • JavaScript判断浏览器及其版本信息

    本篇文章主要分享了通过window.navigator来判断浏览器及其版本信息的实例代码。具有一定的参考价值，下面跟着小编一起来看下吧...2017-01-23

  • 详解如何将c语言文件打包成exe可执行程序

    这篇文章主要介绍了详解如何将c语言文件打包成exe可执行程序，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2021-02-25

  • 一个奇葩的最短的 IE 版本判断JS脚本

    使用 conditional comment 来判断 IE 的版本。嗯，是早早有人提出，但没有认真看代码。昨天刚好在看 CSS3 PIE 的时候看到，觉得是不是不靠谱。今天看到 Paul Irish 也提起，那么，推荐一下吧。这是作者博客上写的：复制代码 代码...2014-05-31

  • c# 判断是否为空然后赋值的4种实现方法

    下面小编就为大家分享一篇c# 判断是否为空然后赋值的4种实现方法，具有很好的参考价值，希望对大家有所帮助。一起跟随小编过来看看吧...2020-06-25

  • C语言中free函数的使用详解

    free函数是释放之前某一次malloc函数申请的空间，而且只是释放空间，并不改变指针的值。下面我们就来详细探讨下...2020-04-25

  • C语言中计算正弦的相关函数总结

    这篇文章主要介绍了C语言中计算正弦的相关函数总结,包括正弦和双曲线正弦以及反正弦的函数,需要的朋友可以参考下...2020-04-25

  • 详解C语言中的rename()函数和remove()函数的使用方法

    这篇文章主要介绍了详解C语言中的rename()函数和remove()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25

  • C语言中求和、计算平均值、方差和标准差的实例

    这篇文章主要介绍了C语言中求和、计算平均值、方差和标准差的实例，具有很好的参考价值，希望对大家有所帮助。一起跟随小编过来看看吧...2020-12-10

  • MySql存储过程之逻辑判断和条件控制

    具体详情请看下文小编给大家带来的知识点。同编写程序类似，存储过程中也有对应的条件判断，功能类似于if、switch。在MySql里面对应的是IF和CASE1、IF判断IF判断的格式是这样的：IF expression THEN commands [ELSEIF ex...2015-10-21

  • PHP中empty和isset对于参数结构的判断及empty()和isset()的区别

    废话不多说了，直接给大家贴代码了。<&#63;php class test{} $a1 = null; $a2 = ""; //$a3 = $a4 = 0; $a5 = '0'; $a6 = false; $a7 = array(); //var $a8; $a9 = new test(); for ($i=1; $i <=9 ; $i++) {...2015-11-24

  • java正则表达式判断前端参数修改表中另一个字段的值

    这篇文章主要介绍了java正则表达式判断前端参数修改表中另一个字段的值,需要的朋友可以参考下...2021-05-07

  • C#判断一个字符串是否是数字或者含有某个数字的方法

    这篇文章主要介绍了C#判断一个字符串是否是数字或者含有某个数字的方法，本文给大家介绍的非常详细，具有一定的参考借鉴价值,需要的朋友可以参考下...2020-06-25

  • C语言的基本语法详解

    本篇文章主要讲解C语言 基本语法,这里提供简单的示例和代码来详细讲解C语言的基本语法，开始学习C语言的朋友可以看一下，希望能够给你带来帮助...2021-09-18

  • C#获得程序的根目录以及判断文件是否存在的实例讲解

    今天小编大家分享一篇C#获得程序的根目录以及判断文件是否存在的实例讲解，具有很好的参考价值，希望对大家有所帮助。一起跟随小编过来看看吧...2020-06-25

  • 从PHP $_SERVER相关参数判断是否支持Rewrite模块

    如果是http://www.jb51.net/p1141.html形式的URL，可通过$_SERVER['REQUEST_URI']和$_SERVER['QUERY_STRING']值的区别来分析，最主要是如果页面是通过重定向会产生$_SERVER['REDIRECT_QUERY_STRING']和$_SERVER['REDIREC...2013-10-04

  • JavaScript判断DIV内容是否为空的方法

    整体思路是这样的：判断div内部是否为空，如果为空，给出无数据提示；否则显示正常页面，下面给大家分享js判断div内容是否为空的方法，对判断div内容是否为空的相关知识感兴趣的朋友一起学习吧...2016-02-01

  • C语言中send()函数和sendto()函数的使用方法

    这篇文章主要介绍了C语言中send()函数和sendto()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25

  • toString.call()通用的判断数据类型方法示例

    这篇文章主要给大家介绍了关于toString.call()通用的判断数据类型方法的相关资料，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2020-08-29