二进制排序树的可视化

二叉树的可视化杨晓波摘要: 在计算机科学领域，二叉树是非常重要的非线性结构，其可视化意义重大. 本文采用面向对象的方法，利用完整二叉树的特征，实现二叉树的可视化，并利用二叉树算法的计算可视化. 动态视觉遍历过程和算法的动态演示是同步的. 关键词: 二叉树；可视化面向对象;数据结构;完整的二叉树CLC编号: TP311.12文件标识码: 教育部重点科技攻关项目（No. 208137）资助的西藏文物普查和旅游开发的三维图像建模技术面向对象的描述和可视化杨晓波（西藏民族学院信息工程系，咸阳712082）摘要: 在计算机科学领域二叉排序树的实现，二叉树是非常重要的非线性结构，二叉树的可视化实现具有重要意义. 意义. 本文采用面向对象的方法和完整二叉树的功能实现了二叉树的可视化，实现了遍历二叉树算法，动态可视遍历过程和动态演示算法的可视化. 关键字: 二叉树，可视化，面向对象，数据结构，完整的二叉树简介树形结构在许多方面都有应用，可以表示层次关系，下级关系和并行关系.

在计算机科学领域，树结构是非常重要的非线性结构. 可以在各种算法问题（例如文件管理，，编译和其他系统算法）中以树状结构表示计算机应用程序中经常出现的嵌套数据. 二叉树是树结构的另一种重要类型. 以二叉树的形式简单，灵活地解决了许多算法问题，并且可以将树结构转换为与其对应的二叉树. 因此，二叉树是树结构的关键组成部分，与二叉树相关的各种算法也是数据结构过程的重点和难点. 讲授数据结构及其算法的困难在于它们的抽象性和动态性. 在学习二叉树算法时，我们遇到了困难: 首先，基于结构化编程思想的算法比较麻烦，同时由于传统的编程，数据与操作分离，所以要孤立地看问题. 为了记录每个顶点的状态，维护每个顶点之间的连接很麻烦. 使用C或Pascal描述数据结构时，抽象数据类型的想法无法很好地实现. 只有C ++或Java类才能自然地实现抽象数据类型的想法. 这是为了提高教学内容，促进软件重用和良好的设计. 软件架构奠定了坚实的基础[1]；其次，当学生去计算机验证构建二叉树的算法时，他们无法知道构建的二叉树是否与他们想要构建的树一致. 无法直观直观地显示该过程. 因此，如果我们使用面向对象的方法来描述二叉树并为学生提供一些界面，我们可以在屏幕上直观地显示学生建立的二叉树，并实现预学习的三种遍历算法的动态同步. 订单，中间订单和后订单. 这将为学生的学习提供极大的帮助，同时激发学生对学习的浓厚兴趣.

