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

本文实例讲述了C++基于递归和非递归算法求二叉树镜像的方法。分享给大家供大家参考，具体如下：

#include 
#include 
#include 
using std::cout;
using std::cin;
using std::endl;
using std::queue;

typedef struct BTreeNode
{
  char elem;
  struct BTreeNode *pleft;
  struct BTreeNode *pright;
}BTreeNode;


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 ;
}

void get_bitree_mirror_leveltraverse(BTreeNode* proot)
{
  if(proot == NULL)
    return ;
  queue  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;
}

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