7.2二叉树相似问题

《7.2二叉树相似问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构实验报告实验题目：二叉树相似问题姓名：张耀班级：计嵌151学号：1513052017一、实验目的设计一个算法，判断两棵树是否相似。、二、数据结构设计(1)设计二叉树的存储结构和建立算法(2)设计二叉树相似的判断算法(3)输入：两颗二叉树(4)输出：判定结果，相似或不相似三、算法设计与N-S图(1)算法设计设计判断相似算法Like(BinTreeNode*A,BinTreeNode*B)，该算法功能是若A与B相似，函数返回1，否则返回0。该算法从以下三个方面考虑。1.若A=B=NULL，则A与B相似，即Like(A,B)=12.若A与B中有一个为NULL，另一个不为NULL，则A与B不

2、相似，即Like(A,B)=0;3.采用递归方法，进一步判断A的左子树和B的左子树、A的右子树和B的右子树是否相似。(1)程序流程图一、程序清单#include"stdafx.h"#includeusingnamespacestd;staticintcount=1;structBinTreeNode//二叉树结点类的定义{chardata;//结点的数据域BinTreeNode*lchild;//左孩子指针BinTreeNode*rchild;//右孩子指针};classBTree//二叉树类{public:BinTreeNode*root;BTree(){root=NU

3、LL;}//构造一棵空的二叉树voidCreatBitree();//创建一棵二叉树voidPretraBitree();//先序遍历二叉树};staticvoidCreate(BinTreeNode*p,intk){//创建二叉树BinTreeNode*q;charx;cin>>x;if(x!='#'){q=newBinTreeNode;q->data=x;if(k==1)p->lchild=q;//k=1,把x存放左孩子结点if(k==2)p->rchild=q;//k=2,把x存放右孩子结点Create(q,1);Create(q,2);}else{q=newBinTreeNode;q

4、->data=x;q->lchild=NULL;q->rchild=NULL;if(k==1)p->lchild=q;if(k==2)p->rchild=q;}}voidBTree::CreatBitree(){BinTreeNode*p;charx;cin>>x;if(x=='#'){p=newBinTreeNode;p->data=x;p->lchild=NULL;p->rchild=NULL;}else{p=newBinTreeNode;p->data=x;root=p;Create(p,1);Create(p,2);}}staticvoidpretraverse(BinTreeNod

5、e*p){//遍历二叉树if(p!=NULL){pretraverse(p->lchild);pretraverse(p->rchild);}}voidBTree::PretraBitree(){BinTreeNode*p;p=root;pretraverse(p);cout<data=='#'&&b->data!='#')

6、

7、(a->data!='#'&&b->data=='#'))count=0;Like(a->lchild,b->

8、lchild);Like(a->rchild,b->rchild);}}voidwork(){BTreea;BTreeb;cout<<"请按先序序列输入二叉树："<

9、ut<<"A与B不相似"<