- 相關推薦
C++二叉樹的鏡像實例
在計算機科學中，二叉樹是每個節(jié)點最多有兩個子樹的樹結構。二叉樹常被用于實現(xiàn)二叉查找樹和二叉堆。下面是小編分享的C++二叉樹的鏡像實例，一起來看一下吧。
遞歸的思想是：
從根節(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é)點先行壓入棧中，然后進入棧同時取棧頂結點并pop棧，然后交換左右子樹的結點，若根節(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);
}
}
【C++二叉樹的鏡像實例】相關文章：
判斷二叉樹是否為完全二叉樹的實例07-16
C++選擇排序算法實例09-26
C++類中的繼承實例詳解07-05
C++插入排序算法實例08-26
C++冒泡排序算法實例詳解06-09
C++歸并排序算法實例09-07
C++畫正弦線實例代碼11-10
C與C++之間相互調用的實例07-07
C語言中二叉樹的鏈式存儲實例分析09-13