《剑指offer》:[59]对称的二叉树

题目;请实现1个函数,用来判断1棵2叉树是否是对称的。如果1颗2叉树和它的镜像1样,那末它是对称的。

例如,下面2棵树图(1)就是对称的2叉树,而图(2)(3)就不是的。

分析:我们知道树的遍历有3种方式:前,中,后。顾名思义,对称就是左侧的和右侧的相等,中间的自己等于自己。所以我们自己可以定义1种对称遍历算法,例如前序遍历中的前,左,右。对称算法就是:前,右,左。恰好对称比较。固然了其他的中和后序遍历也行,我们也能够定义与其对应的对称算法。但是其中为了不出现树(3)中的遍历出来的数据1样,造成误判,我们需要对叶子结点加上标识,如空节点需要设置为NULL。而不能只是比较遍历后的数据。
具体是实现代码以下:

#include <iostream>
using namespace std;
struct BinaryTree
{
int data;
BinaryTree *pLeft;
BinaryTree *pRight;
};
BinaryTree *pRoot1=NULL;
BinaryTree *pRoot2=NULL;
BinaryTree *pRoot3=NULL;
void CreateTree(BinaryTree * &root)
{
int data;
cin>>data;
if(0==data)
root=NULL;
else
{
root=new BinaryTree;
root->data=data;
//前序遍历构建2叉树;
CreateTree(root->pLeft);
CreateTree(root->pRight);
}
}
bool IsSymmetricalHelp(BinaryTree *root1,BinaryTree *root2)
{
if(root1==NULL && root2==NULL)
return true;
if(root1==NULL || root2==NULL)//把null也算上,很重要,避免数据1样的特殊情况;
return false;
if(root1->data!=root2->data)
return false;
return IsSymmetricalHelp(root1->pLeft,root2->pRight)
&& IsSymmetricalHelp(root1->pRight,root2->pLeft);
}
bool IsSymmetrical(BinaryTree *root)
{
return IsSymmetricalHelp(root,root);
}
void PreOrder(BinaryTree *root)
{
if(root)
{
cout<<root->data<<" ";
PreOrder(root->pLeft);
PreOrder(root->pRight);
}
}
void UntiPreOrder(BinaryTree *root)
{
if(root)
{
cout<<root->data<<" ";
PreOrder(root->pRight);
PreOrder(root->pLeft);
}
}
int main()
{
bool result=false;
CreateTree(pRoot1);
cout<<"树1的–前序遍历:";
PreOrder(pRoot1);
cout<<endl;
cout<<"树1的反前序遍历:";
UntiPreOrder(pRoot1);
result=IsSymmetrical(pRoot1);
if(result)
cout<<endl<<"该树是对称树!"<<endl;
else
cout<<"该树不是对称树!"<<endl;
cout<<endl;

CreateTree(pRoot2);//树3虽然遍历1样,但是否是对成树!
cout<<"树2的–前序遍历:";
PreOrder(pRoot2);
cout<<endl;
cout<<"树2的反前序遍历:";
UntiPreOrder(pRoot2);
cout<<endl;
result=IsSymmetrical(pRoot2);
if(result)
cout<<"该树是对称树!"<<endl;
else
cout<<"该树不是对称树!"<<endl;
cout<<endl;
system("pause");
return 0;
}

运行结果以下;

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » 《剑指offer》:[59]对称的二叉树

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