二叉树的镜像
二叉树的镜像:
成都创新互联长期为成百上千家客户提供的网站建设服务,团队从业经验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]!='#'&&index m_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; } }
网站题目:二叉树的镜像
链接分享:http://pwwzsj.com/article/pihdeh.html