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

作者:kgmucom   在线用户:20
风之恋奇迹私服技术网是一家提供最新互联网编程技术网站

二叉树中的元素自上而下地放置在数组中,易于递归实现,其实容器用于存储前一个状态实现循环以创建二叉树,下面爱站技术频道就给大家介绍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++基于递归和非递归算法求二叉树镜像的方法,如若您想要学习更多的技术专业知识可点击进入js.aizhan.com。
提供最全面的奇迹sf开服版本和最新的奇迹私服开服技术信息,奇迹私服文库让每一位奇迹私服玩家找到自己需要的版本技术文章

上一篇:详谈C++的内存泄漏问题

下一篇:详解c++插入排序

请发表您的评论