本文实例讲述了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;
/*
求二叉树镜像
递归方式步骤：
如果proot为NULL，则为空树，返回；
如果proot不为NULL，交换proot左右结点，然后分别求左右子树的镜像；
*/
/*递归求二叉树镜像*/
void get_bitree_mirror(BTreeNode* proot)
{
  if (proot == NULL)
    return ;
  BTreeNode* temp_node = proot->pleft;
  proot->pleft = proot->pright;
  proot->pright = temp_node;
  get_bitree_mirror(proot->pleft);
  get_bitree_mirror(proot->pright);
  return ;
}
/*
非递归方式步骤如下：
借助队列
首先，将根节点proot入队；
第一步：当队列非空时，获取当前层次的节点总数，即当前队列的长度；执行第二步；
第二步：按照当前层的节点总数，出队进行遍历节点，在遍历时，
    交换左右节点，如果左右节点存在，则入队；
    当遍历完当前层所有节点时，遍历下一层，执行第一步。
*/
void get_bitree_mirror_leveltraverse(BTreeNode* proot)
{
  if(proot == NULL)
    return ;
  queue <BTreeNode*> que;
  que.push(proot);
  int level_nodes_number = 0;
  while (!que.empty())//层次遍历
  {
    level_nodes_number = que.size();
    int level_count = 0;
    while (level_count < level_nodes_number)
    {
      ++level_count;
      proot = que.front();
      que.pop();
      //交换左右子节点
      BTreeNode* temp_node = proot->pleft;
      proot->pleft = proot->pright;
      proot->pright = temp_node;
      if(proot->pleft != NULL)
        que.push(proot->pleft);
      if(proot->pright != NULL)
        que.push(proot->pright);
    }
  }
  return ;
}
/*初始化二叉树根节点*/
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);
  }
}
/*先序遍历*/
void pre_order_traverse(BTreeNode* proot)
{
  if(proot == NULL)
    return;
  cout<< proot->elem << " ";
  pre_order_traverse(proot->pleft);
  pre_order_traverse(proot->pright);
  return;
}
int main()
{
  int tree_node_number = 0;
  BTreeNode *bt;
  btree_init(bt);//初始化根节点
  pre_crt_tree(bt);//创建二叉树
  cout << "先序遍历输出如下：" << endl;
  cout << "调用镜像函数前：" << endl;
  pre_order_traverse(bt);
  cout << endl;
  get_bitree_mirror(bt);
  cout << "递归调用镜像函数后：" << endl;
  pre_order_traverse(bt);
  cout << endl;
  cout << "非递归调用镜像函数后：" << endl;
  get_bitree_mirror_leveltraverse(bt);
  pre_order_traverse(bt);
  cout << endl;
  system("pause");
  return 0;
}

/*
运行结果：
a b c # # # d e # # #
------以上为输入-----------
------以下为输出-----------
先序遍历输出如下：
调用镜像函数前：
a b c d e
递归调用镜像函数后：
a d e b c
非递归调用镜像函数后：
a b c d e
请按任意键继续. . .
---------------------------------
本例创建的二叉树形状：
    a
  b    d
c     e
调用递归求二叉树镜像形状：
   a
d    b
  e    c
再次调用非递归求二叉树镜像形状（即镜像的镜像）:
    a
  b    d
c     e
*/

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

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

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

相关推荐： 如何将凡科建站内容保存为本地文件？  lovemo网页版地址 lovemo官网手机登录  矢量图网站制作软件,用千图网的一张矢量图做公司app首页，该网站并未说明版权等问题，这样做算不算侵权？应该如何解决？  HTML5空格和margin有啥区别_空格与外边距的使用场景【说明】  制作ppt免费网站有哪些,有哪些比较好的ppt模板下载网站？  详解Huffman编码算法之Java实现  Laravel如何使用Sanctum进行API认证？（SPA实战）  简历没回改：利用AI润色让你的文字更专业  Laravel的路由模型绑定怎么用_Laravel Route Model Binding简化控制器逻辑  百度输入法ai组件怎么删除 百度输入法ai组件移除工具  如何在建站之星绑定自定义域名？  大连 网站制作,大连天途有线官网？  Windows驱动无法加载错误解决方法_驱动签名验证失败处理步骤  Laravel中间件如何使用_Laravel自定义中间件实现权限控制  Laravel storage目录权限问题_Laravel文件写入权限设置  猪八戒网站制作视频,开发一个猪八戒网站，大约需要多少？或者自己请程序员，需要什么程序员，多少程序员能完成？  如何在服务器上三步完成建站并提升流量？  简单实现Android文件上传  香港服务器网站测试全流程：性能评估、SEO加载与移动适配优化  北京网站制作公司哪家好一点,北京租房网站有哪些？  html5如何实现懒加载图片_ intersectionobserver api用法【教程】  laravel怎么实现图片的压缩和裁剪_laravel图片压缩与裁剪方法  Laravel如何使用.env文件管理环境变量？（最佳实践）  专业商城网站制作公司有哪些,pi商城官网是哪个？  Laravel怎么集成Log日志记录_Laravel单文件与每日日志配置及自定义通道【详解】  实例解析angularjs的filter过滤器  大连网站制作费用,大连新青年网站，五年四班里的视频怎样下载啊？  Laravel怎么使用Collection集合方法_Laravel数组操作高级函数pluck与map【手册】  JavaScript常见的五种数组去重的方式  Laravel怎么实现软删除SoftDeletes_Laravel模型回收站功能与数据恢复【步骤】  laravel怎么用DB facade执行原生SQL查询_laravel DB facade原生SQL执行方法  如何用狗爹虚拟主机快速搭建网站？  JS碰撞运动实现方法详解  制作网站软件推荐手机版,如何制作属于自己的手机网站app应用？  javascript中对象的定义、使用以及对象和原型链操作小结  Laravel中的withCount方法怎么高效统计关联模型数量  西安专业网站制作公司有哪些,陕西省建行官方网站？  Laravel如何使用withoutEvents方法临时禁用模型事件  Laravel如何使用Seeder填充数据_Laravel模型工厂Factory批量生成测试数据【方法】  Laravel如何处理JSON字段的查询和更新_Laravel JSON列操作与查询技巧  如何快速生成专业多端适配建站电话？  微信公众帐号开发教程之图文消息全攻略  Laravel如何使用Telescope进行调试？（安装和使用教程）  Laravel如何使用查询构建器？（Query Builder高级用法）  详解vue.js组件化开发实践  node.js报错：Cannot find module 'ejs'的解决办法  北京网站制作的公司有哪些,北京白云观官方网站？  大连网站制作公司哪家好一点,大连买房网站哪个好？  如何在阿里云域名上完成建站全流程？  Laravel如何实现API速率限制？（Rate Limiting教程）