数据结构-二叉树相似问题.doc

数 据 结 构 课 程 实 验 报 告 班级：计嵌141 姓名：陈志远 学号：1413052023 二叉树相似问题 ?问题描述? 两颗二叉树相似，指要么他们都为空或都只有一个根结点，要么它们的左右子树均相似，本问题是：设计一个算法，判断两颗二叉树是否相似。?? 2.?基本要求? （1）?设计二叉树的存储结构和建立算法。 ?（2）?设计二叉树相似的判断算法。 ?（3）?输入：两颗二叉树。 ? (4)?输出：判定结果，相似或不相似。? 实现提示 （1）存储设计 Class?BinTreeNode {?? char?data;? ? BinTreeNode?*?Lchild;?? BinTreeNode?*?Rchild;? BinTreeNode?*?Parent;?};? 算法设计 代码设计 #includeiostream? using?namespace?std;? static?int?count=1;? struct?node? {?? char?data;?? node?*lchild;? node?*rchild;? };? class?Bitree? {? public:? node?*root;? Bitree()? {? root=NULL;? }? void?CreatBitree();? void?PretraBitree();? } ? static?void?Create(node*p,int?k)? {? //创建二叉树 node?*q;?? char?x;? cinx;? if(x!=#)? {? q=new?node;? q-data=x;? if(k==1)? p-lchild=q;? if(k==2)?? p-rchild=q;? Create(q,1); Create(q,2);? }? ?else {?? q=new?node;? q-data=x;? q-lchild=NULL;? q-rchild=NULL;?? if(k==1)?? p-lchild=q;?? if(k==2)? p-rchild=q;? ?}? }? void?Bitree::CreatBitree()? {? node?*p;? char?x;? cinx;? if(x==#)? {? p=new?node;? p-data=x;? p-lchild=NULL;? p-rchild=NULL;}? else? {? ?p=new?node;? ?p-data=x;? root=p;? Create(p,1);? Create(p,2);? }? }? static?void?pretraverse(node?*p)? {? //遍历二叉树 if(p!=NULL)? {? pretraverse(p-lchild); pretraverse(p-rchild);? }? } void?Bitree::PretraBitree()? {? node?*p;? p=root;? pretraverse(p);? coutendl;? }? static?void?like(node?*a,node?*b)? {? if(a!=NULLb!=NULL)? {? ?if((a-data==#b-data!=#)||(a-data!=#b-data==#))? count=0;? like(a-lchild,b-lchild);? like(a-rchild,b-rchild);? }? }? void?work()? {? Bitree?a;? Bitree?b;? cout输入二叉树A(#为虚结点)：endl;? a.CreatBitree();?//创建二叉树A?? a.PretraBitree();//?先序遍历二叉树A cout输入二叉树B(#为虚结点)：endl;? b.CreatBitree();?//创建二叉树B? b.PretraBitree();//?先序遍历二叉树B? like(a.root,b.root);?//判断AB是否相似 ?cout判断结果：;? ?if(count==1)? ? coutA与B相似endl;? else?coutA与B不相似endl;? }? int?main()? {? work();? return?0;? } 5.?运行结果? 输入二叉树A:ab#c#?#d##? 输入二叉树B:as#d#?#f##? 判断结果：A与B相似?? 输入二叉树A:ab#c#?#d##? 输入二叉树B:a##sd#?#f##? 判断结果：A与B不相似