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; 五、 运行与测试六、 实验分析及体会通过本次实验，进一步熟悉了二叉树的存储结构和相关操作。