打印二叉树.doc

合肥学院计算机科学与技术系课程设计报告20082009学年第二学期课程数据结构与算法课程设计名称打印二叉树结构学生姓名詹书保学号0704032008专业班级07网工（2）班指导教师张贯虹 屠菁2009年5月题目：打印二叉树结构一、问题分析和任务定义：1、问题分析本设计要求按凹入表形式横向打印二叉树结构，即二叉树的根在屏幕的最左边，二叉树的左子数在屏幕的下边，二叉树的右子数在屏幕的上边。图1 二叉树结构示意图由题意和图示可以看出，在根结点A右边的结点即A的右子树（CEF）待横向打印后都在它的上方打印出来，在根结点A左边的结点即左子树(BD)都在它的下方打印出来。同理类推，结点C左边的结点即左子树(EF)都在C的下方，而C结点没有右孩子，所以C结点打印出来的位置为第一行，由此看出可以利用RDL（中序）递归的遍历方法来遍历二叉树，通过RDL递归遍历方法实现结点的纵向位置。并且还可以看出处于第一层的A结点的纵向位置是第一列，而第二层的B、C结点的纵向位置是第二列，依此类推，所以可以利用结点的深度来控制各结点的横向位置，在屏幕上打印出树形结构。2、任务定义（1）建立二叉树，构造任意的二叉树，对于不同的二叉树，输出不同的二叉树图形。要求：对所设计的二叉树图形，能够在屏幕上横向打印。（2）在依次按从上到下从左到右的次序依次输入二叉树结点（其中包括虚结点）在屏幕上输出二叉树形状（不包括输入的虚结点）。（3）对所设计的二叉树能够实现二叉树的中序遍历，具有实际的应用：二叉树的根结点如何在屏幕的最左边，右孩子如何在屏幕的上方以及左孩子如何在屏幕的下方。如何实现对各结点的横向位置的控制。二、概要设计和数据结构选择1、二叉树的存储结构对于任意的二叉树来说，每个结点最多有两个孩子。采用链接方式存储时，我们设计每个结点除了存储结点本身的数据（data）外，还应至少包括两个指针域：左孩子（lchild）指针域和右孩子(rchild)指针域。由于要用结点的深度控制各结点的横向位置，故在二叉树存储结构中加入结点的度(degree)，但这个度于二叉树的度有所不同，就是处于第一层的根的度数为0，而第二层的度数加1，以此类推，同层次的兄弟结点的度数是相同的，这样就容易解决结点的深度控制结点的横向位置的问题了。结点结构如下：lchilddatadegreerchild图2 结点结构示意图结点类型描述如下：typedef struct nodechar data;struct node *lchild,*rchild;int degree;Bitree;2、建立二叉树的算法思想 （1） 对一般的二叉树添加若干个虚结点，使其成为完全二叉树，然后依次输入结点信息，若其不是虚结点，则建立一个新结点。（2） 若新结点是第一个结点，则令其为根结点，否则将新结点作为孩子链接到它的父结点上。（3） 重复（1）、（2），直至输入信息#时为止。该算法实现的关键在于如何将新结点作为左孩子或右孩子链接到他的父结点上，为此，可设置一个队列，该队列是一个指针类型的树组，保存已输入的结点的地址。因为是按层自左向右输入结点的，所以先输入的结点的孩子结点先进入队列。具体操作如下：（1） 令对头指针front指向当前与其孩子结点建立链接的父结点，队尾指针rear指向当前输入的结点。初始时，front=1,rear=0。s-degree=0;/将根结点degree置0（2） 若rear为偶数，则该结点为父结点的左孩子；若rear为奇数，则为父结点的右孩子。若父结点或孩子结点为虚结点，则无需链接。（3） 若父结点与其两个孩子结点链接完毕，则令front=front+1,使front指向下一个等待链接的父结点。(在此之前s-degree=Qfront-degree+1;用来记录结点的深度)。3、RDL递归遍历二叉树递归算法思想若二叉树为空，则操作结束，否则依次执行如下3个操作。（1） RDL遍历右子树，调用RDL递归遍历二叉树算法。（2） 访问根结点。（3） RDL遍历左子树，调用RDL递归遍历二叉树算法。假设T为根指针，则遍历二叉树时，分别遍历以T-lchild和T-rchild为根指针的子树。算法如下：void Inorder(Bitree *T)if(T)Inorder (T-rchild);printf(%4cn,T-data);Inorder (T-lchild);4、利用结点的深度控制结点的横向位置的算法思想for(int i=0;idegree;i+)/利用结点的度来控制结点的横向位置printf(t);printf(%4cn,T-data);/访问根5、结构图main()Creatree()Inorder(Bitree *T)introduce()图3 程序模块结构图6、建立二叉树流程图 开始定义结点类型T=NULL置空二叉树 ch=getchar();ch!=#ch!=s-data=ch;s-lchild=s-rchild=NULL;rear+;Qrear=s;rear= =1T=s;输入的第一个结点为根结点s!=NULL&Qfront!=NULLrear%2= =0Qfront-lchild=s;s-degree=Qfront-degree+1;rear%2= =0front+; 结束图4 二叉树的建立流程图三、详细设计编码1、算法思想首先建立二叉树（其中二叉树的每个结点的深度要弄清楚）；其次用中序遍历（右根左）：其中右根左遍历的前后顺序控制了纵向位置由其结点的深度控制；（1）对于二叉树的建立：依次输入结点信息，若其不是虚结点，则建立一个新结点；若新结点是第一个结点，则令其为根结点，且其深度为一。否则将新结点作为孩子结点链接到它的父结点上，且其结点的深度为父结点深度加一。当输入字符“#”时，停止输入。该算法实现的关键在于如何将新结点作为左孩子或右孩子结点链接到它的父结点上，为此，可设置一个队列，该队列是一个指针类型的数组，保存已输入结点的地址。具体操作如下：（i）令队头指针front指向当前与其孩子结点建立链接的父结点，队尾指针rear指向当前输入的结点。初始是，front=1,rear=0.（ii）若rear为偶数，则该结点为父结点的左孩子；若rear为奇数，则为结点的右孩子。若父结点或孩子结点为虚结点，则无需链接。（iii）若父结点与其两个孩子结点链接完毕，则令front=front+1,使front指向下一个等待链接的父结点。（2）中序遍历控制二叉树纵向位置，具体操作如下：对二叉树的遍历是在对各子树分别遍历的基础上进行的，而各子树的遍历与整个二叉树的遍历方法相同。若二叉树为空，则操作数结束，否则依次执行如下3个操作：（i）中序遍历右子树。（ii）访问根。（iii）中序遍历左子树。在访问根时，利用define maxsize 20二叉树的最大允许深度控制for语句。用for循环语句（for(i=1;idata=ch;s-lchild=s-rchild=NULL;s-degree=0;/将根结点degree置0rear+;Qrear=s;/将虚结点指针NULL或新结点地址入队if(rear=1) T=s;/输入的第一个结点为根结点elseif(s!=NULL&Qfront!=NULL)/孩子和双亲结点均不是虚结点if(rear%2=0) Qfront-lchild=s;else Qfront-rchild=s;s-degree=Qfront-degree+1;/存储各结点度if(rear%2=1) front+;/结点*Qfront的两个孩子已处理完毕front+1ch=getchar();return T;以上是二叉树的建立函数，屏幕首先出现请输入数据。如果输入的字符不为“#”时，可重复输入多个结点。当输入的是虚结点时，则此结点不可与实结点链接。其左右孩子必须为虚结点。由上算法当rear20时,rear为偶数，rear 所指的结点为左孩子。当rear%2!=0时，输入的为右孩子。当右孩子链接完，front加一，front指向下一个等待链接孩子结点的父结点。输入的二叉树有两种情形，一种是没有虚结点，另一种是有虚结点。例：如输入ABCDEF#，则此树的形成过程如图所示：AABABCABCDABCDEABCDEF图5 二叉树形成示意图（2）RDL遍历二叉树递归算void Postorder(Bitree *T)if(T)/若二叉树不空Inorder (T-rchild); /RDL遍历左子树for(int i=0;idegree;i+)/利用结点的度来控制结点的横向位置printf(t);printf(%4cn,T-data);/访问根Inorder (T-lchild); /RDL遍历右子树二叉树的输出可以由中序遍历控制结点纵向位置以及二叉树建立时结点深度控制结点的横向位置。规定最大深度不超过规定的数量M。其中每个结点占用一行，当遍历的结点的深度与横向位置相同时，则输出结点，否则输出空格。对上例进行如上算法，其过程如下图：CCFFECBDAFECAFECDAFEC图6 例图的输出结构四、上机调试1、调试中遇到的问题与解决办法(1) 虚结点无法识别，输入时只能输入实结点。于是选择暂不输入虚结点。(2) 在无虚结点存在的情况下，输入二叉树，可显示结果不正确，只能输出一个结点即中序遍历的首结点，且输出的横向位置与其深度不匹配。返回二叉树的输出函数中检查输出的语句，发现递归未实现。(3) 所输入的结点都能够输出时，但横向位置不正确。经调试发现编写结点深度语句不正确。根据孩子结点深度是父结点深度加一这个思想，另所加结点是front 指针所指结点深度加一。(4) 当输入无虚结点二叉树时，打印结果正确。定义当输入时说明此结点为虚结点，与此结点链接的父结点不存在左或右孩子。(5) 能够输入虚结点时，任意输入结点，结果不正确。经检查发现，输入的结点不能是任意的，必须能够成为一个二叉树状。如若此结点无左右孩子，则此左右孩子结点为虚结点，虚结点不能有实左右孩子。(6) 经过多次调试，在正确输入数据的情形下，结果显示正确。2、算法性能分析建二叉树运算Creatree(Bitree * T)中，算法花费时间最多的操作是while循环中插入元素的语句。While循环体语句执行的次数由插入元素的总个数（即n）的值决定。也就是说，循环体中语句会执行n次，则该算法的时间复杂度为O（n）。建二叉树的运算执行时所需的空间是动态申请的，都是用于存储算法本身所用的指令、常数、变量的，算法的空间性能较好。3、设计体会经过这次数据结构课程设计，不但再次巩固了C语言、C以及数据结构所学知识，更加很好的将这三门专业课的知识融会贯通。由于要设计出甚至完成这样一个比较复杂的程序，涉及到的不仅仅是课堂上书本上那些简单的知识，更需要我们去多方面的查阅资料，学会利用各种可能的资源，让自己自主的去学习去学以致用。学会查阅资料也是一种需要培养的能力，无论基础知识学得有多牢固基础有多扎实，也同样需要我们多看其他相关的书籍，查阅资料，找到更好的解决方法，以求简单明了一目了然。让自己解决问题的能力更上一层楼。对于一个问题，需要多想，多方面考虑，不能仅仅只看到了它的一方面或两面，而要多方面观察，以求运用最好的易懂的方式解决。只有将所有的问题都考虑到了，这个程序才算完整的，没有缺陷的。就像操作系统，由原来的单处理机系统逐步变为多处理机系统，到现在的windows xp。这些都是问题更加一步步不断完善的过程。编写程序的过程和思想一样重要，对于刚开始编写的以及过后修改之后的，都要相互比对，将过去好的得到保留，不好的继续修改升华，最后得到比较完善的满意的结果。在课程设计过程中有过因不知如何解决而忧愁，有过因同一个意思显示不同的结果而埋怨，有过因差一点点就成功了而不甘心，有过因解决问题而喜悦而自豪。经过多次的课程设计，真得是让我深深爱上了编写程序，调试程序。因为它给了我五彩的世界，充实的生活，有成就感的心情。当然，这次设计，编写程序的过程中遇到了很多问题很多麻烦，有的已经通过各种方法得到了解决，但有的还需要继续查阅相关书籍，以求精益求精。五、测试结果及其分析测试数据：1、建立含有虚结点的二叉树：ABCDEF#运行结果如下：图7 含有虚结点的二叉树运行示意图2、建立无虚结点的二叉树：ABCDEFGHIJKLMNO#运行结果如下：图8 无虚结点的二叉树运行示意图3、建立含有虚结点的二叉排序树：5 2 7 1 4 6 9 3 8 #运行结果如下：图9 含有虚结点的二叉排序树运行示意图六、用户使用说明按完全二叉树的层次的顺序，根据屏幕提示信息，依次输入各结点信息建立一棵运用链式存储的二叉树。对于一般的非完全二叉树，须添加一些虚结点，使其成为一颗完全二叉树。例如，对于问题分析里所给的二叉树，按照完全二叉树的结点顺序输入的结点序列为：ABCDEF#。其中，表示虚结点，#是输入结束的标志。不过，如果虚结点是在末尾的，也可以省略不写。即上述二叉树也可以写成：ABCDEF#。输入结束后按下回车键“Enter”即可观察到输入二叉树的打印结果。按以上的操作也可以输入其他二叉树结点信息，输入后即可看到你想看到的结果。七、参考资料1 谭浩强 C程序设计 清华大学出版社 2005年7月第三版2 王昆仑 李红 数据结构与算法 中国铁道出版社2007年6月第一版3 赵坚 姜梅 数据结构（C语言版）中国水利水电出版社 2005年8月第一版八、附录课程设计打印二叉树程序源程序如下：#include#include#define maxsize 20typedef struct node/定义二叉树的数据结构类型char data;/数据struct node *lchild,*rchild;/左右子树int degree;/该结点的度Bitree;Bitree *Qmaxsize;/ 队列Q为指针类型Bitree *Creatree()/建立二叉树，返回根指针char ch;int front,rear;Bitree *T,*s;T=NULL;/置空二叉树front=1;rear=0;/置空队列printf(创建一棵二叉树(注：-虚接点标志，#-结束标志)n);printf(请输入结点信息:n);ch=getchar();/输入第一个结点信息while(ch!=#)/不是结束符号时继续s=NULL;/如果输入的是虚结点，则无需为虚结点申请空间if(ch!=)/表示虚结点，不是虚结点时建立新结点s=(Bitree *)malloc(sizeof(Bitree);s-data=ch;s