实验五树及其应用

《实验五树及其应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验五树及其应用序号：学号：20121120159姓名：胡志龙试验编号：5实验名称：树及其应用难度等级：（1）需求分析：本实验完成的任务是首先让用户输入其想要转化为二叉树的树，将用户输入的树以孩子双亲表示法存储，即需要用户按层次遍历的顺序输入一棵树中每个结点的信息，则可得岀每个结点对应顺序表中的位置序号，还要让用户输入每个结点所对应的双亲结点的位置号。然后通过二重循环将用户输入的树转变为以孩子兄弟法表示的树。即从第二个结点开始循环，如果当前结点为其双亲结点的最左孩子，则将当前结点赋为其双亲结点的左孩子；若当前结点不为其双亲结点的最左孩子，说明当前结点为前一个结点的相邻的兄弟，则将其赋为其前一

2、个结点的右孩子。然后把生成的用孩子兄弟表示法表示的顺序表用二叉链表表示成二叉树，实现树到二叉树的转化。最后对二叉树进行先序、中序和后序遍历并直接输岀遍历序列。（2）概要设计抽象数据类型说明：creattable（Nodetablefl）提示用户输入树的相关信息，即结点的信息和每个结点对应的双亲结点的位置，且将其转化为以孩子兄弟法表示的顺序表table（即根据用户输入的data和parent值给ichild和rchild赋值），并将该表打印岀来（该表为表示二叉树的一种方式）Build（TreeNode*¤t,Nodenode[],intpos,intn）根据以孩子兄弟法表示的顺序表

3、table（这里调用时为node）创建二叉链表Preorder（TreeNode*root）对创建成功的二叉链表进行先序遍历，并输出先序序列lnOrder(TreeNode*root)对创建成功的二叉链表进行中序遍历，并输出中序序列PostOrder(TreeNode*root)对创建成功的二叉链表进行后序遍历，并输出后序序列主程序：intmain(){Nodenode[20];intn二creattable(node);TreeNode*root=0;Build(root,node,0,n);if(root){printf("先序遍历:n);Preorder(root);print

4、f(H中序遍历:n);InOrder(root);printf(n后序遍历：H);PostOrder(root);}elseprintf(H空树!H);system(',pausen);return0;}主程序与子程序间的调用关系:MainCreattableBuildPreorderInOrderPostOrder(3)详细设计顺序表和二叉链表的类型：structNode{〃以表的形式存储的树结点chardata;intparent;intIchild;intrchild;}；structTreeNode{〃以二叉链表存储的树的结点chardata;TreeNode

5、*left;TreeNode*right;}；基本操作实现：intcreattable(Nodetable[]){//创建树的表并转化为二叉树，然后将二叉树以表的形式表示出来intn,k,i,j;chare;printf(n请输入您要建立的树的结点个数:(<20)n);scanf(,,%d%c,,,&n,&e);//用一个字符输入符接受用户输入结点个数时一定会输入的回车if(n>0){printf(H请按序输入所有结点信息:”);〃即输入结点所带数据，如7V,B等for(i二0;ivn;i++){scanf(”％c”,&table[i].data);table[i].lchild

6、=table[i].rchild=0;}printfC*您输入的结点对应的位置号为：K);for(i=0;i

7、;j++){if(table[j].parent==i)if(table[i].lchild==0)〃如果i结点是j结点的双亲结点，且i结点的左孩子为空，则j赋为i的左孩子{table[i].lchild=j;k=j;}else//如果i结点的左孩子不为空，说明j不为i的最左孩子，则j为其前一个兄弟的右孩子{table[k].rchild=j;k=j;}}}printf(n您输入的树转化为二叉树表示为：