二叉树的镜像

   什么是二叉树的镜像呢？

   我们可以自己画一颗二叉树。然后根据照镜子画出它的镜像。

如：

我们不能一次得到二叉树的镜像，要想得到一颗二叉树的镜像，有以下几个步骤：

（1）先交换根的左子树和右子树

（2）交换6的左子树和右子树                      （3）交换10的左子树和右子树

得出以上规律后，就可以写代码喽：

class BinaryTreeNode
{
public:
	BinaryTreeNode(const T& data)
		:_data(data)
		,_left(NULL)
		,_right(NULL)
	{}
	T _data;//值
	BinaryTreeNode* _left;//左子树
	BinaryTreeNode* _right;//右子树
};

template <class T>
class BinaryTree
{
public:
	BinaryTree()//无参构造函数
		:_root(NULL)
	{}
	BinaryTree(const T* a,size_t size,const T& invalue)//构造函数
	{
		size_t index = 0;
		_root = _CreatTree(a,size,index,invalue); 
	}
public:
	void PrevOrder()//先根遍历
	{
		cout<<"先根遍历:";
		_PrevOrder(_root);
		cout<<endl;
	}
	
	void Mirro()//镜像
	{
		_Mirro(_root);
	}
public:
	BinaryTreeNode<T>* _CreatTree(const T* a,size_t size,size_t &index,const T& invalue)//创建树
	{
		BinaryTreeNode<T>* root = NULL;
		if(index < size && a[index] != invalue)
		{
			root = new BinaryTreeNode<T>(a[index]);
			root->_left = _CreatTree(a,size,++index,invalue);//左子树
			root->_right = _CreatTree(a,size,++index,invalue);//右子树
		}
		return root;
	}

	void _PrevOrder(BinaryTreeNode<T>* root)//先根遍历
	{
		if(root == NULL)
			return;
		else
		{
			cout<<root->_data<<" ";
			_PrevOrder(root->_left);
			_PrevOrder(root->_right);
		}
	}

	void _Mirro(BinaryTreeNode<T>* root)//镜像
	{
		if(root == NULL)
			return;
		if(root->_left== NULL && root->_right == NULL)//左右子树同时为NULL，停止
			return;

		BinaryTreeNode<T>* tmp = root->_left;//交换左右子树
		root->_left = root->_right;
		root->_right = tmp;

		_Mirro(root->_left);
		_Mirro(root->_right);
	}
protected:
	BinaryTreeNode<T>* _root;//根节点
};

本文出自 “一起去看星星” 博客，转载请与作者联系！

二叉树的镜像

原文：http://10810429.blog.51cto.com/10800429/1767637