- 相關(guān)推薦
C++二叉樹(shù)的鏡像實(shí)例
在計(jì)算機(jī)科學(xué)中，二叉樹(shù)是每個(gè)節(jié)點(diǎn)最多有兩個(gè)子樹(shù)的樹(shù)結(jié)構(gòu)。二叉樹(shù)常被用于實(shí)現(xiàn)二叉查找樹(shù)和二叉堆。下面是小編分享的C++二叉樹(shù)的鏡像實(shí)例，一起來(lái)看一下吧。
遞歸的思想是：
從根節(jié)點(diǎn)的左右子樹(shù)進(jìn)行交換，然后以根節(jié)點(diǎn)的左子樹(shù)為根節(jié)點(diǎn)，而后以根節(jié)點(diǎn)的右結(jié)點(diǎn)為根節(jié)點(diǎn)，進(jìn)行左右子樹(shù)交換。遇到空節(jié)點(diǎn)或葉節(jié)點(diǎn)直接返回。下面求二叉樹(shù)鏡像的函數(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棧，然后交換左右子樹(shù)的結(jié)點(diǎn)，若根節(jié)點(diǎn)的左右子樹(shù)不為空，即壓入棧中，直到棧為空則停止。
下面是非遞歸實(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);
}
}
【C++二叉樹(shù)的鏡像實(shí)例】相關(guān)文章：
判斷二叉樹(shù)是否為完全二叉樹(shù)的實(shí)例07-16
C++選擇排序算法實(shí)例09-26
C++類中的繼承實(shí)例詳解07-05
C++插入排序算法實(shí)例08-26
C++冒泡排序算法實(shí)例詳解06-09
C++歸并排序算法實(shí)例09-07