求一颗二叉树的镜像
程序员文章站
2024-03-12 12:00:20
...
二叉树的镜像,通俗来讲就是镜子中所呈的像,左右颠倒。如图就是一个简单的二叉树镜像图。
二叉树镜像的过程
从图中可以看出,这棵树的根节点相同,但它们的左右两个子节点交换了位置。因此,我们不妨先交换根节点的两个子节点,就得到图中的第二颗树。
交换根节点的两个子节点后,我们发现值为3,2的节点的子节点仍然保持不变,因此我们还需要交换这两个节点的左右子节点。交换完之后就分别得到图中的第三、四颗树。做完这两次交换之后,就已经遍历完这颗树了,此时交换完之后的二叉树就是原树的镜像。
#include <iostream>
using namespace std;
template<class T>
struct BinaryTreeNode
{
BinaryTreeNode(const T data)
:_data(data)
,_Left(NULL)
,_Right(NULL)
{}
T _data;
BinaryTreeNode<T>* _Left;
BinaryTreeNode<T>* _Right;
};
template<class T>
class BinaryTree
{
typedef BinaryTreeNode<T> Node;
public:
BinaryTree()
:_root(NULL)
{}
BinaryTree(const T array[], size_t size, const T& invalid)
{
size_t index = 0;
_CreateBinaryTree(_root, array, size, invalid, index);
}
void MirrorTree()
{
_MirrorTree(_root);
}
private:
//创建二叉树
void _CreateBinaryTree(Node*& root, const T array[], size_t size, const T& invalid, size_t& index)
{
while ((index < size) && (array[index] != invalid))
{
//创建根节点
root = new Node(array[index]);
//创建根节点的左子树
_CreateBinaryTree(root->_Left, array, size, invalid, ++index);
//创建根节点的右子树
_CreateBinaryTree(root->_Right, array, size, invalid, ++index);
}
}
//二叉树的镜像
void _MirrorTree(Node* root)
{
if (root == NULL)
return ;
if (root->_Left == NULL && root->_Right == NULL)
return ;
Node* tmp = root->_Left;
root->_Left = root->_Right;
root->_Right = tmp;
if (root->_Left != NULL)
_MirrorTree(root->_Left);
if (root->_Right != NULL)
_MirrorTree(root->_Right);
}
private:
BinaryTreeNode<T>* _root;
};
int main()
{
const char* ptr = "124###35##6";
BinaryTree<char> t(ptr, strlen(ptr), '#');
t.MirrorTree();
return 0;
}
上一篇: 获取元素高度与宽度
下一篇: java技术---对象的实例化方法