C++ 二叉樹的鏡像實例詳解
更新時間：2017年06月06日 10:00:36 投稿：lqh
這篇文章主要介紹了C++ 二叉樹的鏡像實例詳解的相關(guān)資料,需要的朋友可以參考下
二叉樹的鏡像：將一個二叉樹的左右子樹，調(diào)換位置。即下圖的形式：
遞歸的思想是：
從根節(jié)點的左右子樹進行交換，然后以根節(jié)點的左子樹為根節(jié)點，而后以根節(jié)點的右結(jié)點為根節(jié)點，進行左右子樹交換。遇到空節(jié)點或葉節(jié)點直接返回。下面求二叉樹鏡像的函數(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);
}
非遞歸實現(xiàn)思想：
利用stack棧的FILO，即先進后出原則，將根節(jié)點先行壓入棧中，然后進入棧同時取棧頂結(jié)點并pop棧，然后交換左右子樹的結(jié)點，若根節(jié)點的左右子樹不為空，即壓入棧中，直到棧為空則停止。
下面是非遞歸實現(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);
}
}
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
相關(guān)文章
這篇文章主要介紹了C++ 中構(gòu)造函數(shù)的實例詳解的相關(guān)資料,希望通過本文能幫助到大家，讓大家理解掌握這部分內(nèi)容，需要的朋友可以參考下2021-09-09
c++中有2種getline函數(shù)，一種在頭文件 <istream> 中，是istream類的成員函數(shù)；另一種是在頭文件 <string> 中，是普通函數(shù)。這篇文章主要介紹了c++中的兩種getline用法,需要的朋友可以參考下2020-02-02
基于對話框程序中讓對話框捕獲WM_KEYDOWN消息的實現(xiàn)方法
下面我們將通過程序給大家演示基于對話框的應(yīng)用程序?qū)M_KEYDOWN消息的捕獲。需要的朋友可以參考下2013-05-05
這篇文章主要為大家詳細(xì)介紹了C++代碼實現(xiàn)逆波蘭式，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-11-11
這篇文章主要為大家詳細(xì)介紹了opencv利用鼠標(biāo)滑動畫出多彩的形狀，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下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ì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-05-05
Windows下sentry接入C/C++程序的詳細(xì)過程
sentry作為一個開源的軟件，發(fā)展至今，已經(jīng)非常成熟。它支持的平臺眾多，甚至于針對不同的工作者(后臺、前端、客戶端)都有相應(yīng)的內(nèi)容，這篇文章主要介紹了Windows下sentry接入C/C++程序,需要的朋友可以參考下2022-09-09
這篇文章主要為大家詳細(xì)介紹了C++的拷貝構(gòu)造函數(shù)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-03-03
這篇文章主要為大家詳細(xì)介紹了C語言單鏈表貪吃蛇小游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-02-02