温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

二叉树的镜像

发布时间:2020-07-16 16:11:34 来源:网络 阅读:215 作者:秋笙夏笛 栏目:编程语言

二叉树的镜像:

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


(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;
	}
}
向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI