二叉树相似问题C__数据结构算法.docVIP

实验五 二叉树相似问题 姓名：*** 班级：计算机099 学号：20 实验时间：2011.4.11 #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; }