二叉树的镜像-创新互联
二叉树的镜像:
创新互联 - 多线BGP机房,四川服务器租用,成都服务器租用,四川网通托管,绵阳服务器托管,德阳服务器托管,遂宁服务器托管,绵阳服务器托管,四川云主机,成都云主机,西南云主机,多线BGP机房,西南服务器托管,四川/成都大带宽,成都机柜租用,四川老牌IDC服务商先序遍历二叉树,若有子节点,则交换子节点。
(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; } }
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
网站栏目:二叉树的镜像-创新互联
本文网址:http://myzitong.com/article/geisd.html