1引言数据结构课程是计算机及相关专业的核心课程，是程序设计的重要理论技术基础[1].在动态查表中，平衡二叉树被广泛的应用，平衡二叉树又称AVL 树，它是由Adel ，son-Vel ，skii 和Landis 两位数学家于1962年提出并用他们的名字来命名的.平衡二叉树或者是一棵空树，或者是满足下列条件的二叉排序树：二叉排序树的所有结点的平衡因子为-1、0和1.所谓平衡因子BF （Balance
Factor ）可定
义为某结点左子树的深度减去右子树的深度[2]
.若
二叉树中任一个结点的平衡因子的绝对值大于1，
则该二叉树就不是平衡二叉树.
平衡二叉树在插入结点和删除结点时候，会使其变得不平衡.为此，需要对二叉排序树进行调整，使之重新变为平衡二叉树.相关教材和论文中关于平衡二叉树的调整方法较难理解，学生难以接受.笔者通过阅读大量的相关资料，并且总结教学经验，提出了一种易于理解和实用的二叉排序树转换成平衡二叉树方法.2
平衡二叉树调整方法的文献综述
由于平衡二叉树的重要性，以及学生在学习平衡二叉树调整的过程中，普遍反映对用于平衡二叉树调整的四种方法较难理解，算法复杂.为此，许多学者对平衡二叉树的调整进行了大量的研究.
严蔚敏、吴伟民[1]在《数据结构》（C 语言版）一书中二叉排序树调整为平衡二叉树采用左旋转
（LL ）、右旋转（LR ）、先左旋转后右旋转（LR ）、先右旋转后左旋转（RL ）四种旋转方法.
李春葆[2]在《数据结构教程》（第2版）一书中也是采用了LL 、
LR 、RR 、RL 四种旋转方法.朱宇、张红彬[3]在《平衡二叉树的选择调整算法》一文中，提出利用“中为根、小为左、大为右”的调整策略，但本质上仍然是利用旋转的思想.
胡云[4]在《快速构建AVL 树》一文中采用“将二叉排序树中的数据进行排序，将中点数据作为根，大于中点的数据构成右子树，小于中点的数据构成左子树，然后采用同样的方法分别对左子树和右子树进行调整.”
但从作者举出的实例可以看出，该方法与传统方法得到的平衡二叉树并不一致.
杜薇薇[5]等在《基于平衡因子的AVL 树设计实现》
一文中则从平衡因子出发，并用数学公式进行了验证了插入和删除操作.
刘绍翰[6]等在《一种简化的AVL 树的实现方法》一文提出了高度平衡树(HAVL)它是一种新的AVL 树的数学描述.
以上文献中虽然提出了较好的调整方法，但在平衡二叉树的调整基本上仍然是采用旋转的方法进行调整，并没有从根本上解决学生的困惑.笔者在教学中发现学生对二叉排序树的建立普遍能熟练掌握，并且平衡二叉树的前提必须是一棵二叉排序树，为此，本文提出了一种利用平衡因子和构建二叉排序树的方法来实现平衡二叉树的调整，从而
Vol.28No.3
M ar.2012
赤峰学院学报（自然科学版）Journal of Chifeng University （Natural Science Edition ）数据结构中平衡二叉树的教学探讨与研究
朱洪浩
（蚌埠学院计算机科学与技术系，安徽蚌埠233000）
摘要：平衡二叉树是对二叉排序树的一种改进，又被称为AVL 树，平衡二叉树的结构较好，可以提高查运算的速度.本文分析了权威教材和相关论文中平衡二叉树的调整方法，
这些方法学生普遍反映理解和掌握较困难.据此，本文依据平衡因子和二叉排序树的特性，设计出一种基于平衡因子和二叉排序树的平衡二叉树的调整方法，该方法易于理解和掌握.
关键词：二叉排序树；平衡因子；平衡二叉树中图分类号：TP311.12
二叉树公式
文献标识码：A
文章编号：1673-260X （2012）03-0019-03
第28卷第3期（上）
2012年3月基金项目：安徽省自然科学基金项目（11040606M151）资助
19--

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。