/*求二叉樹鏡像 -- 采用遞歸和非遞歸方法經(jīng)調(diào)試可運(yùn)行源碼及分析如下：***/#include <stdlib.h>#include <iostream>#include <queue>using std::cout;using std::cin;using std::endl;using std::queue;/*二叉樹結(jié)點(diǎn)定義*/typedef struct BTreeNode{  char elem;  struct BTreeNode *pleft;  struct BTreeNode *pright;}BTreeNode;/*求二叉樹鏡像遞歸方式步驟：如果proot為NULL，則為空樹，返回；如果proot不為NULL，交換proot左右結(jié)點(diǎn)，然后分別求左右子樹的鏡像；*//*遞歸求二叉樹鏡像*/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 ;}/*非遞歸方式步驟如下：借助隊(duì)列首先，將根節(jié)點(diǎn)proot入隊(duì)；第一步：當(dāng)隊(duì)列非空時(shí)，獲取當(dāng)前層次的節(jié)點(diǎn)總數(shù)，即當(dāng)前隊(duì)列的長度；執(zhí)行第二步；第二步：按照當(dāng)前層的節(jié)點(diǎn)總數(shù)，出隊(duì)進(jìn)行遍歷節(jié)點(diǎn)，在遍歷時(shí)，    交換左右節(jié)點(diǎn)，如果左右節(jié)點(diǎn)存在，則入隊(duì)；    當(dāng)遍歷完當(dāng)前層所有節(jié)點(diǎn)時(shí)，遍歷下一層，執(zhí)行第一步。*/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();      //交換左右子節(jié)點(diǎn)      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 ;}/*初始化二叉樹根節(jié)點(diǎn)*/BTreeNode* btree_init(BTreeNode* &bt){  bt = NULL;  return bt;}/*先序創(chuàng)建二叉樹*/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);//初始化根節(jié)點(diǎn)  pre_crt_tree(bt);//創(chuàng)建二叉樹  cout << "先序遍歷輸出如下：" << endl;  cout << "調(diào)用鏡像函數(shù)前：" << endl;  pre_order_traverse(bt);  cout << endl;  get_bitree_mirror(bt);  cout << "遞歸調(diào)用鏡像函數(shù)后：" << endl;  pre_order_traverse(bt);  cout << endl;  cout << "非遞歸調(diào)用鏡像函數(shù)后：" << endl;  get_bitree_mirror_leveltraverse(bt);  pre_order_traverse(bt);  cout << endl;  system("pause");  return 0;}

/*運(yùn)行結(jié)果：a b c # # # d e # # #------以上為輸入-----------------以下為輸出-----------先序遍歷輸出如下：調(diào)用鏡像函數(shù)前：a b c d e遞歸調(diào)用鏡像函數(shù)后：a d e b c非遞歸調(diào)用鏡像函數(shù)后：a b c d e請(qǐng)按任意鍵繼續(xù). . .---------------------------------本例創(chuàng)建的二叉樹形狀：    a  b    dc     e調(diào)用遞歸求二叉樹鏡像形狀：   ad    b  e    c再次調(diào)用非遞歸求二叉樹鏡像形狀（即鏡像的鏡像）:    a  b    dc     e*/