数据结构抽象数据类型的实现.doc

《数据结构抽象数据类型的实现.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构实验报告题目：二叉树学院计算机学院专业软件工程年级班别2010级4班学号学生姓名指导教师成绩____________________2012年6月1、设计任务【DesignTasks】完成二叉树的17中基本操作。如：二叉树中插入、删除节点或一棵子树。求节点的双亲、孩子、兄弟节点等。2、设计思路【DesignIdeas】2.1主函数设计框图X==0YN结束通过switch()函数选择基本操作开始2.2基本操作函数设计框图主函数随机生成二叉树新建二叉树嵌套输出二叉树二叉树深度节点的双亲根节点遍历二叉树节点的孩子节点

2、的兄弟删除子树删除节点插入节点修改节点的值查找节点的值插入子树摧毁二叉树清空二叉树凹进输出二叉树先序遍历中序遍历后序遍历层次遍历左孩子右孩子左兄弟右兄弟1.所有的分支通过switch()函数实现。2.在遍历、找节点孩子和节点的兄弟时，通过while()实现循环。3.实现插入删除子树和插入删除节点,注意节点的重新连接。3、部分代码分析【CodeAnalysis】3.1．插入子树分析：1、通过建立队列，采用层次遍历查找要插入子树的双亲x，在通过Flag标志，决定插入的是左子树还是右子树。2、if(p->data==x&

3、&((flag==0&&p->lchild==NULL)

4、

5、(flag==1&&p->rchild==NULL)))。找到双亲节点时，如果插入的是左子树，则其双亲的左孩子必须是空的；如果插入的是右子树，则其双亲的右孩子必须是空的。3、通过f标志，判断是否查找成功。voidEnter(BTree&T,BTrees,elemtypex,intflag){BTreep=T;intf=0;LinkQueueQ;InitQueue(Q);//建立工作队列EnQueue(Q,T);/***按层次遍历查找x节点*/while(!Qu

6、eueEmpty(Q)){DeQueue(Q,p);/***可建立子树的条件*/if(p->data==x&&((flag==0&&p->lchild==NULL)

7、

8、(flag==1&&p->rchild==NULL))){f=1;//查找成功break;}if(p->lchild)EnQueue(Q,p->lchild);if(p->rchild)EnQueue(Q,p->rchild);}/***如果flag=0则建立该节点的左子树**flag=1则建立该节点的右子树*/if(f){switch(flag){ca

9、se0:p->lchild=s;break;case1:p->rchild=s;break;}Print_tree(T);cout<<"插入成功!"<lchild;p->lchild=NULL;dispose(q);break;case1:q=p->rchild;p->rch

10、ild=NULL;dispose(q);break;查找成功时，要重新连接节点。同时释放删除子树的空间3、通过f标志，判断是否查找成功。voidDeleChild(BTree&T,elemtypex,intflag){BTreep=T,q;intf=0;LinkQueueQ;InitQueue(Q);//建立工作队列EnQueue(Q,T);/***按层次遍历查找x节点*/while(!QueueEmpty(Q)){DeQueue(Q,p);if(p->data==x){f=1;//删除成功break;}if(p->l

11、child)EnQueue(Q,p->lchild);if(p->rchild)EnQueue(Q,p->rchild);}/***如果flag=0则删除该节点的左子树**flag=1则删除该节点的右子树*/if(f){switch(flag){case0:q=p->lchild;p->lchild=NULL;dispose(q);break;case1:q=p->rchild;p->rchild=NULL;dispose(q);break;}Print_tree(T);cout<<"删除成功!"<

12、e{Print_tree(T);cout<<"删除失败!"<data==x&&(((p->lchild->lchild==NULL)

13、

14、(p->lchild->rchild==NULL))

15、

16、((p->rchild->lchild==NULL)

17、

18、(p->rch