這篇文章將為大家詳細(xì)講解有關(guān)C++中基于遞歸和非遞歸算法如何求二叉樹(shù)鏡像，小編覺(jué)得挺實(shí)用的，因此分享給大家做個(gè)參考，希望大家閱讀完這篇文章后可以有所收獲。

創(chuàng)新互聯(lián)網(wǎng)站建設(shè)由有經(jīng)驗(yàn)的網(wǎng)站設(shè)計(jì)師、開(kāi)發(fā)人員和項(xiàng)目經(jīng)理組成的專業(yè)建站團(tuán)隊(duì)，負(fù)責(zé)網(wǎng)站視覺(jué)設(shè)計(jì)、用戶體驗(yàn)優(yōu)化、交互設(shè)計(jì)和前端開(kāi)發(fā)等方面的工作，以確保網(wǎng)站外觀精美、網(wǎng)站設(shè)計(jì)制作、網(wǎng)站制作易于使用并且具有良好的響應(yīng)性。

具體如下：

/*求二叉樹(shù)鏡像 -- 采用遞歸和非遞歸方法
經(jīng)調(diào)試可運(yùn)行源碼及分析如下：
***/
#include 
#include 
#include 
using std::cout;
using std::cin;
using std::endl;
using std::queue;
/*二叉樹(shù)結(jié)點(diǎn)定義*/
typedef struct BTreeNode
{
  char elem;
  struct BTreeNode *pleft;
  struct BTreeNode *pright;
}BTreeNode;
/*
求二叉樹(shù)鏡像
遞歸方式步驟：
如果proot為NULL，則為空樹(shù)，返回；
如果proot不為NULL，交換proot左右結(jié)點(diǎn)，然后分別求左右子樹(shù)的鏡像；
*/
/*遞歸求二叉樹(shù)鏡像*/
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ǎng)度；執(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  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 ;
}
/*初始化二叉樹(shù)根節(jié)點(diǎn)*/
BTreeNode* btree_init(BTreeNode* &bt)
{
  bt = NULL;
  return bt;
}
/*先序創(chuàng)建二叉樹(shù)*/
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)建二叉樹(shù)
  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)建的二叉樹(shù)形狀：
    a
  b    d
c     e
調(diào)用遞歸求二叉樹(shù)鏡像形狀：
   a
d    b
  e    c
再次調(diào)用非遞歸求二叉樹(shù)鏡像形狀（即鏡像的鏡像）:
    a
  b    d
c     e
*/

關(guān)于“C++中基于遞歸和非遞歸算法如何求二叉樹(shù)鏡像”這篇文章就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，使各位可以學(xué)到更多知識(shí)，如果覺(jué)得文章不錯(cuò)，請(qǐng)把它分享出去讓更多的人看到。