C++二叉樹的映象例項

在計算機科學中，二叉樹是每個節點最多有兩個子樹的樹結構。二叉樹常被用於實現二叉查詢樹和二叉堆。下面是小編分享的C++二叉樹的`映象例項，一起來看一下吧。

　　遞迴的思想是：

從根節點的左右子樹進行交換，然後以根節點的左子樹為根節點，而後以根節點的右結點為根節點，進行左右子樹交換。遇到空節點或葉節點直接返回。下面求二叉樹映象的函式程式碼實現：

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，即先進後出原則，將根節點先行壓入棧中，然後進入棧同時取棧頂結點並pop棧，然後交換左右子樹的結點，若根節點的左右子樹不為空，即壓入棧中，直到棧為空則停止。

下面是非遞迴實現程式碼：

template<class T>

void MirroTree_NoR(TreeNode<T>* root)

{

stack<TreeNode<T>*> s;

(root);

while (())

{

TreeNode<T>* Top = ();

if (Top->_left != NULL || Top->_right != NULL)

{

TreeNode<T>* temp = Top->_left;

Top->_left = Top->_right;

Top->_right = temp;

}

if (Top->_left != NULL)

(Top->_left);

if (Top->_right != NULL)

(Top->_right);

}

}