本文实例讲述了C++基于递归和非递归算法判定两个二叉树结构是否完全相同。分享给大家供大家参考，具体如下：

/*两个二叉树结构是否相同(结构和数据都相同) -- 递归和非递归方法
经调试可运行源码及分析如下：
***/
#include <stdlib.h>
#include <iostream>
#include <queue>
using std::cout;
using std::cin;
using std::endl;
using std::queue;
/*二叉树结点定义*/
typedef struct BTreeNode
{
  char elem;
  struct BTreeNode *pleft;
  struct BTreeNode *pright;
}BTreeNode;
/*初始化二叉树节点*/
BTreeNode* btree_init(BTreeNode* &bt)
{
  bt = NULL;
  return bt;
}
/*先序创建二叉树*/
void pre_crt_tree(BTreeNode* &bt)
{
  char ch;
  cin >> ch;
  if (ch == '#')
  {
    bt = NULL;
  }
  else
  {
    bt = new BTreeNode;
    bt->elem = ch;
    pre_crt_tree(bt->pleft);
    pre_crt_tree(bt->pright);
  }
}
/*
递归方式:
如果两个二叉树proot都为空树，则自然相同，返回true；
如果两个二叉树proot一个为空树，另一个不为空树，则不相同，返回false；
如果两个二叉树的数据不相等，返回false;
如果两个二叉树都不为空树，则需要分别比较左右子树后，根据比较结果共同判定，只要有一个为false，则返回false。
*/
/*递归判断两个二叉树是否相等(结构和数据)*/
bool bitree_compare(BTreeNode* proot1, BTreeNode* proot2)
{
  if (proot1 == NULL && proot2 == NULL)//都为空
    return true;
  if((proot1 != NULL && proot2 == NULL) ||
    (proot1 == NULL && proot2 != NULL))//一个空，一个非空
    return false;
  /*比较元素*/
  if(proot1->elem != proot2->elem)
    return false;
  bool left_compare = bitree_compare(proot1->pleft, proot2->pleft);
  bool right_compare = bitree_compare(proot1->pright, proot2->pright);
  return (left_compare && right_compare);
}
/*
非递归方式
借助队列实现
实现算法：
首先将给定根节点proot1和proot2都入队
第一步：当两个队列未空时，分别获取两个树的当前层次中节点总数（即当前队列中节点个数），
    先比较节点个数是否相同，如果不相同，则两个树自然不同；
    如果节点个数相同，需要出队进行比较(数据也要比较)。如果有一个队列未空，则退出比较。
第二步：如果有一个队列未空，则清空队列并返回不同。
*/
/*非递归方式判断两个二叉树是否相等（仅仅结构）*/
bool bitree_compare_leveltraverse(BTreeNode* proot1, BTreeNode* proot2)
{
  if (proot1 == NULL && proot2 == NULL)//都为空
    return true;
  queue <BTreeNode*> que1;
  queue <BTreeNode*> que2;
  que1.push(proot1);
  que2.push(proot2);
  int cur_level_nodes_num1 = 0;
  int cur_level_nodes_num2 = 0;
  bool flag = true;
  while (!que1.empty() && !que2.empty())
  {
    cur_level_nodes_num1 = que1.size();
    cur_level_nodes_num2 = que2.size();
    //节点数目不一样时flag设为false，退出循环
    if (cur_level_nodes_num1 != cur_level_nodes_num2)
    {
      flag = false;
      break;
    }
    int cur_level_node_count1 = 0;
    int cur_level_node_count2 = 0;
    while (cur_level_node_count1 < cur_level_nodes_num1 &&
        cur_level_node_count2 < cur_level_nodes_num2)
    {
      ++cur_level_node_count1;
      ++cur_level_node_count2;
      proot1 = que1.front();
      que1.pop();
      proot2 = que2.front();
      que2.pop();
      /*元素数据比较*/
      if(proot1->elem != proot2->elem)
      {
        flag = false;
        break;
      }
      //判断左右孩子是否相同，不同肯定结构不相同，提前break
      if( proot1->pleft == NULL && proot2->pleft != NULL  ||
        proot1->pleft != NULL && proot2->pleft == NULL  ||
        proot1->pright == NULL && proot2->pright != NULL ||
        proot1->pright != NULL && proot2->pright == NULL)
      {
        flag = false;
        break;
      }
      /*下一层的节点入队*/
      if(proot1->pleft)
        que1.push(proot1->pleft);
      if(proot1->pright)
        que1.push(proot1->pright);
      if(proot2->pleft)
        que2.push(proot2->pleft);
      if(proot2->pright)
        que2.push(proot2->pright);
    }
    if(flag == false)
      break;
  }
  if(flag == false)
  {
    while(!que1.empty())
      que1.pop();
    while(!que2.empty())
      que2.pop();
    cout << "非递归：reslut is false." << endl;
    return false;
  }else
  {
    cout << "非递归：reslut is true." << endl;
    return true;
  }
  return true;
}
int main()
{
  BTreeNode *bt1;
  BTreeNode* bt2;
  bool flag;
  btree_init(bt1);//初始化根节点
  btree_init(bt2);//初始化根节点
  cout << "creat 1th tree:" << endl;
  pre_crt_tree(bt1);//创建二叉树
  cout << "creat 2th tree:" << endl;
  pre_crt_tree(bt2);//创建二叉树
  /*递归测试*/
  flag = bitree_compare(bt1, bt2);
  if(flag == true)
    cout<< "递归：result is true." << endl;
  else
    cout << "递归：result is false." << endl;
  /*非递归测试*/
  bitree_compare_leveltraverse(bt1, bt2);
  system("pause");
  return 0;
}

