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語言實(shí)現(xiàn)簡單圖書管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)圖書管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-01-01
本文在介紹C++使用的對(duì)象模型之前，先介紹了2種對(duì)象模型：簡單對(duì)象模型（a simple object model）和表格驅(qū)動(dòng)對(duì)象模型（a table-driven object model），這樣介紹對(duì)后面的內(nèi)容更有幫助，有需要的小伙伴們可以參考學(xué)習(xí)。2016-08-08
c++ 單線程實(shí)現(xiàn)同時(shí)監(jiān)聽多個(gè)端口
這篇文章主要介紹了c++ 單線程實(shí)現(xiàn)同時(shí)監(jiān)聽多個(gè)端口的方法，幫助大家更好的理解和學(xué)習(xí)使用c++，感興趣的朋友可以了解下2021-03-03
關(guān)鍵字const用來定義只讀變量,被const定義的變量它的值是不允許改變的,即不允許給它重新賦值,即使是賦相同的值也不可以,下面這篇文章主要給大家介紹了關(guān)于C語言中Const關(guān)鍵字的相關(guān)資料,需要的朋友可以參考下2022-02-02
C++11標(biāo)準(zhǔn)新引入了一種類模板,命名為 tuple(中文可直譯為元組),下面這篇文章主要給大家介紹了關(guān)于C++中神奇的tuple詳解使用技巧及實(shí)例解析的相關(guān)資料,需要的朋友可以參考下2024-01-01![C++程序中main（int argc, char *argv[]）函數(shù)的參數(shù)意義](http://img.jbzj.com/images/xgimg/bcimg5.png)
C++程序中main（int argc, char *argv[]）函數(shù)的參數(shù)意義
這篇文章主要介紹了C++程序中main（int argc, char *argv[]）函數(shù)的參數(shù)意義,本文給大家介紹的非常詳細(xì)，具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2018-09-09
基于epoll的多線程網(wǎng)絡(luò)服務(wù)程序設(shè)計(jì)
這篇文章主要為大家詳細(xì)介紹了基于epoll的多線程網(wǎng)絡(luò)服務(wù)程序設(shè)計(jì)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-08-08
詳解C語言中的fopen()函數(shù)和fdopen()函數(shù)
這篇文章主要介紹了詳解C語言中的fopen()函數(shù)和fdopen()函數(shù),注意其之間指針功能相關(guān)的區(qū)別,需要的朋友可以參考下2015-08-08
這篇文章主要為大家詳細(xì)介紹了C語言的程序環(huán)境與預(yù)處理，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-02-02
這篇文章主要介紹了C++中淺拷貝與深拷貝的詳解及其作用介紹，本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-09-09