二叉树的镜像-创新互联

二叉树的镜像：

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

（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;
	}
}

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。