二叉树的镜像:
先序遍历二叉树,若有子节点,则交换子节点。
(1)递归实现
(2)非递归实现,循环实现,利用栈
#include<iostream> #include<stdlib.h> #include<assert.h> #include<stack> 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<size) { root=new BinaryTreeNode(array[index]); root->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<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); } } } void PreOrder(BinaryTreeNode* root) { if(root==NULL) { return; } cout<<root->m_nValue<<"->"; PreOrder(root->m_pLeft); PreOrder(root->m_pRight); } void MidOrder(BinaryTreeNode* root) { if(root==NULL) { return; } MidOrder(root->m_pLeft); cout<<root->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; } }
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。