二叉树的镜像

二叉树的镜像：

成都创新互联长期为成百上千家客户提供的网站建设服务，团队从业经验10年，关注不同地域、不同群体，并针对不同对象提供差异化的产品和服务；打造开放共赢平台，与合作伙伴共同营造健康的互联网生态环境。为鹿城企业提供专业的成都网站设计、网站制作，鹿城网站改版等技术服务。拥有10年丰富建站经验和众多成功案例,为您定制开发。

先序遍历二叉树，若有子节点，则交换子节点。

（1）递归实现

（2）非递归实现，循环实现，利用栈

#include
#include
#include
#include
using namespace std;
struct BinaryTreeNode
{
BinaryTreeNode(int _value)
:m_nValue(_value)
,m_pLeft(NULL)
,m_pRight(NULL)
{}
int m_nValue;
struct BinaryTreeNode* m_pLeft;
struct BinaryTreeNode* m_pRight;
};
BinaryTreeNode* Buildtree(int* array,int& index,int size)
{
	assert(array);
	BinaryTreeNode* root=NULL;
	if(array[index]!='#'&&indexm_pLeft=Buildtree(array,++index,size);
		root->m_pRight=Buildtree(array,++index,size);
	}
	return root;
}

//void BinaryTreeMirror(BinaryTreeNode* root) //递归实现
//{
//	 if(root==NULL)
//	 {
//		 return;
//	 }
//	 if(root->m_pLeft==NULL&&root->m_pRight==NULL)
//	 {
//		 return;
//	 }
//	 BinaryTreeNode* tmp=root->m_pLeft;
//	 root->m_pLeft=root->m_pRight;
//	 root->m_pRight=tmp;
//	 if(root->m_pLeft)
//	 BinaryTreeMirror(root->m_pLeft);
//	 if(root->m_pRight)
//	 BinaryTreeMirror(root->m_pRight);
//}
void BinaryTreeMirror(BinaryTreeNode* root)  //非递归实现，利用栈
{
	if(root==NULL||(root->m_nValue==NULL&& root->m_pRight==NULL))
	{
		return;
	}
	stack StackTree;
	StackTree.push(root);
	while(StackTree.size())
	{
		BinaryTreeNode* proot=StackTree.top();
		StackTree.pop();
		if(proot->m_pLeft!=NULL||proot->m_pRight!=NULL)
		{
			BinaryTreeNode* tmp=proot->m_pLeft;
			proot->m_pLeft=proot->m_pRight;
			proot->m_pRight=tmp;
		}
		if(proot->m_pLeft)
		{
			StackTree.push(proot->m_pLeft);
		}
		if(proot->m_pRight)
		{
			StackTree.push(proot->m_pRight);
		}
	}
}
void PreOrder(BinaryTreeNode* root)
{
if(root==NULL)
{
return;
}
cout<m_nValue<<"->";
PreOrder(root->m_pLeft);
PreOrder(root->m_pRight);
}
void MidOrder(BinaryTreeNode* root)
{
if(root==NULL)
{
return;
}
MidOrder(root->m_pLeft);
cout<m_nValue<<"->";
MidOrder(root->m_pRight);
}
int main()
{
	int array[]={1,2,4,'#',7,'#','#','#',3,5,'#','#',6,8,};
	
	int index=0;
	
	BinaryTreeNode* root=Buildtree(array,index,sizeof(array)/sizeof(array[0]));
	PreOrder(root);
	printf("\n");

	BinaryTreeMirror(root);
	PreOrder(root);
	printf("\n");
	MidOrder(root);

   system("pause");
   return 0;
}

结果：

<2>利用后序遍历

（1）递归实现

void BinaryTreeMirror(BinaryTreeNode* root) 
{
	if(root==NULL||(root->m_nValue==NULL&& root->m_pRight==NULL))
	{
		return;
	}
	BinaryTreeMirror(root->m_pLeft);
	BinaryTreeMirror(root->m_pRight);
	if(root->m_pLeft!=NULL||root->m_pRight!=NULL)
	{
		BinaryTreeNode* tmp=root->m_pLeft;
		root->m_pLeft=root->m_pRight;
		root->m_pRight=tmp;
	}
}