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

}

}