数据结构导论作业三

《数据结构导论作业三》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实践考核设计报告书2学生姓名学生学号所在地区提交日期（年/月）2014/9/25实践题目实现二叉树的建立与遍历需求分析“以二叉链表作为存储结构，定义二叉树类型bitree；建立create()输入二叉树的结点元素，建立二叉链表；选择一种遍历方式（先序、中序、后序）遍历这棵二叉树。”二叉树有不同的链式存储结构，最常用的就是二叉链表与三叉链表，本需求中采用二叉链表存储实现建树与遍历树的基本算法。本方案给出的算法是使用的树的逻辑表示方法中的嵌套括号表示法。嵌套括号表示法：每棵树对应一个由根作为名字的表，表名放在表的左边，表是由在一个括号里

2、的各子树对应的表组成的，之间用逗号分开。用这种方法表示的树中，结点之间的关系是通过括号的嵌套表示的，如A(B(E,F),C(G(J)),D(H,I(K,L,M))),A为根节点，B,C,D是兄弟，E是B的孩子。概要设计1.创建二叉树使用一个栈stack保存当前二叉树的根节点，top为其栈指针，k指定其后处理的结点是双亲结点、左孩子（k=1）还是右孩子（k=2）,ch为当前处理的str中的字符，若ch=“（”，则将创建的结点作为双亲结点进栈，并置k=1，其后创建的结点为左孩子；若ch=“）”，表示左右结点处理完毕，退栈；若ch=“，”

3、，表示其后创建的结点为右孩子；其他情况，表示要创建一个结点，并根据k值建立它与栈中结点之间的联系，如此循环直到str处理完毕。2.二叉树遍历算法的实现采用递归的思想详细设计1.voidcreatree(Btree*b,char*str){btree*stack[Maxsize],*p=null;inttop=-1,k,j=0;charch;b=null;ch=str[j]while(ch!=’’){switch(ch){case’(’:top++;stack[top]=p;k=1;break;//为左结点case’)’:top-

4、-;break;case’,’:k=2;break;//为右结点default:p=(Btree*)malloc(sizeof(BTree));p->data=ch;p->lchild=p->rchild=null;if(b==null)//为根结点b=p;else(switch(k){case1:stack[top]->lchild=p;break;case2:stack[top]->rchild=p;break;})}j++;ch=str[j];}}2.先序遍历、中序遍历和后序遍历的递归算法，以先序遍历为例Voidpreorde

5、r(Bintreebt){if(bt!=null){visit(bt);//访问根节点btpreorder(bt->lchild);preorder(bt->rchild);}}调试分析TurboC2.01.启动TC：在我的电脑中找到TC2.0所在文件夹（c:tc），双击TC.EXE。2.右键单击标题栏，选“属性”，显示选项?“全屏显示”。3.新建文件：ALT+F，选“NEW”，编辑源程序。4.保存文件：按F2键或者ALT+F，选“SAVE”，命名文件，扩展名必须为.C。5.编译和连接文件：按F9键6.如果有错误，重新修改源程序，

6、再按F9键，无错误下一步。7.运行程序：按CTRL+F9键8.查看运行结果：ALT+F59.退出编辑环境：ALT+X设计总结本设计中主要先解决二叉树的逻辑存储结构，以嵌套括号表示法表示一棵二叉树，引入栈来实现物理存储，通过对符号的判断来实现对二叉树结构的构建.二叉树的遍历采用递归的方式实现，因为要对每个节点访问一次，所以时间复杂性为O（n）