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    dc     e调用递归求二叉树镜像形状：   ad    b  e    c再次调用非递归求二叉树镜像形状（即镜像的镜像）:    a  b    dc     e*/以上就是武林技术频道小编给大家介绍的C++基于递归和非递归算法求二叉树镜像的方法，如若您想要学习更多的技术专业知识可点击进入js.Vevb.com。