云南大学软件学院数据结构试验 实验五 树及其应用

《云南大学软件学院数据结构试验 实验五 树及其应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、云南大学软件学院数据结构实验报告（本实验项目方案受“教育部人才培养模式创新实验区（X3108005）”项目资助）实验难度：A□B□C□序号学号姓名成绩123指导教师（签名）学　　期：　　2010秋季学期任课教师:　朱艳萍　　实验题目:实验五树及其应用小组长:　　　联系电话:　　　　　　电子邮件:　完成提交时间：2010年12月27日　（下面的内容由学生填写，格式统一为，字体:楷体,行距:固定行距18，字号:小四，个人报告按下面每一项的百分比打分。难度A满分70分，难度B满分90分）一、【实验构思（Conceive）】(10%)（本部分应包括：描述实验实现

2、的基本思路，包括所用到的离散数学、工程数学、程序设计、算法等相关知识）本实验需要完成的操作是：首先让用户输入其想要转化为二叉树的树，将用户输入的树以孩子双亲表示法存储，即需要用户按层次遍历的顺序输入一棵树中每个结点的信息，则可得出每个结点对应顺序表中的位置序号，还要让用户输入每个结点所对应的双亲结点的位置号。然后通过二重循环将用户输入的树转变为以孩子兄弟法表示的树。即从第二个结点开始循环，如果当前结点为其双亲结点的最左孩子，则将当前结点赋为其双亲结点的左孩子；若当前结点不为其双亲结点的最左孩子，说明当前结点为前一个结点的相邻的兄弟，则将其赋为其前一个结点

3、的右孩子。然后把生成的用孩子兄弟表示法表示的顺序表用二叉链表表示成二叉树，实现树到二叉树的转化。最后对二叉树进行先序、中序和后序遍历并直接输出遍历序列。二、【实验设计(Design)】(20%)（本部分应包括：抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明，主程序模块与各子程序模块间的调用关系）抽象数据类型说明：creattable(Nodetable[])提示用户输入树的相关信息，即结点的信息和每个结点对应的双亲结点的位置，且将其转化为以孩子兄弟法表示的顺序表table（即根据用户输入的data和parent值给ichild和rchil

4、d赋值），并将该表打印出来（该表为表示二叉树的一种方式）Build(TreeNode*¤t,Nodenode[],intpos,intn)根据以孩子兄弟法表示的顺序表table（这里调用时为node）创建二叉链表Preorder(TreeNode*root)对创建成功的二叉链表进行先序遍历，并输出先序序列InOrder(TreeNode*root)对创建成功的二叉链表进行中序遍历，并输出中序序列PostOrder(TreeNode*root)对创建成功的二叉链表进行后序遍历，并输出后序序列主程序：intmain(){Nodenode[20];

5、intn=creattable(node);TreeNode*root=0;Build(root,node,0,n);if(root){printf("先序遍历：");Preorder(root);printf("中序遍历:");InOrder(root);printf("后序遍历：");PostOrder(root);}elseprintf("空树！");system("pause");return0;}主程序与子程序间的调用关系：MainCreattableBuildPreorderInOrderPostOrder三、

6、【实现描述（Implement）】(30%)（本部分应包括：抽象数据类型具体实现的函数原型说明、关键操作实现的伪码算法、函数设计、函数间的调用关系，关键的程序流程图等，给出关键算法的时间复杂度分析。）顺序表和二叉链表的类型：structNode{//以表的形式存储的树结点chardata;intparent;intlchild;intrchild;};structTreeNode{//以二叉链表存储的树的结点chardata;TreeNode*left;TreeNode*right;};基本操作实现：intcreattable(Nodetable[]){

7、//创建树的表并转化为二叉树，然后将二叉树以表的形式表示出来intn,k,i,j;chare;printf("请输入您要建立的树的结点个数:(<20)");scanf("%d%c",&n,&e);//用一个字符输入符接受用户输入结点个数时一定会输入的回车if(n>0){printf("请按序输入所有结点信息:");//即输入结点所带数据，如‘A’，‘B’等for(i=0;i

8、的位置号为：");for(i=0;i