C++基于递归和非递归算法求二叉树镜像的方法_网络技术

C++基于递归和非递归算法求二叉树镜像的方法

发布时间 - 2026-01-11 01:05:06 点击率：次

本文实例讲述了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 】

上一篇：什么是桥接模式？你可能还不知道

下一篇：阿里云建站教程：新手如何快速创建并发布网站？

相关栏目网站优化
网络推广
网络技术
AI营销

最新文章 Sublime怎么一键压缩JS代码 Su sublime如何在搜索中使用正则表达式 Sublime如何设置透明窗口效果 Su mysql如何设计商品表结构_mysql css属性背景图不显示怎么办_通过检查路如何使用Golang实现排序_Golan 农历闰月是怎么回事_为合回归年加一月调整塑造《刺客信条》艾吉奥传奇的编剧离开育碧 1英里等于多少公里 1mile和km的换 css grid布局中行和列是如何定义的 PS批量旋转和翻转图片，快速校正图片方向 C# Swagger UI自定义方法 C OPPO手机九宫格和全键盘怎么切换_OP Go语言如何实现用户登录注册_Golan 1节飞行速度多少公里每小时 1节是多少公纸嫁衣8千子树第五章庙门怎么开启庙门 Laravel 多行数据编辑表单中实现逐明日之后如何提升钓鱼等级明日之后提升钓支付宝怎样查年度账单_支付宝年度账单查看 C# 多线程UI更新Dispatcher

上一篇：什么是桥接模式？你可能还不知道

下一篇：阿里云建站教程：新手如何快速创建并发布网站？