实验五 树及其应用.doc

实验五 树及其应用序号： 学号：20121120159 姓名：胡志龙 试验编号：5 实验名称：树及其应用 难度等级：（1） 需求分析：本实验完成的任务是首先让用户输入其想要转化为二叉树的树，将用户输入的树以孩子双亲表示法存储，即需要用户按层次遍历的顺序输入一棵树中每个结点的信息，则可得出每个结点对应顺序表中的位置序号，还要让用户输入每个结点所对应的双亲结点的位置号。然后通过二重循环将用户输入的树转变为以孩子兄弟法表示的树。即从第二个结点开始循环，如果当前结点为其双亲结点的最左孩子，则将当前结点赋为其双亲结点的左孩子；若当前结点不为其双亲结点的最左孩子，说明当前结点为前一个结点的相邻的兄弟，则将其赋为其前一个结点的右孩子。然后把生成的用孩子兄弟表示法表示的顺序表用二叉链表表示成二叉树，实现树到二叉树的转化。最后对二叉树进行先序、中序和后序遍历并直接输出遍历序列。（2） 概要设计抽象数据类型说明：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（3） 详细设计顺序表和二叉链表的类型：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请输入您要建立的树的结点个数:(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 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）（4） 运行记录（5） 实验总结实验过程中出现的问题：输入模