/*
测试结果如下：
creat 1th tree:
a b c # # # d e # # f # g # #
creat 2th tree:
a b c # # # d e # # f # g # #
递归：result is true.
非递归：reslut is true.
请按任意键继续. . .
------------------分界线-----------------------
creat 1th tree:
a b c # # # d # #
creat 2th tree:
a b c # # # x # #
递归：result is false.
非递归：reslut is false.
请按任意键继续. . .
本例创建的二叉树形状：
a b c # # # d e # # f # g # # 如下：
    a
  b    d
c     e  f
       g
a b c # # # d # # 如下：
    a
  b    d
c
a b c # # # x # # 如下：
    a
  b    x
c
*/

希望本文所述对大家C++程序设计有所帮助。

# C++  # 递归  # 非递归  # 算法  # 判定  # 二叉树  # 完全相同  # C++ 非递归实现二叉树的前中后序遍历  # C++ 数据结构二叉树（前序/中序/后序递归、非递归遍历）  # C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法  # C++基于递归和非递归算法求二叉树镜像的方法  # C++非递归队列实现二叉树的广度优先遍历  # C++非递归建立二叉树实例  # C++二叉树的前序中序后序非递归实现方法详细讲解  # 为空  # 子树  # 请按  # 有一个  # 都不  # 也要  # 设为  # 给大家  # 第二步  # 所述  # 程序设计  # 清空  # 则需  # 本例  # 下一层  # 只要有  # 不相等 

相关栏目： 【 网站优化151355 】 【 网络推广146373 】 【 网络技术251813 】 【 AI营销90571 】

相关推荐： Laravel Sail是什么_基于Docker的Laravel本地开发环境Sail入门  如何在IIS7中新建站点？详细步骤解析  Laravel如何使用Blade模板引擎？（完整语法和示例）  Laravel如何使用查询构建器？（Query Builder高级用法）  EditPlus中的正则表达式 实战(1)  Laravel怎么做数据加密_Laravel内置Crypt门面的加密与解密功能  如何在万网开始建站？分步指南解析  如何快速查询网址的建站时间与历史轨迹？  EditPlus中的正则表达式 实战(4)  如何用AI一键生成爆款短视频文案？小红书AI文案写作指令【教程】  BootStrap整体框架之基础布局组件  Laravel如何实现数据库事务？（DB Facade示例）  如何快速生成凡客建站的专业级图册？  使用Dockerfile构建java web环境  Laravel怎么使用Blade模板引擎_Laravel模板继承与Component组件复用【手册】  阿里云高弹*务器配置方案｜支持分布式架构与多节点部署  如何在阿里云ECS服务器部署织梦CMS网站？  如何快速查询域名建站关键信息？  如何自己制作一个网站链接,如何制作一个企业网站，建设网站的基本步骤有哪些？  如何用花生壳三步快速搭建专属网站？  php做exe能调用系统命令吗_执行cmd指令实现方式【详解】  LinuxCD持续部署教程_自动发布与回滚机制  Laravel怎么实现微信登录_Laravel Socialite第三方登录集成  Windows10如何更改计算机工作组_Win10系统属性修改Workgroup  edge浏览器无法安装扩展 edge浏览器插件安装失败【解决方法】  移动端脚本框架Hammer.js  如何在景安服务器上快速搭建个人网站？  bing浏览器学术搜索入口_bing学术文献检索地址  夸克浏览器网页跳转延迟怎么办 夸克浏览器跳转优化  猎豹浏览器开发者工具怎么打开 猎豹浏览器F12调试工具使用【前端必备】  车管所网站制作流程,交警当场开简易程序处罚决定书，在交警网站查询不到怎么办？  香港服务器租用每月最低只需15元？  Laravel安装步骤详细教程_Laravel环境搭建指南  Mybatis 中的insertOrUpdate操作  网站视频制作书签怎么做,ie浏览器怎么将网站固定在书签工具栏？  如何在IIS7上新建站点并设置安全权限？  香港服务器建站指南：免备案优势与SEO优化技巧全解析  实例解析Array和String方法  linux top下的 minerd 木马清除方法  如何快速上传自定义模板至建站之星？  Laravel与Inertia.js怎么结合_使用Laravel和Inertia构建现代单页应用  Laravel中的Facade(门面)到底是什么原理  如何在VPS电脑上快速搭建网站？  Laravel如何发送邮件_Laravel Mailables构建与发送邮件的简明教程  Laravel怎么自定义错误页面_Laravel修改404和500页面模板  Android自定义listview布局实现上拉加载下拉刷新功能  如何在阿里云高效完成企业建站全流程？  详解Nginx + Tomcat 反向代理 如何在高效的在一台服务器部署多个站点  Laravel如何为API生成Swagger或OpenAPI文档  Laravel怎么集成Vue.js_Laravel Mix配置Vue开发环境