C++二叉樹的鏡像實例

　　在計算機科學中，二叉樹是每個節(jié)點最多有兩個子樹的樹結構。二叉樹常被用于實現二叉查找樹和二叉堆。下面是小編分享的C++二叉樹的鏡像實例，一起來看一下吧。

　　遞歸的思想是：

　　從根節(jié)點的左右子樹進行交換，然后以根節(jié)點的左子樹為根節(jié)點，而后以根節(jié)點的右結點為根節(jié)點，進行左右子樹交換。遇到空節(jié)點或葉節(jié)點直接返回。下面求二叉樹鏡像的函數代碼實現：

　　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);

　　}

　　非遞歸實現思想：

　　利用stack棧的FILO，即先進后出原則，將根節(jié)點先行壓入棧中，然后進入棧同時取棧頂結點并pop棧，然后交換左右子樹的結點，若根節(jié)點的左右子樹不為空，即壓入棧中，直到棧為空則停止。

　　下面是非遞歸實現代碼：

　　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++二叉樹的鏡像實例】相關文章：

判斷二叉樹是否為完全二叉樹的實例02-08

C++選擇排序算法實例02-25

C++冒泡排序算法實例詳解10-13

C++插入排序算法實例11-22

C++畫正弦線實例代碼03-10

C++類中的繼承實例詳解01-25

C++歸并排序算法實例02-09

C與C++之間相互調用的實例09-08

C與C++之間相互調用的實例方法01-23