- 相关推荐
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;
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