二叉樹的鏡像：

創(chuàng)新互聯(lián) - 多線BGP機(jī)房，四川服務(wù)器租用，成都服務(wù)器租用，四川網(wǎng)通托管,綿陽(yáng)服務(wù)器托管，德陽(yáng)服務(wù)器托管，遂寧服務(wù)器托管，綿陽(yáng)服務(wù)器托管，四川云主機(jī)，成都云主機(jī)，西南云主機(jī)，多線BGP機(jī)房，西南服務(wù)器托管，四川/成都大帶寬，成都機(jī)柜租用，四川老牌ＩＤＣ服務(wù)商

先序遍歷二叉樹，若有子節(jié)點(diǎn)，則交換子節(jié)點(diǎn)。

（1）遞歸實(shí)現(xiàn)

（2）非遞歸實(shí)現(xiàn)，循環(huán)實(shí)現(xiàn)，利用棧

#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) //遞歸實(shí)現(xiàn)
//{
//	 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)  //非遞歸實(shí)現(xiàn)，利用棧
{
	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;
}

結(jié)果：

<2>利用后序遍歷

（1）遞歸實(shí)現(xiàn)

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

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

當(dāng)前名稱：二叉樹的鏡像-創(chuàng)新互聯(lián)
轉(zhuǎn)載來源：http://weahome.cn/article/geisd.html