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

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

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

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

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

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

5、ttabIe(node);TreeNode*root=0;Build(root,node,0,n);if(root){printf("先序遍历：");Preorder(root);printf("中序遍历：");InOrder(root);printf("后序遍历：");PostOrder(root);}elseprintf("空树！H);system("pause");return0;}主程序与子程序间的调用关系：MainCreattabIeBuildPreorderInOrderPostOrder三、【实现描述(

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

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

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