二叉树的镜像:
先序遍历二叉树,若有子节点,则交换子节点。
(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;
}
}
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。