数据结构课程设计报告-最短路径算法-二叉树的三种遍历

1、数据结构课程设计报告班 级： 计算机科学与技术132班 姓 名： 赖恒财 指导教师： 董跃华 成 绩： 32 信息工程学院 2015 年 7月 8日目录图的最短路径算法实现1.需求分析11.1 程序设计内容11.2 设计要求12.概要设计23.详细设计23.1 数据类型的定义23.2 功能模块的设计23.3 主程序流程94.调试分析104.1 问题回顾和分析104.2.经验和体会115.测试结果12二叉树的遍历1.设计目的132.需求分析142.1课程设计的内容和要求142.2选题的意义及背景143.概要设计143.1设计思想143.2程序数据类型163.3程序模块分析163.3.1置空栈16

2、3.3.2入栈173.3.3出栈173.3.4取栈顶操作173.3.5判空栈173.4函数关系：184.详细设计184.1二叉树算法程序截图和结果185.程序测试结果及问题分析196.总结20参考文献21附录122附录22630图的最短路径算法实现 -基于floyd最短路径算法1. 需求分析设计校园平面图，所含景点不少于8个。以图中顶点表示学校内各景点，存放景点的名称、景点介绍信息等；以边表示路径，存放路径长度信息。要求将这些信息保存在文件graph.txt中，系统执行时所处理的数据要对此文件分别进行读写操作。1.1 程序设计内容1从文件graph.txt中读取相应数据, 创建一个图,使用邻接

3、矩阵表示图 ；2景点信息查询：为来访客人提供校园任意景点相关信息的介绍；3问路查询：为来访客人提供校园任意两个景点之间的一条最短路径 。1.2 设计要求(1) 程序要具在一定的健壮性，即当输入数据非法时，程序也能适当地做出反应。(2) 程序要添加适当的注释，程序的书写要采用缩进格式。(3) 根据实验报告模板详细书写实验报告，在实验报告中给出校园平面图。(4) 校园平面图中的校园景点信息保存在文件graph.txt中。2.概要设计此程序主要实现以下几个模块, 基于下面几个模块完全可以实现此题要求.(1). 图的创建(2). 输出提供可选查询景点(3). 景点介绍查询处理(4). 查找两景点间的最

4、短路径(5). Floyd算法(核心)3.详细设计3.1 数据类型的定义typedef struct char name100;/名字char info10000;/介绍VertexType; /顶点结构typedef struct VertexType vexs10;int arcs100100; /邻接矩阵int vexnum,arcnum;/顶点个数，边的个数 MGraph;/图结构校园道路是双向通行的，可设校园平面图是一个带权的无向图，用邻接矩阵表示此无向网。邻接矩阵的数据类型定义如下：3.2 功能模块的设计3.2.1 图的创建void initGraph() freopen(&quo

5、t;graph.txt", "r", stdin);/打开文件scanf("%d %d", &mg.vexnum, &mg.arcnum);/读取顶点数、边数/循环输入景点、景点介绍for (int i = 0; i < mg.vexnum; i+) scanf("%s %s", &, &);/初始化矩阵，任意两点之间没有路for (int i = 0; i < 100; i+) for (int j = 0; j < 10

6、0; j+) mg.arcsij = 999999;/999999相当于无穷大/输入距离for (int i = 0; i < mg.arcnum; i+) char from100;/开始结点名char to100;/结束结点名/f表示开始结点编号，t表示目的结点编号，dis表示两点间的距离int f, t, dis;scanf("%s %s %d", &from, &to, &dis);/把景点名字换成编号for (int j = 0; j < mg.vexnum; j+) if (strcmp(, from

7、) = 0) f = j;if (strcmp(, to) = 0) t = j;/创建邻接矩阵mg.arcsft = dis;mg.arcstf = dis;floyd();/floyd算法计算各两点之间的最短路径，后文定义freopen("CON", "r", stdin);/改变输入流校园平面图可以表示成为一个无向网，用一个MGraph 类型的变量 mg表示这张无向网。网中包含了景点的名字和信息，以及表示各景点之间是否有路可达邻接矩阵，同时还保存了景点个数和边数。其俱体定义如下：Graph.txt8 15 校门江西理工大学

