快捷導(dǎo)航

C++ 二叉樹的鏡像實(shí)例詳解

更新時(shí)間：2017年06月06日 10:00:36 投稿：lqh

這篇文章主要介紹了C++ 二叉樹的鏡像實(shí)例詳解的相關(guān)資料,需要的朋友可以參考下

二叉樹的鏡像：將一個(gè)二叉樹的左右子樹，調(diào)換位置。即下圖的形式：

遞歸的思想是：

從根節(jié)點(diǎn)的左右子樹進(jìn)行交換，然后以根節(jié)點(diǎn)的左子樹為根節(jié)點(diǎn)，而后以根節(jié)點(diǎn)的右結(jié)點(diǎn)為根節(jié)點(diǎn)，進(jìn)行左右子樹交換。遇到空節(jié)點(diǎn)或葉節(jié)點(diǎn)直接返回。下面求二叉樹鏡像的函數(shù)代碼實(shí)現(xiàn)：

template<class T> 
void MirroTree(TreeNode<T> * root) 
{ 
  if (root == NULL) 
    return; 
  if (root->_left == NULL && root->_right == NULL) 
    return; 
  else 
  { 
    TreeNode<T>* temp = root->_left; 
    root->_left = root->_right; 
    root->_right = temp; 
  } 
  MirroTree(root->_left); 
  MirroTree(root->_right); 
}

非遞歸實(shí)現(xiàn)思想：

利用stack棧的FILO，即先進(jìn)后出原則，將根節(jié)點(diǎn)先行壓入棧中，然后進(jìn)入棧同時(shí)取棧頂結(jié)點(diǎn)并pop棧，然后交換左右子樹的結(jié)點(diǎn)，若根節(jié)點(diǎn)的左右子樹不為空，即壓入棧中，直到棧為空則停止。

下面是非遞歸實(shí)現(xiàn)代碼：

template<class T> 
void MirroTree_NoR(TreeNode<T>* root) 
{ 
  stack<TreeNode<T>*> s; 
  s.push(root); 
  while (s.size()) 
  { 
    TreeNode<T>* Top = s.top(); 
    if (Top->_left != NULL || Top->_right != NULL) 
    { 
      TreeNode<T>* temp = Top->_left; 
      Top->_left = Top->_right; 
      Top->_right = temp; 
    } 
    if (Top->_left != NULL) 
      s.push(Top->_left); 
    if (Top->_right != NULL) 
      s.push(Top->_right); 
  } 
}

感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！

您可能感興趣的文章:

相關(guān)文章

C++中的構(gòu)造函數(shù)詳解
這篇文章主要介紹了C++ 中構(gòu)造函數(shù)的實(shí)例詳解的相關(guān)資料,希望通過本文能幫助到大家，讓大家理解掌握這部分內(nèi)容，需要的朋友可以參考下
2021-09-09
c++中的兩種getline用法詳解
c++中有2種getline函數(shù)，一種在頭文件 <istream> 中，是istream類的成員函數(shù)；另一種是在頭文件 <string> 中，是普通函數(shù)。這篇文章主要介紹了c++中的兩種getline用法,需要的朋友可以參考下
2020-02-02
基于對(duì)話框程序中讓對(duì)話框捕獲WM_KEYDOWN消息的實(shí)現(xiàn)方法
下面我們將通過程序給大家演示基于對(duì)話框的應(yīng)用程序?qū)M_KEYDOWN消息的捕獲。需要的朋友可以參考下
2013-05-05
C++代碼實(shí)現(xiàn)逆波蘭式
這篇文章主要為大家詳細(xì)介紹了C++代碼實(shí)現(xiàn)逆波蘭式，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2020-11-11
opencv利用鼠標(biāo)滑動(dòng)畫出多彩的形狀
這篇文章主要為大家詳細(xì)介紹了opencv利用鼠標(biāo)滑動(dòng)畫出多彩的形狀，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2020-07-07
C語言中操作utmp文件的相關(guān)函數(shù)用法
這篇文章主要介紹了C語言中操作utmp文件的相關(guān)函數(shù)用法,包括getutent()函數(shù)和setutent()函數(shù)以及endutent()函數(shù),需要的朋友可以參考下
2015-08-08
C++ 標(biāo)準(zhǔn)模板庫 STL 順序容器詳解
這篇文章主要介紹了C++ 標(biāo)準(zhǔn)模板庫 STL 順序容器詳解,本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下
2021-05-05
Windows下sentry接入C/C++程序的詳細(xì)過程
sentry作為一個(gè)開源的軟件，發(fā)展至今，已經(jīng)非常成熟。它支持的平臺(tái)眾多，甚至于針對(duì)不同的工作者(后臺(tái)、前端、客戶端)都有相應(yīng)的內(nèi)容，這篇文章主要介紹了Windows下sentry接入C/C++程序,需要的朋友可以參考下
2022-09-09
C++的拷貝構(gòu)造函數(shù)你了解嗎
這篇文章主要為大家詳細(xì)介紹了C++的拷貝構(gòu)造函數(shù)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助
2022-03-03
C語言單鏈表貪吃蛇小游戲
這篇文章主要為大家詳細(xì)介紹了C語言單鏈表貪吃蛇小游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2020-02-02