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