8、校门主教学校教学主楼，有11层二教学校二号教学楼图书馆 供学生自习或借书体育场一个大的田径场，包括足球场，女生宿舍 生女生住宿的地方南门?学校通向外面的一个小门蕙莘园食堂 学校有三个食堂，其中一个就是蕙莘园食堂，靠近男生宿舍。校门 图书馆 110校门 主教 30校门 体育场 70校门 南门 90校门 女生宿舍 110主教 图书馆 50主教 二教 10二教 蕙莘园食堂 50二教 体育场 30图书馆 体育场 70图书馆 蕙莘园食堂 60体育场 蕙莘园食堂 40体育场 南门 40南门 女生宿舍 20蕙莘园食堂 女生宿舍 130程序中用到的关于学校各景点及信息的的数据保存在graph.txt文件中，文

9、件的具体信息如下：graph.txt 文件中的格式是，第一行包括两个整数，第一个整数是景点的个数n, 也就是图中的结点个数，第二个整数是边的数量m。接着n行数据分别是学校的每个景点（结点），每个景点后的是对景点的介绍。再接着的m行是路径信息，每条路径信息有三部分数据组成，分别是起始结点，终止结点，和它们之间的路径长度。3.2.2 提供可选景点提供可选景点信息这一模块，是向用户展示从graph.txt文件中读取到的学校的各大景点，告诉用户提供的可查看的景点有哪些。景点信息用一个for循环输出。此外为了方便对景点的各项操作，我们在输出所有可选景点的同时还为它们进行了数字编号，在后面的查询或找路过程

10、中还需要输入烦琐的景点名称，只需要输入想要查询的景点的对应编号即可进行操作。简单方便，实用，用户体验性好。/输出可选景点，并进行编号void outPlace() printf("本校景点有：n");for (int i = 0; i < mg.vexnum; i+) printf("ttt%d、%sn",i, );printf("n");输出提供的可选景点的代码如下：3.2.3 景点信息查询处理景点信息查询处理这一模块，要求用户输入要查询的景点的编号，根据用户输入的查询景点信息指令，判断要查询的景点，

11、并同时作出反应，向用户展示景点的具体信息。作为算法的健壮性，这一模块在用户输入查询指令后，判断用户输入的指令的合法性，防止出现异常。/景点信息查询处理void outInfo() int n;printf(" -n");printf("| 您选择了 1.查询景点信息 |n");printf(" -n");printf(">>>>>>请选择您要查询的景点（0 - %d） :n", mg.vexnum);scanf("%d", &n);if (n >

12、= 0 && n < mg.vexnum) printf("t%s:ntt%snn", , );else printf("您输入的数据有误！n");具体实现代码如下：3.2.4 查找两景点的最短路径查找两景点的最短路径模块，同景点信息查询处理模块相似。只不过是所处理的事情不一样。查找两景点的最短路径模块要求用户输入要查询的两景点的编号a , b（a表示开始结点， b表示终止结点）。然后程序会对用户输入的查询指令进行判断合法性，如果用户输入的指令合法，则告诉用户所查询到的最短路径。如

13、果输入指令不合法，则提醒用户输入的数据有误。/两景点最短路径的查询void mindistance() int a, b;printf(" -n");printf("| 您选择了 2.查找最短路径 |n");printf(" -n");printf(">>>>>>请输入要查询的两景点 a b（a b表示景点编号）:n");scanf("%d %d", &a, &b);if (a >= 0 && a < mg.vexn

14、um && b >= 0 && b < mg.vexnum) printf("n -n");printf("| 起始地 | 目的地 | 最短路径 |n");printf(" -n");printf("| %s | %s | %4d |n", , , mg.arcsab);printf(" -nn");elseprintf("输入有误！n");具体实现代码如下：3.2.5 Floyd