2. 二叉树的面向对象描述2.1顶点类的设计公共类BinaryTreeNode {private BinaryTreeNode left; //左侧的子私有BinaryTreeNode右侧； //正确的子私有Object数据； //此节点中的数据private int id; private int x，y;}顶点类的基本成员是left，right和data. 左边代表节点的左子树，右边代表节点的右子树，数据代表节点的数据字段. 为了以直观且易于理解的格式在屏幕上显示复杂的数据结构，应设计可视数据结构. 视觉数据结构是在顶点类的基本属性和操作的基础上添加视觉属性（例如，顶点大小，颜色，坐标值等），并为程序调用提供视觉界面[2]. 因此，为了实现二叉树的可视化，添加了三个成员id，x和y，id表示节点的完整数目，x和y表示节点的视觉坐标. 2.2二叉树的二进制链表的实现--------二进制链表的设计公共类LinkedBinaryTree //实现BinaryTree {受保护的BinaryTreeNode根；受保护的BinaryTreeNode游标；保护点p [] =新点[64]；公共LinkedBinaryTree（）{root = null; cursor = null;} public LinkedBinaryTree（String s）{//广义形式形成一个二叉树...} public LinkedBinaryTree（String s，int pred）{//建立二叉树的输入字符序列... } public void createPoint（）{//设置完整的二叉树的可见坐标...} public void drawNode（）{//绘制节点...} public void drawNode（）{//绘制边缘...} public void show（）{//视觉显示二叉树......} ......}其中根成员代表二叉树的根；游标成员代表当前节点，称为游标；方法LinkedBinaryTree（）构造一个空的二叉树？方法LinkedBinaryTree（String s）构造一个二叉树，字符串s是二叉树的广义形式，例如a（b（c，d（e，f）），i（j，k（x，y）） ）？方法LinkedBinaryTree（String s）构造一个Binary树，字符串s是二叉树的前序遍历序列，例如abc ** de * g ** f ***，其中“ *”表示子树是空的？方法drawNode（）在绘制区域中的二叉树中绘制节点？方法drawEdge（）在绘制区域中绘制二叉树的边缘吗？方法show（）直观地显示指定表单上的二叉树. 3二进制树的可视化3.1完整二进制树的可视化由于确定了屏幕的大小，因此有必要在此弹丸中绘制二进制树并不容易.

对于教学而言，足以达到教学目的，因此我们可以限制二叉树的高度，该树的高度最多可以限制为6层，因此二叉树的大小受到限制，最多63个节点，即充满了二叉树. 因此，当前的问题是可视化具有63个节点的二叉树，而可视化的关键是为63个节点设置坐标. 我们使用完整二叉树的特征来实现以下方法: 绘制区域可分为6层，用于确定完整二叉树的每一层坐标的节点数和每一层中的节点数具有高度6相同，即第一层为1层，第二层为2层，第三层为4层，第四层为8层，第五层为16层，第六层为32层. 首先确定第六层每个节点的坐标，将绘图区域的x轴分为33个部分，并获得32个坐标. 使用第六层的节点的坐标来计算第五层的节点的坐标，并计算第六层的每两个节点的水平坐标的中点坐标，即第六层为水平. 该坐标的中点坐标为第五层的第一节点的水平坐标，依此类推，可以确定每层节点的水平坐标. 每层节点的坐标是相同的. 需要说明的是，为保证视觉效果，每一层的纵坐标应保持一定距离. 等等. 此过程由createPoint（）方法实现.

接下来是绘制节点和边的问题，由方法drawNode（）和drawEdge（）实现. 完整的二叉树的可视化如图1所示. 图1完整的二叉树的可视化结果3.2不完整的二叉树的可视化对于不完整的二叉树，由于形式不同，为了实现简单并适用于各种形式的二叉树，使用不完全二叉树的思想来完成，以实现将一个完整编号的成员添加到节点类中，使每个节点的坐标采用完整二叉树中相应节点的坐标，并进行可视化不完全的二叉树很容易实现. 图2显示了不完整的二叉树的可视化效果. 图2不完整的二叉树的可视化结果3.3窗口刷新问题另外，如果在绘制过程中直接在窗口中绘制，则在刷新窗口时（例如窗口最小化并恢复正常），或者窗口被覆盖，图形形状将被删除. 为避免这种情况，您可以在绘图区域中加载背景图片并在图片上进行绘制，以使形状不会被擦除. 3.4二叉树可视化的应用3.4.1建立二叉树的广义表形式在文本框中输入二叉树的广义表形式，例如a（b（c，d（e，f）），i（j，k（ x，y）））），调用LinkedBinaryTree（String s）方法来构建二叉树，然后调用show方法以可视方式显示二叉树.

构建的二进制树如图3所示. 图3生成二进制树的通用表形式3.4.2建立二进制树的预输入字符序列在文本框中（例如， abc ** de * g ** f ***，其中“ *”表示子树为空），调用LinkedBinaryTree（字符串s，int pred）方法来构建二叉树，然后调用show方法以可视方式显示二叉树. 构建的二叉树如图3所示. 图4按顺序输入字符序列以建立二叉树3.4.3动态视觉遍历过程和动态演示算法来实现同步实现我们使用shape-设计时基于的. 基于形状的也称为“精灵”，这是一种更强大的技术. 在基于形状的中，每个图形对象都成为一个子图片. 并且它可以随着时间改变位置[3]. 以中间顺序遍历为例，以上窗口是遍历过程中的动态演示. 椭圆，线条，文本，填充颜色和其他方式用于描绘顶点. 例如，将当前访问的节点绘制为粗红线，以反映遍历的动态过程. 左下方的窗口是算法执行的动态演示，字符的反位置用来反映算法的执行位置；上下窗口的演示是通过动态同步可视化进行的. 中序遍历的实现比前序遍历的实现更为复杂. 中阶遍历左侧子树，访问根节点，然后中阶遍历右侧子树. 因此，需要设置四个定时器timer1，timer2，timer3和timer4.

遍历还应该反映遍历过程中遍历的路径，因此可以捕获并显示中阶遍历的递归算法中堆栈的变化. 从堆栈的更改顺序可以看出，节点值的第一次出现表明该节点在堆栈上，该节点未被访问，而第二次出现表明该节点不在堆栈中，即，该节点被访问. Timer1控制算法的动态演示，timer2用于控制中阶遍历的动态视觉遍历过程. 由于中间顺序遍历的特性，算法中访问节点访问（b.data）的图像显示由计时器5控制，计时器4用于控制堆栈更改顺序的显示. 当节点进入堆栈时，它将启动timer3，而当节点退出堆栈时，它将启动timer3. Timer3在算法中显示访问节点访问的图片（b.data），然后启动Timer2绘制访问节点，从而实现两者的同步. 通过循环图片实现算法的动态演示，左右子树的图片不同. 中阶遍历的动态视觉遍历过程是用粗红线重绘所访问的节点，同时遍历中阶的序列文本框. 显示所访问节点的值. 文本更改在中级遍历序列文本框中，文本在堆栈更改序列文本框中发生更改，中级遍历的动态视觉遍历过程以及算法的动态演示都同步进行. 图5中顺序遍历的动态可视化演示过程4实现二叉树可视化的意义. 一方面，解决了在视觉上显示二叉树的问题，并且将所构建的二叉树直观地直观地显示在用户面前，解决了入门上的“听不见好”的难题. 或学习抽象概念并训练抽象思维都需要自然和直观的方法.

无论对“鱼”的描述多么生动，最好亲自看到鱼的动态图像，而后者可以给人留下深刻的印象. 另一方面，旅行旅行的二叉树算法的可视化的实现显示了动态旅行的过程. 讲授数据结构及其算法的困难在于它们的抽象性和动态性. 在课堂教学中可以在一定程度上使用插图. 抽象是直观的，但是很难显示对象的瞬时动态特性和算法的动态执行过程，我们通过对二进制进行可视化来做到这一点. 树. 在第三方面，数据结构中存在各种二进制树，例如二进制排序树，平衡二进制树，霍夫曼树，堆，二进制决策树等. 二进制树的可视化提供了这些特殊二进制树的可视化可能. 参考文献: 1.尹仁坤，邓俊辉. 清华大学“数据结构”精品课程建设二叉排序树的实现，计算机教育，2006，5 2.苏颖，吴为民，数据结构可视化类库的设计与实现，计算机技术与发展，2006. 3.迈克尔·莫里森. 徐刚，于坚，薛蕾，翻译. 游戏编程概论[M]. 北京: 人民邮电出版社，2005: 131-135. 作者简介: 杨晓波（1970.8），女，汉族，甘肃省景泰市人，计算机应用技术硕士，副教授，研究方向: 计算机教学与数据结构与算法研究. 电子邮件: hzyangxb@126.com.

传记: 杨晓波，女，汉族，1970年8月生于甘肃省景泰市. 计算机应用技术硕士，副教授，计算机教学以及数据结构和算法研究. 通讯地址: （陕西咸阳西藏民族学院信息工程学院712082）电话: 13689186609电子邮件: hzyangxb@126.com杨晓波

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-185017-1.html