苏慧哲 刘杰

摘要：数据结构内容的高抽象性、强逻辑性和算法复杂性始终是学生学习的一个难点。为便于学生理解算法，将算法结果可视化，即输出直观的图像。以建立并输出二叉树的图像为例介绍如何层次遍历输出描述二叉树的DOT文件，在Graphviz软件中查看二叉树图像结果。

关键词：二叉树;层次遍历;结果可视化;dot;graphviz

中图分类号：G642       文献标识码：A        文章编号：1009-3044（2018）36-0247-03

Abstract： High abstraction， strong logic and complex algorithm of data structure are always difficult for students to learn. In order to facilitate students to understand the algorithm， the algorithm results are visualized， that is， the output of intuitive images.Taking the image of building and outputting binary tree as an example， this paper introduces how to output the DOT file of describing binary tree hierarchically and view the result of binary tree image in Graphviz software.

Key words： binary tree; hierarchy traversal; result visualization; dot; graphviz

在計算机科学与技术中，数据结构介于数学、计算机软硬件之间，由于其独特的地位使其成为计算机专业的核心基础课程。数据结构课程偏重理论，内容抽象，注重理解，同时又要求学生能够将抽象的思维转化为在计算机可以操作的具体实践，因此数据结构是一门理论性和实践性都很强的课程[1]，其概念多、内容多、高抽象性、强逻辑性和算法复杂性始终是学生学习的一个难点[2]。

在教学过程中发现大部分学生的C语言掌握得不够扎实，尤其是指针部分，算法没有理解透彻。如果在教学过程中演示程序能直接输出直观的图形化结果，这样可以帮助学生调动和激发学生学习的积极性。

在数据结构中，树是非常重要的非线性结构，二叉树是一种特殊的树，遍历二叉树是二叉树的最基本的操作[3]。根据遍历序列来确定构造唯一的二叉树，是二叉树遍历算法的最基础的应用。以二叉树为例，先根据先序遍历的字符序列建立二叉链表，然后输出二叉树的图形。

为方便输出图形，只关注遍历算法，不用思考计算输出图形的坐标位置，因此不考虑在命令行中打印二叉树，而是采用DOT图形描述语言。DOT是纯文本图像描述语言，文件扩展名通常是.dot，需要有专门的程序处理这些文件并将其渲染成为图片。Graphviz是贝尔实验室开发的一个开源的图像可视化的软件，它使用dot作为脚本语言，然后使用布局引擎来解析此脚本，并完成自动布局。

因此根据先序遍历，建立唯一二叉树，然后层次遍历输出描述二叉树的DOT脚本文件，接下来用Graphviz图像可视化软件打开输出的DOT脚本文件，渲染即可得到二叉树图像。

1 根据先序遍历的字符序列建立二叉链表

首先声明二叉链表每个结点的抽象数据类型bitree，包括三个成员，一个数据data和左右两个指针lchild，rchild，还有指向该结点类型的指针Bitree。代码如图1所示。

然后根据给定的先序遍历得到的字符序列如AB#D##C##，一个一个扫描，递归建立二叉链表。构造的二叉链表如图2所示，代码如图3所示。

2 输出二叉树

要输出二叉树，采用层次遍历，即需要链队列结构来实现，因此先声明链队列每个结点的抽象数据类型LKQueNode，包括两个成员，指向二叉链表的结点类型bitree的data指针和指向LKQueNode类型的指针。为方便操作链队列，再声明链队列的抽象数据类型LKQue，包括两个指向链队列队头队尾的front和rear指针。代码如图4所示。

输出描述图像的DOT脚本文件应是可以被Graphviz渲染得到一个二叉树。根据DOT语法，主函数有2种，graph是无向图，digraph是有向图。在无向图中用—表述结点之间的关系，在有向图中用—>表述前一个结点指向后一个结点。要绘制的二叉树结点之间的连线并无箭头，因此选择无向图graph，用—描述结点之间的关系，DOT脚本内容如图5所示.

程序执行完毕输出一个文件，需要用到FILE文件类型以及打开文件fopen、关闭文件fclose和写文件fprintf函数。输出时采用链队列实现层次遍历，从而可以从上到下从左到右输出所有结点，和与该结点有关联关系的左右孩子结点的关系。代码如图6所示。

其中InitQueue（）、EmptyQueue（）、EnQueue（）、OutQueue（）和GetHead（）分别是队列的初始化、判断队列是否为空、入队、出队、取队首元素的队列基本操作。具体代码分别如图7，图8，图9，图10，图11所示。

3 主函数

先定义一个二叉链表Bitree变量T，然后在命令行中提示用户输入先序遍历得到的字符序列，用‘#代表空，接着根据用户输入的结点序列构造二叉链表，最后层次遍历输出tree.dot文件。代码如图12所示。

4 运行结果

先序遍历字符序列为AB#D##C##，执行结果如图13所示。

程序执行完后，在与该源程序相同路径下找到生成的tree.dot文件。然后用graphviz软件打开该文件，可以看到渲染得到的二叉树图像。代码如图14所示。

5 改进输出图像

但是二叉树严格区分左右子树，D结点从这张图中看不出是B结点的左孩子还是右孩子，因此采用隐藏结点的方法可以使得D结点显示为B结点的右孩子。修改输出函数PrintTree（）。层次遍历到某结点时，如果该结点的左孩子不为空，且右孩子为空，则也要输出该结点的右孩子和边，因为实际上并没有右孩子所以就用该结点加r来表示该结点的右孩子，然后隐藏右孩子结点和边;同理，如果该结点的右孩子不为空，且左孩子为空，则也要输出该结点的左孩子和边，而该结点实际并不存在的左孩子就加l来表示，然后隐藏左孩子结点和边。隐藏结点和边均用[style=invis]实现。最后注意输出顺序永远是左孩子在前，右孩子在后。代码如图15所示。

先序遍历字符序列依然是AB#D##C##，程序执行完后，在与该源程序相同路径下找到生成的tree.dot文件，文件内容如图16所示。

最后用graphviz软件打开该文件，可以看到渲染得到的二叉树图像，D结点是B结点的右孩子，满足要求。如图17所示。

为便于学生理解数据结构的算法，将算法结果可视化，输出直观的图像。以构建二叉树输出二叉树的图像为例，无须思考在命令行中输出图像的坐标位置，层次遍历输出描述二叉树的DOT文件，在Graphviz软件中查看二叉树图像结果。

参考文献：

[1] 刘中华，王琳.数据结构教学改革与探索[J].科教文汇（下旬刊），2018（7）.

[2] 元昌安，彭昱忠，覃晓，陆建波.地方高校双创型IT专业人才培养模式的研究与实践[M].北京：北京理工大学出版社，2016.

[3] 严蔚敏，李冬梅，吴伟民.数据结构（C语言）：第二版[M].北京：人民邮电出版社，2015.

[通联编辑：王力]