15、算法计算任意两点间的最短路径（重点）在这个问题中需要用到floyd算法，这是此问题中的核心重点，也是难点,下面也将重点介绍。Floyd算法又称为插点法，是一种用于寻找给定的加权图中多源点之间最短路径的算法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。路径矩阵：通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。从图的带权邻接矩阵A=a(i,j) n×n开始，递归地进行n次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)；又用同样地公式由D(1)构造出D(2)；最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩

16、阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径。采用松弛技术（松弛操作），对在i和j之间的所有其他点进行一次松弛。所以时间复杂度为O(n3)。状态转移方程：其状态转移方程如下： mapi,j:=minmapi,k+mapk,j,mapi,jmapi,j表示i到j的最短距离，K是穷举i,j的断点，mapn,n初值应该为0，或者按照题目意思来做。当然，如果这条路没有通的话，还必须特殊处理，比如没有mapi,k这条路。算法过程：1，从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边

17、相连，则权为无穷大。2，对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果是更新它。把图用邻接矩阵G表示出来，如果从Vi到Vj有路可达，则Gi,j=d，d表示该路的长度；否则Gi,j=无穷大。定义一个矩阵D用来记录所插入点的信息，Di,j表示从Vi到Vj需要经过的点，初始化Di,j=j。把各个顶点插入图中，比较插点后的距离与原来的距离，Gi,j = min( Gi,j, Gi,k+Gk,j )，如果Gi,j的值变小，则Di,j=k。在G中包含有两点之间最短道路的信息，而在D中则包含了最短通路径的信息。比如，要寻找从V5到V1的路径。根据D

