郭秋 马云吉 张媛媛 张秀梅 宫玺
辽宁科技大学）
1 前言
程序设计可视化工具通过对程序逻辑和代码结构进行可视化，使编程初学者直观地了解当前程序地运行状态，快速排查程序的逻辑错误，提高学习效率。
其中，数据结构可视化是程序设计可视化的一个重要组成部分。数据结构可视化指的是通过可视化技术展现一个数据结构内部各个节点之间、以及各个数据结构之间的逻辑关系。而二叉树这种数据结构又是编程学习中的一种极其重要的非线性结构，因此二叉树结构可视化是数据结构可视化的重要内容之一，其对于初学者理解和应用二叉树结构具有重要意义。二叉树结构由两部分组成：组成树的节点集合以及节点之间的逻辑关系。节点之间的逻辑关系通常由节点中的左右孩子指针域来表示。
一般的数据结构可视化技术可分为静态可视化和动态可视化两种。静态可视化侧重展示，可对某个时刻的二叉树结构的状态进行完整的绘制和呈现。
将两个二叉树结构可视化视图间的平滑过渡称为二叉树结构的演变过程。动态可视化方法为解决演变过程可视化提供了可能性，例如使用某种动画计算算法去呈现数据结构演变前和后造成的差异，使得两个可视化视图间可以平滑地衔接，改善用户对可视化图形之间变化的图形感知，有助于增进用户对程序调试过程的理解和参与度。
在数据结构可视化领域中，动态可视化的演变过程技术对于增进程序调试的理解程度和效率方面尤为明显。当用户进行程序调试时，如果用户想要知道执行当前代码行对整体数据结构的影响，则可以直观地观察在执行该行代码前和后程序中的数据结构可视化视图的变化。更为重要的是，动态可视化方法可以展现可视化视图中每一个节点或者指针的具体变化过程，包括创建、销毁、位置变化或者样式更改。通过观察这些变化过程，配合适当的交互机制，用户可以清楚地体会到数据结构是如何变化与运作的，更能深刻地掌握程序调试过程，提升程序调试效率。
现有方法中尚未发现较为完善的适用于编程教育领域中面向程序调试的二叉树数据结构针对其演变过程的动态可视化方案。
2 项目设计基本内容
本项目提供了面向学生的数据结构实验可视化方法，方法包括：
获取在程序调试中单步执行前和后的两组二叉树结构数据；对两组二叉树结构数据进行二叉树结构逻辑对比，获取两组二叉树结构数据的结构差异信息；对两组二叉树结构数据进行结构布局对比，获取两组二叉树结构数据的布局差异信息；将结构差异信息与布局差异信息转化成可视化演变操作序列；将可视化演变操作序列中的每一个可视化演变操作解析成为特定的动画对象，动画对象依次执行播放。
在在程序调试中单步执行前和后的两组二叉树结构数据，之后还包括：
二叉树结构数据进行数据清洗和数据转换，得到新生成的二叉树结构数据T0和T1。
对两组二叉树结构数据进行二叉树结构逻辑对比，获取两组二叉树结构数据的结构差异信息，具体为：将单步执行前和后的两组二叉树结构数据转换成线性结构进行存储，记为分别记为L0和L1；将存在于L1但不存在于L0的节点称为新增节点，将新增节点加入到L0，得到L2；将存在于L2但不存在于L1的节点称为被移除节点，将被移除节点从L2中移除，得到L3；将L1和L3中相同的节点进行节点间的比较，获取相同节点的差异信息，差异信息包括节点内指针域变化的信息、节点内数据域变化的信息、节点的外部指针域变化的信息以及泄露树节点的信息；结构差异信息包括新增节点信息、移除节点信息、节点内指针域变化的信息、节点内数据域变化的信息、节点的外部指针域变化的信息以及泄露树节点的信息。
泄露树节点的检查方法为：
若单步执行前二叉树中节点q的左孩子节点为节点p，经过单步执行后的q的左孩子节点变成了空；T(p)是以p为根的子树；则当p是外部指针节点时，T(p)是一棵独立的树，此时没有产生泄露树；当p是汇点时，从当前的从父节点中选取p的主父节点，此时没有产生泄露树；当p是普通节点时，则从T(p)的子孙节点中查找是否存在外部指针节点或者汇点，若存在，则将以外部指针节点或者汇点为根的子树从T(p)中剔除，T(p)中剩余的部分为泄漏树。
对两组二叉树结构数据进行结构布局对比，获取两组二叉树结构数据的布局差异信息，具体为：
对单步执行后的二叉树结构数据进行二叉树布局，即分别二叉树结构数据进行的树内节点间布局以及树间布局；将二叉树布局后的两组二叉树结构数据中相同节点的坐标进行对比，记录相同节点的坐标差异信息。
二叉树结构数据进行的树内节点间布局以及树间布局，具体为：
二叉树结构数据中的每一棵树，从每一棵树的根节点开始，按各节点所在的层次，逐层进行节点间布局，节点间布局包括先由上至下进行向下排布，然后由下至上进行回推调整以消除节点位置重叠和保持对称性；二叉树结构数据进行树间布局包括：二叉树结构数据进行树布局单元划分，若存在符合二叉树定义的普通树结构，则普通树结构单独成为一个树布局单元；若存在相连树结构，则将相连树结构结合成一个树布局单元；从左到右保持预设的间距对所有树布局单元进行水平排布。
图1 二叉树实验数据结构的可视化方法流程图
3拟解决的关键问题和创新点
提供了面向学生的数据结构实验可视化方法，包括：获取在程序调试中单步执行前和后的两组二叉树结构数据；对两组二叉树结构数据进行二叉树结构逻辑对比，获取两组二叉树结构数据的结构差异信息；对两组二叉树结构数据进行结构布局对比，获取两组二叉树结构数据的布局差异信息；将结构差异信息与布局差异信息转化成可视化演变操作序列；将可视化演变操作序列中的每一个可视化演变操作解析成为特定的动画对象，对动画对象依次执行播放。
通过将单步执行前和后的两组二叉树结构数据进行对比，分别获取结构差异信息与布局差异信息，再将结构差异信息与布局差异信息转化成可视化演变操作序列，通过将可视化演变操作解析成为特定的动画对象，对动画对象依次执行播放，使得解决了在编程教育领域的程序调试过程中，由于二叉树结构的演变过程复杂和抽象，导致程序设计学习人员难以掌控二叉树结构演变过程的技术问题，同时弥补了应用静态可视化技术对二叉树结构进行可视化呈现时，会产生突变的缺陷。
4结束
本项目实施例提供了面向学生的数据结构实验可视化方法，解决了在编程教育领域的程序调试过程中，由于二叉树结构的演变过程复杂和抽象，导致程序设计学习人员难以掌控二叉树结构演变过程的技术问题。
参考文献：
[1] “赋能教育”的混合教学模式设计与实践——以数据结构与算法课程为例[J]. 王曙燕,郑佳妮,王燕,王春梅. 计算机教育. 2020(04)
[2]基于问题导向的数据结构混合式教学模式研究与实践[J]. 张平,刘福东. 计算机教育. 2020(04)
[3]基于分层教学的带动导向式“数据结构”实验课研究[J]. 崔妍,祝世东,曹福毅,姜柳,代钦. 沈阳工程学院学报(社会科学版). 2020(01)
[4]工程教育专业认证背景下数据结构课程改革探索与分析[J]. 李照奎,吴杰宏,王岩,赵亮,范纯龙,刘芳. 计算机教育. 2019(08)
2021年辽宁科技大学实验教学改革项目立项编号SYJG202108