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

.云南大学软件学院 数据结构实验报告 （本实验项目方案受“教育部人才培养模式创新实验区（X3108005）”项目资助） 实验难度： A B C 序号学号姓名成绩123指导教师 （签名）学期：2010秋季学期 任课教师: 朱艳萍 实验题目: 实验五 树及其应用 小 组 长: 联系电话: 电子邮件: 完成提交时间：2010年 12月27日（下面的内容由学生填写，格式统一为，字体: 楷体, 行距: 固定行距18，字号: 小四，个人报告按下面每一项的百分比打分。难度A满分70分，难度B满分90分）一、【实验构思（Conceive）】(10%)（本部分应包括：描述实验实现的基本思路，包括所用到的离散数学、工程数学、程序设计、算法等相关知识）本实验需要完成的操作是：首先让用户输入其想要转化为二叉树的树，将用户输入的树以孩子双亲表示法存储，即需要用户按层次遍历的顺序输入一棵树中每个结点的信息，则可得出每个结点对应顺序表中的位置序号，还要让用户输入每个结点所对应的双亲结点的位置号。然后通过二重循环将用户输入的树转变为以孩子兄弟法表示的树。即从第二个结点开始循环，如果当前结点为其双亲结点的最左孩子，则将当前结点赋为其双亲结点的左孩子；若当前结点不为其双亲结点的最左孩子，说明当前结点为前一个结点的相邻的兄弟，则将其赋为其前一个结点的右孩子。然后把生成的用孩子兄弟表示法表示的顺序表用二叉链表表示成二叉树，实现树到二叉树的转化。最后对二叉树进行先序、中序和后序遍历并直接输出遍历序列。二、【实验设计(Design)】(20%)（本部分应包括：抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明，主程序模块与各子程序模块间的调用关系）抽象数据类型说明：creattable( Node table)提示用户输入树的相关信息，即结点的信息和每个结点对应的双亲结点的位置，且将其转化为以孩子兄弟法表示的顺序表table（即根据用户输入的data和parent值给ichild和rchild赋值），并将该表打印出来（该表为表示二叉树的一种方式）Build ( TreeNode*& current,Node node, int pos ,int n )根据以孩子兄弟法表示的顺序表table（这里调用时为node）创建二叉链表Preorder( TreeNode* root )对创建成功的二叉链表进行先序遍历，并输出先序序列InOrder(TreeNode* root)对创建成功的二叉链表进行中序遍历，并输出中序序列PostOrder(TreeNode* root)对创建成功的二叉链表进行后序遍历，并输出后序序列主程序：int main()Node node 20;int n = creattable( node );TreeNode* root = 0;Build ( root, node, 0 , n);if (root)printf("n先序遍历：n");Preorder ( root );printf("n中序遍历: n");InOrder(root);printf("n后序遍历：n");PostOrder(root);elseprintf("n空树！n");system("pause");return 0;主程序与子程序间的调用关系： Main Creattable Build Preorder InOrder PostOrder三、【实现描述（Implement）】(30%)（本部分应包括：抽象数据类型具体实现的函数原型说明、 关键操作实现的伪码算法、 函数设计、函数间的调用关系，关键的程序流程图等，给出关键算法的时间复杂度分析。）顺序表和二叉链表的类型：struct Node /以表的形式存储的树结点char data;int parent;int lchild;int rchild;struct TreeNode /以二叉链表存储的树的结点char data;TreeNode* left;TreeNode* right;基本操作实现：int creattable( Node table) /创建树的表并转化为二叉树，然后将二叉树以表的形式表示出来int n,k,i,j; char e;printf("n请输入您要建立的树的结点个数:(<20)");scanf("%d%c",&n,&e);/用一个字符输入符接受用户输入结点个数时一定会输入的回车if ( n>0 )printf("n请按序输入所有结点信息:n");/即输入结点所带数据，如A，B等for( i = 0; i < n; i+)scanf("%c",&tablei.data);tablei.lchild = tablei.rchild = 0;printf("您输入的结点对应的位置号为：n");for( i = 0;i < n; i+)printf("%d:%cn",i,tablei.data);printf("对应位置号，请您按序输入每个结点对应的双亲结点的位置号：n");/显示用户输入的结点所对应的位置，让用户输入其双亲位置时有参照for( i = 0;i < n; i+)printf("请输入第%d个节点的双亲信息：",i);scanf("%d",&tablei.parent);for( i = 0; i < n; i+ )/将用户输入的树以孩子兄弟表示法构建，并以表的形式存储for( j = 1;j < n; j+ )if( tablej.parent = i )if( tablei.lchild = 0 )/如果i结点是j结点的双亲结点，且i结点的左孩子为空，则j赋为i的左孩子tablei.lchild = j;k = j;else/如果i结点的左孩子不为空，说明j不为i的最左孩子，则j为其前一个兄弟的右孩子tablek.rchild = j; k = j;printf("n您输入的树转化为二叉树表示为：n");printf("n结点 该结点的双亲 该结点的左孩子 该结点的右孩子");for( i = 0; i < n; i+)printf("n %c %d %d %dn",tablei.data,tablei.parent,tablei.lchild,tablei.rchild);return n;void Build ( TreeNode*& current,Node node, int pos ,int n ) /将以表的形式存储的树转化为二叉链表if (n>0)if ( current = 0 )current = new TreeNode; /动态为存储TreeNode型的数据分配空间current->left = current->right = 0;current->data = nodepos.data; if (nodepos.lchild ) Build( current->left, node, nodepos.lchild, n);/一直构建当前结点的左子树if (nodepos.rchild ) Build( current->right ,node, nodepos.rchild, n);/若当前结点的左子树为空，则构建当前结点的右子树，若当前结点的右子树，则又开始构建其双亲结点的右子树void Preorder( TreeNode* root ) /对建立好的二叉树按先序遍历TreeNode* current = root;if( current != 0 ) printf("%c",current->data); Preorder( current->left );Preorder( current->right ); void InOrder(TreeNode* root)/对建立好的二叉树按中序遍历TreeNode* current = root;if(current != 0)InOrder(current->left);printf("%c",current->data);InOrder(current->right);void PostOrder(TreeNode* root)/对建立好的二叉树按后序遍历TreeNode* current = root;if(current != 0)PostOrder(current->left);PostOrder(current->right);printf("%c",current->data); 关键操作的时间复杂度分析：Creattable（)函数的时间复杂度为O（n2），Build ()Preorder()、InOrder()、PostOrder()函数的时间复杂度为O（n）关键的程序流程图:四、【测试结果（Testing）】(10%)（本部分应包括：对实验的测试结果，应具体列出每次测试所输入的数据以及输出的数据，并对测试结果进行分析总结）四、【实验总结】(10%)（本部分应包括：自己在实验中完成的任务，注意组内的任意一位同学都必须独立完成至少一项接口的实现；对所完成实验的经验总结、心得）本实验完成的任务是首先让用户输入其想要转化为二叉树的树，将用户输入的树以孩子双亲表示法存储，即需要用户按层次遍历的顺序输入一棵树中每个结点的信息，则可得出每个结点对应顺序表中的位置序号，还要让用户输入每个结点所对应的双亲结点的位置号。然后通过二重循环将用户输入的树转变为以孩子兄弟法表示的树。即从第二个结点开始循环，如果当前结点为其双亲结点的最左孩子，则将当前结点赋为其双亲结点的左孩子；若当前结点不为其双亲结点的最左孩子，说明当前结点为前一个结点的相邻的兄弟，则将其赋为其前一个结点的右孩子。然后把生成的用孩子兄弟表示法表示的顺序表用二叉链表表示成二叉树，实现树到二叉树的转化。最后对二叉树进行先序、中序和后序遍历并直接输出遍历序列。实验过程中出现的问题：输入模块中输入结点个数之后用户会输入一个回车符来进行下一步的操作，平常一般不会出现问题，但本次实验中输入结点个数之后紧接着就是要求用户输入每个结点的信息，则用户在输入个数时最后一个输入的回车符会读入第一个结点信息中，则会影响其后的输入。解决方法是让用户输入结点个数时就安排一个字符输入符直接来接受用户输入的回车符。五、【项目运作描述（Operate）】(10%)（本部分应包括：项目的成本效益分析，应用效果等的分析。）本实验完成将用户输入的树以孩子兄弟表示法表示出来，且由于孩子兄弟法即是将树转化为二叉树的方法，故输出的表同时也是将转化而成的二叉树表示出来，最后在屏幕上输出转化成的二叉树的先序、中序和后序序列，进而完成二叉树的三种遍历过程。缺点为无法接受用户输入的本来就是一个二叉树的情况，灵活性差。六、【代码】(10%)（本部分应包括：完整的代码及充分的注释。 注意纸质的实验报告无需包括此部分。格式统一为，字体: Georgia , 行距: 固定行距12，字号: 小五）例如：#include<stdio.h>#include <iostream>struct Node /以孩子双亲表示法的形式存储树结点char data;int parent;int lchild;int rchild;struct TreeNode /以二叉链表存储的二叉树的结点char data;TreeNode* left;TreeNode* right;int creattable( Node table) /创建树的表并转化为二叉树，然后将二叉树以表的形式表示出来int n,k,i,j; char e;printf("n请输入您要建立的树的结点个数:(<20)");scanf("%d%c",&n,&e);/用一个字符输入符接受用户输入结点个数时一定会输入的回车if ( n>0 )printf("n请按序输入所有结点信息:n");/即输入结点所带数据，如A，B等for( i = 0; i < n; i+)scanf("%c",&tablei.data);tablei.lchild = tablei.rchild = 0;printf("您输入的结点对应的位置号为：n");for( i = 0;i < n; i+)printf("%d:%cn",i,tablei.data);printf("对应位置号，请您按序输入每个结点对应的双亲结点的位置号：n");/显示用户输入的结点所对应的位置，让用户输入其双亲位置时有参照for( i = 0;i < n; i+)printf("请输入第%d个节点的双亲信息：",i);scanf("%d",&tablei.parent);for( i = 0; i < n; i+ )/将用户输入的树以孩子兄弟表示法构建，并以表的形式存储for( j = 1;j < n; j+ )if( tablej.parent = i )if( tablei.lchild = 0 )/如果i结点是j结点的双亲结点，且i结点的左孩子为空，则j赋为i的左孩子tablei.lchild = j;k = j;else/如果i结点的左孩子不为空，说明j不为i的最左孩子，则j为其前一个兄弟的右孩子tablek.rchild = j; k = j;printf("n您输入的树转化为二叉树表示为：n");printf("n结点 该结点的双亲 该结点的左孩子 该结点的右孩子");for( i = 0; i < n; i+)printf("n %c %d %d %dn",tablei.data,tablei.parent,tablei.lchild,tablei.rchild);return n;void Build ( TreeNode*& current,Node node, int pos ,int n ) /将以表的形式存储的树转化为二叉链表if (n>0)if ( current = 0 )current = new TreeNode; /动态为存储TreeNode型的数据分配空间current->left = current->right = 0;current->data = nodepos.data; if (nodepos.lchild ) Build( current->left, node, nodepos.lchild, n);/一直构建当前结点的左子树if (nodepos.rchild ) Build( current->right ,node, nodepos.rchild, n);/若当前结点的左子树为空，则构建当前结点的右子树，若当前结点的右子树，则又开始构建其双亲结点的右子树void Preorder( TreeNode* root ) /对建立好的二叉树按先序遍历TreeNode* current = root;if( current != 0 ) printf("%c",current->data); Preorder( current->left );Preorder( current->right ); void InOrder(TreeNode* root)/对建立好的二叉树按中序遍历TreeNode* current = root;if(current != 0)InOrder(current->left);printf("%c",current->data);InOrder(current->right);void PostOrder(TreeNode* root)/对建立好的二叉树按后序遍历TreeNode* current = root;if(current != 0)PostOrder(current->left);PostOrder(current->right);printf("%c",current->data); int main()Node node 20;int n = creattable( node );TreeNode* root = 0;Build ( root, node, 0 , n);if (root)printf("n先序遍历：n");Preorder ( root );printf("n中序遍历: n");InOrder(root);printf("n后序遍历：n");PostOrder(root);elseprintf("n空树！n");system("pause");return 0;