18、，假如D(5,1)=3则说明从V5到V1经过V3，路径为V5,V3,V1，如果D(5,3)=3，说明V5与V3直接相连，如果D(3,1)=1，说明V3与V1直接相连。/Floyd 算法计算任两点间的最短路径void floyd() int i, j, k;for (i = 0; i < mg.vexnum; i+) for (j = 0; j < mg.vexnum; j+) for (k = 0; k < mg.vexnum; k+) if (mg.arcsjk >= (mg.arcsik + mg.arcsij) mg.arcsjk = mg.arcsik + mg

19、.arcsij;在符合本问题时的Floyd算法的具体实现代码如下：3.3 主程序流程在主程序中，首先通过 initGraph() 读取图文件并创建图信息，然后展示用户可选择的菜单，用户根据菜单提示进行操作。用户输入指令后，系统根据用户的输入指令进行 1、景点信息查询 2、最短路径的查询。如果是用户要求查询景点信息，输入了相应的指令，则系统调用景点信息查询模块outInfo() 。如果用户要求查询景点信息，并输入了相应的指令，则系统调用最短路径查询模块 mindistance() 结束退出具体操作流程如下图：结束退出指令是否合法用户输入指令输出可选操作菜单开始创建图信息图退出指令查询景点信息指令

20、最短路径指令是否outInfo()mindistance() .314.调试分析4.1 问题回顾和分析在程序设计中的遇到的问题有;1、 文件读取和操作。2、 输入文件的字符编码的选择。3、 求最短路径算法的选择。问题1、文件的读取操作。起初用了好多种文件操作的方法，不知道用哪种方式读取文件，最后看见同学用了一种文件读取方式可以正确读取文件，于是就把那个方法给引用过来了。问题2、输入文件的字符编码的选择。由于不同的编译器对字符编码的要求不一，所以要选择正确的字符编码，程序可以正确地读取文件并显示。问题3、求最短路径算法的选择。最初对于最短路径算法，我首先想到的是Dijkstra算法,但后来发现D

21、ijkstra算法每次只能计算两点之间的最短路径，在这个问题中用起来比较烦琐，最后发现Floyd算法可以很好地解决这个问题，于是毫不犹豫地选择了Floyd算法。4.2.经验和体会通过这次数据结构课程设计我觉得要设计一个程序不简单，尤其是要设计出一个很好的程序，那更是难上加难，在今后的学习中还要不断加强自己设计程序的能力，进行更多的程序设计实践，提高设计程序和写程序的水平。5.测试结果二叉树的三种遍历 -基于栈的非递归遍历1.设计目的数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。因此，主要有三个方面的内容：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算法

22、）。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。在当今信息时代，信息技术己成为当代知识经济的核心技术。我们时刻都在和数据打交道。比如人们在外出工作时找最短路径，在银行查询存款、通过互联网查新闻、以及远程教育报名等，所有这些都在与数据发生关系。实际上，现实世界中的实体经过抽象以后，就可以成为计算机上所处理的数据。数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数

23、学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。通过此次课程设计主要达到以下目的：1、 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；2、 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3、 提高综合运用所学的理论知识和方法独立分析和解决问题的能力；四训练用系统的观点和软件开发

24、一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风2.需求分析2.1课程设计的内容和要求二叉树的遍历: 对任意给定的二叉树（顶点数自定）建立它的二叉链表存贮结构，并利用栈的五种基本运算（置空栈、进栈、出栈、取栈顶元素、判栈空）实现二叉树的先序、中序、后序三种遍历，输出三种遍历的结果。2.2选题的意义及背景二叉树的链式存储结构是用指针建立二叉树中结点之间的关系。二叉链存储结构的每个结点包含三个域，分别是数据域，左孩子指针域，右孩子指针域。因此每个结点为leftchild data rightchild 由二叉树的定义知可把其遍历设计成递归算法。共有前序遍历、中序遍历、后序遍历。可

25、先用这三种遍历输出二叉树的结点。采用递归算法设计，以前序遍历为例，它要求首先要访问根节点，然后前序遍历左子树和前序遍历右子树。特点在于所有未被访问的节点中，最后访问结点的左子树的根结点将最先被访问，这与堆栈的特点相吻合。因此可借助堆栈实现二叉树的递归遍历。将输出结果与递归结果比较来检验正确性，因此程序结果可做成菜单方便这两种算法的结果查看。3.概要设计3.1设计思想所谓遍历二叉树，就是遵从某种次序，访问二叉树中的所有结点，使得每个结点仅被访问一次。这里提到的“访问”是指对结点施行某种操作，操作可以是输出结点信息，修改结点的数据值等，但要求这种访问不破坏它原来的数据结构。我们访问是输出结点信息d

26、ata，且以二叉链表作为二叉树的存储结构。由于二叉树是一种非线性结构，每个结点可能有一个以上的直接后继，因此，必须规定遍历的规则，并按此规则遍历二叉树，最后得到二叉树所有结点的一个线性序列。令L,R,D分别代表二叉树的左子树、右子树、根结点，则遍历二叉树有6中规则：DLR、DRL、LDR、LRD、RDL、RKD。若规定二叉树中必须先左后右（左右顺序不能颠倒），则只有DLR、LDR、LRD三种遍历规则。称DLR先序遍历，LDR中序遍历，LRD后序遍历。3.1.1先序遍历二叉树若二叉树非空，依次进行如下操作：（） 访问根结点（） 先序遍历左子树（） 先序遍历右子树3.1.2中序遍历二叉树若二叉树非

27、空，依次进行如下操作：（1）中序遍历左子树（2）访问根结点（3）中序遍历右子树3.1.3后序遍历二叉树若二叉树非空，依次进行如下操作： （1）后序遍历左子树 （2）后序遍历右子树（3）访问根结点3.2程序数据类型 typedef struct BiTNodechar data;struct BiTNode *LChild; struct BiTNode *RChild; BiTNode,*BiTree;typedef struct snodeBiTNode pp;struct snode *next; linkstacknode,*linkstack;3.3程序模块分析3.3.1置空栈link

28、stack InitBiTree()Linkstack top;top=(linkstack)malloc(sizeof(struct snode);if(!top) printf(“EROORn”);top=NULL;return top;3.3.2入栈void Push(linkstack top,BiTNode x)linkstack temp;temp=(linkstack)malloc(sizeof(struct snode);temp->pp=x;temp->next=top->next;top->next=temp;3.3.3出栈BiTNode Pop(l

29、inkstack top)BiTNode ss;linkstacknode *temp;temp=top->next;top->next=temp->next;ss=temp->pp;return ss;3.3.4取栈顶操作int getTop(BiTree T,char &e)if(!T)return 0;e=T->data;return 1;3.3.5判空栈int linkstackempty(linkstack top)if（！top） return 1;else return 0; 3.4函数关系：图3.4.1 函数间的关系4.详细设计4.1二叉树

30、算法程序截图和结果例如：输入二叉树为：A(B(,D(E,F),C(G(,H(I,J),K)。 它的前序遍历为：ABDEFCGHIJK 它的中序遍历为：BEDFAGIHJCK 它的后序遍历为：EFDBIJHGKCA AB C D 当输入数据为 A(B(,D(E,F),C(G(,H(I,J),K) 显示结果如下：图4.1.15.程序测试结果及问题分析 通过与递归的遍历结果相比较之后，用堆栈实现的非递归遍历算法得出了正确的遍历结果，可以对二叉树进行遍历操作。但是程序中树的结点已经建立好不能随意改动这确实是一个缺点因此可以进行改进，可以用递归的方法建立一棵二叉树，先建立左子树，在建立右子树这样用户输入

31、的字符可以直接用来建树程序的灵活性会更强。6.总结 通过一周的数据结构实训，进一步加深了对数据结构整体的理解，明白了链表的各种操作的实质，并且对老师课上讲的各种算法进行了实际的运用，更加掌握了各种算法的使用方法，例如链表的创建，查找，插入，二叉树的遍历等算法。 而且，通过这一次的实训，不仅加深了对数据结构知识的了解，更复习了以前学习过的C语言，重新复习了栈等经典算法，而且对于以前不懂得地方，例如主函数与子函数之间的实参，形参之间的传递，并且在二叉树的遍历部分复习了递归算法的使用。这一周的实训，我深刻的领悟到，遇到困难，一定不要畏惧，自己多动脑思考思考，所联系自己以前学过的知识，便会有很大的进展

32、，还有就是，往往一些错误都不是编写的逻辑错误，而是一些小错误点，例如忘记另外一部分的大括号，忘记分号等等，这提醒自己以后要细心，不要错在一些小问题上。 在这次课程设计中在，虽然不会成功的编写一个完整的程序，但是在看程序的过程中，不断的上网查资料以及翻阅相关书籍，通过不断的模索，测试，发现问题，解决问题和在老师的帮助下一步一步慢慢的正确运行程序决问题，终于完成了这次课程设计，虽然这次课程设计结束了但是总觉得自已懂得的知识很是不足，学无止境，以后还会更加的努力深入的学习。参考文献1严蔚敏，吴伟民数据结构（C语言版），北京：清华大学出版社，2009.2顾泽元，刘文强，数据结构（C语言版），北京：北京

33、航空航天大学出版社，20113徐德民.最新C语言程序设计M电子工业出版社1992年4唐策善，黄刘生.数据结构M中国科学技术出版社.1992年5仲萃豪，冯玉琳.程序设计方法学M北京科学技术出版社1985年6 宁正元，王秀丽，算法与数据结构 清华大学出版社，2006 7 谭浩强， 数据结构教程上级实验指导 清华大学出版社，2008. 8 朱站立，数据结构-使用C语言西安：西安交通大学出版社，2004. 附录1最短路径源代码:#include <iostream>#include <stdio.h>#include <string>#include <alg

34、orithm>using namespace std;const int MAXPLACE = 100;typedef structchar name100;char info10000;VertexType; /顶点结构typedef structVertexType vexs10;int arcs100100;/邻接矩阵int vexnum, arcnum;/顶点个数，边的个数 MGraph; /图结构MGraph mg;void floyd() int i, j, k;for (i = 0; i<mg.vexnum; i+)for (j = 0; j<mg.vexnum

35、; j+)for (k = 0; k<mg.vexnum; k+)mg.arcsij = min(mg.arcsij, mg.arcsik + mg.arcskj);void initGraph() freopen("graph.txt", "r", stdin);scanf("%d %d", &mg.vexnum, &mg.arcnum);/输入景点信息for (int i = 0; i < mg.vexnum; i+) scanf("%s %s", &mg.vexsi.nam

36、e, &);/初始化矩阵for (int i = 0; i < 100; i+) for (int j = 0; j < 100; j+) mg.arcsij = 999999;/输入距离for (int i = 0; i < mg.arcnum; i+) char from100;char to100;int f, t, dis;scanf("%s %s %d", &from, &to, &dis);/把景点换成编号for (int j = 0; j < mg.vexnum; j+) if

37、(strcmp(, from) = 0) f = j;if (strcmp(, to) = 0) t = j;/创建邻接矩阵mg.arcsft = dis;mg.arcstf = dis;floyd();/算出各两点之间的最短路径freopen("CON", "r", stdin);void outPlace() printf("本校景点有：n");for (int i = 0; i < mg.vexnum; i+) printf("ttt%d、%sn",i

38、, );printf("n");void outInfo() int n;printf(" -n");printf("| 您选择了 1.查询景点信息 |n");printf(" -n");printf(">>>>>>请选择您要查询的景点（0 - %d） :n", mg.vexnum);scanf("%d", &n);if (n >= 0 && n < mg.vexnum) pri

39、ntf("t%s:ntt%snn", , );else printf("您输入的数据有误！n");void mindistance() int a, b;printf(" -n");printf("| 您选择了 2.查找最短路径 |n");printf(" -n");printf(">>>>>>请输入要查询的两景点 a b（a b表示景点编号）:n");scanf("%d %d&

40、quot;, &a, &b);if (a >= 0 && a < mg.vexnum && b >= 0 && b < mg.vexnum) printf("n -n");printf("| 起始地 | 目的地 | 最短路径 |n");printf(" -n");printf("| %s | %s | %4d |n", , , mg.arcsab);printf("

41、-nn");elseprintf("输入有误！n");int main() int a;initGraph();outPlace();while (1) printf(" -n");printf("| 您有以下选择： |n");printf(" -n");printf("| |n");printf("| 1.查询景点t 2.查找最短路径 |n");printf("| |n");printf(" -n");printf(&quo

42、t;| 输入对应编号执行相应操作，输入 -1 结束操作 |n");printf(" -n");scanf("%d", &a);if (a = -1) break;if (a = 1) outInfo();if (a = 2) mindistance();return 0;附录2二叉树遍历源代码:#include <stdio.h>#include <iostream>#include <stack>using namespace std;#define MaxSize 100#define MaxWi

43、dth 40typedef char ElemType;typedef struct nodeElemType data;struct node *left, *right;int isOut = 0; /访问次数(后序遍历会用到) BTree;void creatree(BTree *BT, char *str)BTree *stackMaxSize, *p;int top = -1, k, j = 0;/*top为栈指针,k指定是左还是右孩子,j为str指针*/char ch;*BT = NULL;ch = strj;while (ch != '0')switch (ch)

44、case '(':top+; stacktop = p; k = 1; /*为左结点*/break;case ')':top-;break;case ',':k = 2; /*为右结点*/break;default: p = (BTree *)malloc(sizeof(BTree);p->data = ch; p->left = p->right = NULL; p->isOut = 0;if (*BT = NULL) /*根结点*/*BT = p;elseswitch (k)case 1:stacktop->le

45、ft = p;break;case 2:stacktop->right = p;j+;ch = strj;void disptree(BTree *BT) BTree *stackMaxSize, *p;int levelMaxSize2, top, n, i, width = 4;if (BT != NULL)printf("n凹入表示法:n");top = 1;stacktop = BT; /*根结点入栈*/leveltop0 = width;while (top>0)p = stacktop; /*退栈并凹入显示该结点值*/n = leveltop0;fo

46、r (i = 1; i <= n; i+) /*其中n为显示场宽,字符以右对齐显示*/printf(" ");printf("%c", p->data);for (i = n + 1; i <= MaxWidth; i += 2)printf("");printf("n");top-;if (p->right != NULL) /*将右子树根结点入栈*/top+;stacktop = p->right;leveltop0 = n + width; /*显示场宽增width*/leveltop1 = 2;if (p->left != NULL) /*将左子树根结点入栈*/top+;stacktop =