二叉树的镜像：

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


（1）递归实现

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

#include<iostream>#include<stdlib.h>#include<assert.h>#include<stack>usingnamespacestd;structBinaryTreeNode{BinaryTreeNode(int_value):m_nValue(_value),m_pLeft(NULL),m_pRight(NULL){}intm_nValue;structBinaryTreeNode*m_pLeft;structBinaryTreeNode*m_pRight;};BinaryTreeNode*Buildtree(int*array,int&index,intsize){assert(array);BinaryTreeNode*root=NULL;if(array[index]!='#'&&index<size){root=newBinaryTreeNode(array[index]);root->m_pLeft=Buildtree(array,++index,size);root->m_pRight=Buildtree(array,++index,size);}returnroot;}//voidBinaryTreeMirror(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);//}voidBinaryTreeMirror(BinaryTreeNode*root)//非递归实现，利用栈{if(root==NULL||(root->m_nValue==NULL&&root->m_pRight==NULL)){return;}stack<BinaryTreeNode*>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);}}}voidPreOrder(BinaryTreeNode*root){if(root==NULL){return;}cout<<root->m_nValue<<"->";PreOrder(root->m_pLeft);PreOrder(root->m_pRight);}voidMidOrder(BinaryTreeNode*root){if(root==NULL){return;}MidOrder(root->m_pLeft);cout<<root->m_nValue<<"->";MidOrder(root->m_pRight);}intmain(){intarray[]={1,2,4,'#',7,'#','#','#',3,5,'#','#',6,8,};intindex=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");return0;}

结果：


<2>利用后序遍历

（1）递归实现

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