数据结构导论作业三.doc

实践考核设计报告书2学生姓名学生学号所在地区提交日期（年/月）2014/9/25实践题目实现二叉树的建立与遍历需求分析“以二叉链表作为存储结构，定义二叉树类型 bitree ；建立 create( ) 输入二叉树的结点元素，建立二叉链表；选择一种遍历方式（先序、中序、后序）遍历这棵二叉树。”二叉树有不同的链式存储结构，最常用的就是二叉链表与三叉链表，本需求中采用二叉链表存储实现建树与遍历树的基本算法。本方案给出的算法是使用的树的逻辑表示方法中的嵌套括号表示法。嵌套括号表示法：每棵树对应一个由根作为名字的表，表名放在表的左边，表是由在一个括号里的各子树对应的表组成的，之间用逗号分开。用这种方法表示的树中，结点之间的关系是通过括号的嵌套表示的，如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=“，”，表示其后创建的结点为右孩子；其他情况，表示要创建一个结点，并根据k值建立它与栈中结点之间的联系，如此循环直到str处理完毕。2.二叉树遍历算法的实现采用递归的思想详细设计1. void creatree(Btree *b,char *str)btree *stackMaxsize,*p=null;int top=-1,k,j=0;char ch;b=null;ch=strjwhile (ch!=0)switch (ch)case (:top+;stacktop=p;k=1;break; /为左结点case ):top-;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) case 1:stacktop-lchild=p;break;case 2:stacktop-rchild=p;break;)j+;ch=strj;2. 先序遍历、中序遍历和后序遍历的递归算法，以先序遍历为例Void preorder(Bintree bt)if (bt!=null) visit(bt); /访问根节点btpreorder(bt-lchild);preorder(bt-rchild);调试分析TurboC 2.0 1.启动TC：在我的电脑中找到TC2.0所在文件夹（c:tc），双击TC.EXE。2.右键单击标题栏，选“属性”，显示选项?“全屏显示”。3.新建文件：ALT+F，选“NEW”，编辑源程序。4.保存文件：按F2键 或者ALT+F，选“SAVE”，命名文件，扩展名必须为 .C 。5.编译和连接文件：按F9键6.如果有错误，重新修改源程序，再按F9键，无错误下一步。7.运行程序：按CTRL+F9键8.查看运行结果：ALT+F59.退出编辑环境：ALT+X设计总结本设计中主要先解决二叉树的逻辑存储结构，以嵌套括号表示法表示一棵二叉