基于C#的二叉排序树图形显示系统研究与实现

摘　要：本文首先介绍了二叉树在数据结构中的应用，并结合C#语言实现了二叉树的可视化功能。文章对二叉树的构建和输出实现进行了说明，同时对数据结构的教学方法进行了讨论。

关键词：二叉树；图形显示；遍历
　　1、背景介绍
　　二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树的形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。
　　二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree)。其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树：
　　①若它的左子树非空，则左子树上所有结点的值均小于根结点的值；
　　②若它的右子树非空，则右子树上所有结点的值均大于根结点的值；
　　③左、右子树本身又各是一棵二叉排序树。
　　上述性质简称二叉排序树性质(BST性质)，故二叉排序树实际上是满足BST性质的二叉树。
　　二叉排序树在实际应用中，经常用来实现提高数据的查寻效率，但由于概念理解上的困难，在教学过程中，学生往往不能掌握二叉树的基本操作，不能在脑海中形成对应的模型。所以本文试图从概念入手，用可视化的方法来对数据结构中二叉树的教学进行改进。
　　2、实现工具
　　C#是一种先进的面向对象的程序开发语言，通过C#可以让开发人员快速的建立大范围的基于MS网络平台的应用，并且提供大量的开发工具和服务帮助开发人员开发基于计算和通信的各种应用。基于这个特点，我们采用C#来开发二叉排序树图形显示系统。
　　3、具体设计
　　界面设计，除了基本的二叉排序树显示功能以外，还可对二叉排序树中的节点进行增加和删除。
　　4、实现
　　实现二叉树的显示，主要要进行这样几个操作，首先是初始化二叉树，对初始的输入序列依次进行增加节点操作，在增加节点时先要找到节点要插入的位置，然后在窗口上显示出这个结点，直到所有输入序列都插入到二叉树中为止，这些操作都是递归进行的。
　　4.1插入位置查找 
　　 private bool Search(TreeNode node, int data)
　　        {
　　            if ( == data)
　　            {
　　                found = true;
　　            }
　　            else
　　            {
　　                if ( > data)  ///条件成立则查左子树，否则查右子树。
　　                {
　　                    if (de != null)
　　                    {
　　                        Search(de, data);
　　                    }
　　                }
　　                else
　　                {
　　                    if (ode != null)
　　                    {
　　                        Search(ode, data);
　　                    }
　　                }
　　            }
　　            return found;
　　        }
　　4.2插入操作
　　    private void Insert(TreeNode node, int data)
　　        {
　　            if ( > data)
　　            {
　　                if (de == null)
　　                {
　　                    TreeNode temp = new TreeNode();
　　                    = data;
　　                    de = temp;
　　                }
　　                else
　　                {
　　                    Insert(de, data);
　　                }
　　            }
　　            else
　　            {
　　                if (ode == null)
　　                {
　　                    TreeNode temp = new TreeNode();
　　                    = data;
　　                    ode = temp;
　　                }
　　                else
　　                {
　　                    Insert(ode, data);
　　                }
　　            }
　　        }
　　4.3显示模块
　　private void Draw(TreeNode parent, Point cur, Point last, int deep)
　　        {
　　            if (parent == null)
　　            {
　　                return;
　　            }
　　            /* 画圆圈*/
　　            Size size = new Size(nodeRadius*2, nodeRadius*2);
　　            Point center = new Point();
　　            center.X = cur.X - nodeRadius;
　　            center.Y = cur.Y - nodeRadius;
　　            Rectangle rec = new Rectangle(center, size);
　　            lipse(cirBrush, rec);
　　            /* 画线*/
　　            ne(myPen, cur, last);
　　            /* 绘制左右子树*/
　　            Point left = new Point();
　　            int len = (int)(2.0, (double)deep);
　　            left.X = cur.X - (nodeRadius + distanceWidth) * len;
　　            left.Y = cur.Y + distanceHeight;
　　            Draw(de, left, cur, deep-1);
　　            Point right = new Point();
　　            right.X = cur.X + (nodeRadius + distanceWidth) * len;
　　            right.Y = cur.Y + distanceHeight;
　　            Draw(ode, right, cur, deep-1);
　　            /* 写字*/
　　            center.X = cur.X - nodeRadius * 9 / 10;
　　            center.Y = cur.Y - nodeRadius * 9 / 10;
　　            ring(ng(), myFont, fontBrush, center);
　　        }
　　5、结论
　　通过使用二叉排序树图形显示系统，在教学中能够使学生对二叉排序树的概念和基本操作有良好的认识，对掌握二叉树这一数据结构中的重要概念有很好的帮助作用。当然这个系统还有很多需要完善的地方，比如平衡的二叉排序树的显示实现，还有遍历的过程显示等，将在今后进行不断的完善。　　
参考文献
　　[1] 顺序存储的满二叉树中序遍历的非递归算法 吴福英 谭罗生 王明文  江西师范大学学报(自然科学版)2003, 27(4)
　　[2] 基于满二叉树的原地快速排序 范时平 重庆邮电学院学报（自然科学版）2006, 18(6)
　　[3] 二叉树的绘制算法 周志华 计算机应用研究 1997，4
　　[4] 浅谈《数据结构》课程教改 储美芳  成才之路 2010年第29期