7.2二叉树相似问题.doc

数 据 结 构 实 验 报 告实验题目：二叉树相似问题姓名： 张耀班级： 计嵌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不相似，即Like(A,B)=0;3. 采用递归方法，进一步判断A的左子树和B的左子树、A的右子树和B的右子树是否相似。(2) 程序流程图四、 程序清单#include stdafx.h#includeusing namespace std;static int count=1; struct BinTreeNode /二叉树结点类的定义char data; /结点的数据域BinTreeNode *lchild;/左孩子指针BinTreeNode *rchild;/右孩子指针;class BTree /二叉树类 public:BinTreeNode *root;BTree() root = NULL; /构造一棵空的二叉树void CreatBitree();/创建一棵二叉树void PretraBitree();/先序遍历二叉树;static void Create(BinTreeNode *p, int k) /创建二叉树BinTreeNode *q; char x;cinx;if(x!=#)q = new BinTreeNode;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 = new BinTreeNode;q-data = x;q-lchild = NULL; q-rchild = NULL;if (k = 1)p-lchild = q; if (k = 2) p-rchild = q; void BTree:CreatBitree()BinTreeNode *p;char x; cin x;if (x = #)p = new BinTreeNode;p-data = x;p-lchild = NULL; p-rchild = NULL; else p = new BinTreeNode;p-data = x;root = p;Create(p, 1);Create(p, 2); static void pretraverse(BinTreeNode *p) /遍历二叉树if(p!=NULL) pretraverse(p-lchild); pretraverse(p-rchild); void BTree:PretraBitree() BinTreeNode *p;p = root;pretraverse(p); coutdata = #&b-data != #) | (a-data != #&b-data = #) count = 0; Like(a-lchild, b-lchild); Like(a-rchild, b-rchild); void work() BTree a; BTree b; cout 请按先序序列输入二叉树： endl; a.CreatBitree();/创建二叉树 A a.PretraBitree();/ 先序遍历二叉树 A cout请按先序序列输入二叉树：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; 五、 运行与测试六、 实验分析及体会通过本次实验，进一步熟悉了二叉树的存储结构和相关操作。并且根据数据结构实验教程实验课本上关于对二叉树相似问题的分析和引导，完成了本次实验。本算法的核心