平衡二叉树-构造方法(绝妙)

解题思路多代入法二叉树度叶子结点就是没有孩子的结点，其度为0，度为二的结点是指有两个子数的结点。

注意树的度和图的度区别叶子结点二叉排序树完全二叉树若设二叉树的深度为h，除第h 层外，其它各层(1～h-1) 的结点数都达到最大个数，第h 层所有的结点都连续集中在最左边，这就是完全二叉树。

完全二叉树——只有最下面的两层结点度小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树；最优二叉树（就是哈弗曼树）平衡二叉树平衡二叉树，又称AVL树。

它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度之差之差的绝对值不超过1.。

满二叉树满二叉树——除了叶结点外每一个结点都有左右子叶且叶结点都处在最底层的二叉树,。

除最后一层无任何子节点外，每一层上的所有结点都有两个子结点（最后一层上的无子结点的结点为叶子结点）。

也可以这样理解，除叶子结点外的所有结点均有两个子结点。

节点数达到最大值。

所有叶子结点必须在同一层上.本题主要考查一些特殊二叉树的性质。

若二叉树中最多只有最下面两层的结点度数可以小于2，并且最下面一层的叶子结点都依次排列在该层最左边的位置上，则这样的二叉树称为完全二叉树，因此在完全二叉树中，任意一个结点的左、右子树的高度之差的绝对值不超过1。

二叉排序树的递归定义如下：二叉排序树或者是一棵空树；或者是具有下列性质的二叉树：(1)若左子树不空，则左子树上所有结点的值均小于根结点的值；(2)若右子树不空，则右子树上所有结点的值均大于根结点的值；(3)左右子树也都是二叉排序树。

在n个结点的二叉树链式存储中存在n+1个空指针，造成了巨大的空间浪费，为了充分利用存储资源，可以将这些空链域存放指向结点在遍历过程中的直接前驱或直接后继的指针，这种空链域就称为线索，含有线索的二叉树就是线索二叉树。

最优二叉树即哈夫曼树。

排序各种排序的大致思路？各种排序适用于什么情况？各种排序的时间，空间复杂度？快速排序1.快速排序（Quicksort）是对冒泡排序法的一种改进，它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列；在对一个基本有序的数组进行排序时适合采用快速排序法。

数据结构之⼆叉树（BinaryTree）⽬录导读 ⼆叉树是⼀种很常见的数据结构，但要注意的是，⼆叉树并不是树的特殊情况，⼆叉树与树是两种不⼀样的数据结构。

⽬录 ⼀、⼆叉树的定义 ⼆、⼆叉树为何不是特殊的树 三、⼆叉树的五种基本形态 四、⼆叉树相关术语 五、⼆叉树的主要性质（6个） 六、⼆叉树的存储结构（2种） 七、⼆叉树的遍历算法（4种） ⼋、⼆叉树的基本应⽤：⼆叉排序树、平衡⼆叉树、赫夫曼树及赫夫曼编码⼀、⼆叉树的定义 如果你知道树的定义（有限个结点组成的具有层次关系的集合），那么就很好理解⼆叉树了。

定义：⼆叉树是n(n≥0)个结点的有限集，⼆叉树是每个结点最多有两个⼦树的树结构，它由⼀个根结点及左⼦树和右⼦树组成。

（这⾥的左⼦树和右⼦树也是⼆叉树）。

值得注意的是，⼆叉树和“度⾄多为2的有序树”⼏乎⼀样，但，⼆叉树不是树的特殊情形。

具体分析如下⼆、⼆叉树为何不是特殊的树 1、⼆叉树与⽆序树不同 ⼆叉树的⼦树有左右之分，不能颠倒。

⽆序树的⼦树⽆左右之分。

2、⼆叉树与有序树也不同（关键） 当有序树有两个⼦树时，确实可以看做⼀颗⼆叉树，但当只有⼀个⼦树时，就没有了左右之分，如图所⽰：三、⼆叉树的五种基本状态四、⼆叉树相关术语是满⼆叉树；⽽国际定义为，不存在度为1的结点，即结点的度要么为2要么为0，这样的⼆叉树就称为满⼆叉树。

这两种概念完全不同，既然在国内，我们就默认第⼀种定义就好）。

完全⼆叉树：如果将⼀颗深度为K的⼆叉树按从上到下、从左到右的顺序进⾏编号，如果各结点的编号与深度为K的满⼆叉树相同位置的编号完全对应，那么这就是⼀颗完全⼆叉树。

如图所⽰：五、⼆叉树的主要性质 ⼆叉树的性质是基于它的结构⽽得来的，这些性质不必死记，使⽤到再查询或者⾃⼰根据⼆叉树结构进⾏推理即可。

性质1：⾮空⼆叉树的叶⼦结点数等于双分⽀结点数加1。

证明：设⼆叉树的叶⼦结点数为X，单分⽀结点数为Y，双分⽀结点数为Z。

树的种类和构造树是一种重要的数据结构，它具有分层结构和层次性的特点。

在计算机科学中，树的种类和构造非常丰富多样。

本文将介绍一些常见的树的种类和它们的构造方式，以及它们在实际应用中的一些应用场景。

一、二叉树二叉树是最简单、也是最常见的一种树结构，它由一个根节点以及每个节点最多有两个子节点组成。

二叉树的构造方式有多种，包括满二叉树、完全二叉树、平衡二叉树等。

其中，满二叉树是一种特殊的二叉树，每个节点要么没有子节点，要么有两个子节点；完全二叉树是一种二叉树，除了最后一层的叶子节点外，其他层的节点都是满的；平衡二叉树是一种二叉树，它的左子树和右子树的高度差不超过1。

二叉树的应用非常广泛，例如在搜索算法中，二叉搜索树可以快速地定位某个节点；在编译原理中，语法分析树可以用于解析和分析代码的结构；在图像处理中，霍夫曼树可以用于对图像进行压缩等。

二、多叉树多叉树是一种每个节点最多有多个子节点的树结构。

它的构造方式和二叉树不同，可以有任意多个子节点。

多叉树的应用也非常广泛，例如在文件系统中，目录和文件的关系可以用多叉树来表示；在组织架构中，公司的部门和员工的关系也可以用多叉树来表示。

三、红黑树红黑树是一种自平衡的二叉查找树，它在插入和删除节点时会自动调整树的结构，保持树的平衡性。

红黑树的构造方式非常复杂，但它的性能非常优秀，能够在最坏情况下保持对数时间的复杂度。

红黑树的应用非常广泛，例如在C++的STL中，红黑树被用于实现set 和map等容器。

四、B树B树是一种自平衡的多路查找树，它的每个节点可以存储多个键值对。

B树的构造方式和红黑树类似，但它的每个节点可以有多个子节点。

B树的应用非常广泛，特别适合在磁盘等外存储设备上进行查找和插入操作，因为它可以最大限度地减少磁盘的I/O操作次数。

五、Trie树Trie树，也称为字典树或前缀树，是一种用于快速检索字符串的树结构。

它的每个节点包含一个字符，根节点表示空字符。

Trie树的构造方式非常简单，每个字符对应一个子节点。

二叉树结构的特点二叉树是一种常见的数据结构，它具有以下特点：1. 结构简单：二叉树是一种有序树结构，每个节点最多只有两个子节点，分别称为左子节点和右子节点。

这种结构的简洁性使得二叉树在实际应用中得到广泛使用。

2. 层次性：二叉树具有明显的层次性，即树的每一层都可以通过节点间的父子关系来确定。

根节点是第一层，根节点的子节点是第二层，以此类推。

3. 有序性：在二叉树中，每个节点的左子节点小于它，右子节点大于它。

这种有序性使得二叉树在查找和排序方面具有很高的效率。

4. 高度平衡：二叉树的高度平衡性是指树的左右子树的高度差不超过1。

高度平衡的二叉树可以保证查找、插入和删除操作的平均时间复杂度为O(log n)。

5. 递归性：二叉树的定义是递归的，即每个子树都是二叉树。

这种递归性质使得在二叉树上的操作可以通过递归算法来实现。

6. 存储结构灵活：二叉树的存储结构可以采用顺序存储和链式存储两种方式。

顺序存储是将二叉树的节点按照层次顺序存储在一维数组中，链式存储是通过每个节点的指针来连接各个节点。

在二叉树的基础上，还可以扩展出以下几种特殊的二叉树结构：1. 完全二叉树：完全二叉树是指除了最后一层外，其他层的节点个数都达到最大值，并且最后一层的节点依次从左到右排列。

完全二叉树的特点是高度平衡，可以用数组来存储。

2. 满二叉树：满二叉树是指每个节点都有两个子节点的二叉树，即除了叶子节点外，每个节点都有两个子节点。

满二叉树的特点是节点个数达到最大值，高度平衡。

3. 平衡二叉树：平衡二叉树是指任意节点的左右子树的高度差不超过1的二叉树。

平衡二叉树的特点是高度平衡，可以保证各种操作的时间复杂度较低。

4. 二叉搜索树：二叉搜索树是一种特殊的二叉树，它具有以下性质：对于树中的任意节点，其左子树中的节点值都小于它，右子树中的节点值都大于它。

二叉搜索树的特点是可以高效地进行查找、插入和删除操作。

5. 线索二叉树：线索二叉树是对二叉树的一种扩展，它的特点是在每个节点上增加了指向前驱节点和后继节点的指针。

二叉树知识点总结二叉树是一种常见的数据结构，它由节点和边组成，每个节点最多有两个子节点。

以下是关于二叉树的知识点总结。

1. 二叉树的基本概念二叉树是一种树形结构，它由节点和边组成。

每个节点最多有两个子节点，分别称为左子节点和右子节点。

如果一个节点没有子节点，则称其为叶子节点。

二叉树可以为空。

2. 二叉树的遍历方式遍历是指按照一定顺序访问二叉树中的所有节点。

常见的遍历方式有前序遍历、中序遍历和后序遍历。

前序遍历：先访问当前节点，然后递归访问左子树和右子树。

中序遍历：先递归访问左子树，然后访问当前节点，最后递归访问右子树。

后序遍历：先递归访问左子树和右子树，最后访问当前节点。

3. 二叉搜索树二叉搜索树（Binary Search Tree）也称为有序二叉树或排序二叉树。

它是一种特殊的二叉树，在满足以下条件的情况下被称为“搜索”：对于任意节点，其左子树中的所有节点的值都小于该节点的值。

对于任意节点，其右子树中的所有节点的值都大于该节点的值。

左右子树也分别为二叉搜索树。

二叉搜索树支持快速查找、插入和删除操作。

它还有一些变种，如平衡二叉搜索树（AVL Tree）和红黑树（Red-Black Tree）等。

4. 二叉堆二叉堆是一种特殊的完全二叉树，它分为最大堆和最小堆两种类型。

最大堆满足父节点的值大于等于其子节点的值，最小堆满足父节点的值小于等于其子节点的值。

在最大堆中，根节点是整个堆中最大的元素；在最小堆中，根节点是整个堆中最小的元素。

二叉堆常用来实现优先队列（Priority Queue），即按照一定优先级顺序处理元素。

5. 二叉树常见问题5.1 判断是否为平衡二叉树平衡二叉树（Balanced Binary Tree）是指任意节点左右子树高度差不超过1的二叉搜索树。

判断一个二叉搜索树是否为平衡二叉树可以通过递归遍历每个节点，计算其左右子树的高度差。

5.2 判断是否为完全二叉树完全二叉树（Complete Binary Tree）是指除了最后一层外，其他层都是满的，并且最后一层的节点都靠左排列的二叉树。

【数据结构】⼆叉树【⼆叉树】 ⼆叉树是最为简单的⼀种树形结构。

所谓树形结构，其特征（部分名词的定义就不明确给出了，毕竟不是学术⽂章。

）在于： 1. 如果是⾮空的树形结构，那么拥有⼀个唯⼀的起始节点称之为root（根节点） 2. 除了根节点外，其他节点都有且仅有⼀个“⽗节点”；除此外这些节点还都可以有0到若⼲个“⼦节点” 3. 树中的所有节点都必须可以通过根节点经过若⼲次后继操作到达 4. 节点之间不会形成循环关系，即任意⼀个节点都不可能从⾃⾝出发，经过不重复的径路再回到⾃⾝。

说明了树形结构内部蕴含着⼀种“序”，但是不是线性表那样的“全序” 5. 从树中的任意两个节点出发获取到的两个任意⼦树，要不两者⽆交集，要不其中⼀者是另⼀者的⼦集 限定到⼆叉树，⼆叉树就是任意⼀个节点⾄多只能有两个⼦节点的树形结构。

也就是说，某个节点的⼦节点数可以是0,1或2。

由于可以有两个⼦节点，所以区别两个⼦节点可以将其分别定义为左⼦节点和右⼦节点。

但是需要注意的是，若⼀个节点只有⼀个⼦节点，那么也必须明确这个⼦节点是左⼦节点还是右⼦节点。

不存在“中⼦节点”或者“单⼦节点”这种表述。

由于上述规则对所有节点都⽣效，所以⼆叉树也是⼀个递归的结构。

事实上，递归就是⼆叉树⼀个⾮常重要的特点，后⾯还会提到很多通过递归的思想来建⽴的例⼦。

对于左⼦节点作为根节点的那颗⼆叉树被称为相对本节点的左⼦树，右⼦树是同理。

■ 基本概念 空树 不包含任何节点的⼆叉树，连根节点也没有 单点树 只包含⼀个根节点的⼆叉树是单点树 ⾄于兄弟关系，⽗⼦关系，长辈后辈关系是⼀⾔既明的就不说了。

树中没有⼦节点的节点被称为树叶（节点），其余的则是分⽀节点。

⼀个节点的⼦节点个数被称为“度数”。

正如上所说，⼆叉树任意节点的度数取值可能是0，1或2。

节点与节点之间存在关联关系，这种关联关系的基本长度是1。

通过⼀个节点经过若⼲个关联关系到达另⼀个节点，经过的这些关联关系合起来被称为⼀个路径。

基本概念结点的层次（Level）从根开始定义，根为第一层，根的孩子为第二层。

二叉树的高度：树中结点的最大层次称为树的深度（Depth）或高度。

二叉树在计算机科学中，二叉树是每个结点最多有两个子树的有序树。

通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）。

二叉树常被用作二叉查找树和二叉堆。

二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。

二叉树的第i层至多有2的（i-1）次方个结点；深度为k的二叉树至多有2的k次− 1个结点；对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0 = n2 + 1。

树和二叉树的2个主要差别：1. 树中结点的最大度数没有限制，而二叉树结点的最大度数为2；2. 树的结点无左、右之分，而二叉树的结点有左、右之分。

……树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的结构，很象自然界中的树那样。

树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树形象表示。

树在计算机领域中也得到广泛应用，如在编译源程序如下时，可用树表示源源程序如下的语法结构。

又如在数据库系统中，树型结构也是信息的重要组织形式之一。

一切具有层次关系的问题都可用树来描述。

一、树的概述树结构的特点是：它的每一个结点都可以有不止一个直接后继，除根结点外的所有结点都有且只有一个直接前趋。

以下具体地给出树的定义及树的数据结构表示。

（一）树的定义树是由一个或多个结点组成的有限集合，其中：⒈必有一个特定的称为根(ROOT)的结点；⒉剩下的结点被分成ｎ>=0个互不相交的集合T1、T2、......Tn，而且，这些集合的每一个又都是树。

树T1、T2、......Tn被称作根的子树(Subtree)。

树的递归定义如下：（1）至少有一个结点（称为根）（2）其它是互不相交的子树1.树的度——也即是宽度，简单地说，就是结点的分支数。

第八节最优二叉树(哈夫曼树)一、概念在具有n个带权叶结点的二叉树中，使所有叶结点的带权路径长度之和（即二叉树的带权路径长度）为最小的二叉树，称为最优二叉树（又称最优搜索树或哈夫曼树），即最优二叉树使（W k—第k个叶结点的权值；P k—第k个叶结点的带权路径长度）达到最小。

二、最优二叉树的构造方法假定给出n个结点ki(i=1‥n)，其权值分别为Wi(i=1‥n)。

要构造以此n个结点为叶结点的最优二叉树，其构造方法如下：首先，将给定的n个结点构成n棵二叉树的集合F={T1，T2，……，Tn}。

其中每棵二叉树Ti中只有一个权值为wi的根结点ki，其左、右子树均为空。

然后做以下两步⑴在F中选取根结点权值最小的两棵二叉树作为左右子树，构造一棵新的二叉树，并且置新的二叉树的根结点的权值为其左、右子树根结点的权值之和；⑵在F中删除这两棵二叉树，同时将新得到的二叉树加入F 重复⑴、⑵，直到在F中只含有一棵二叉树为止。

这棵二叉树便是最优二叉树。

三、最优二叉树的数据类型定义在最优二叉树中非叶结点的度均为2，为满二叉树，因此采用顺序存储结构为宜。

如果带权叶结点数为n个，则最优二叉树的结点数为2n-1个。

Const n=叶结点数的上限；m=2*n-1；{最优二叉树的结点数}Typenode=record{结点类型}data：<数据类型>；{权值}prt，lch，rch,lth：0‥m；{父指针、左、右指针和路径长度}end；wtype=array[1‥n] of <数据类型> ；{n个叶结点权值的类型}treetype=array[1‥m] of node；{最优二叉树的数组类型}Var tree：treetype；{其中tree [1‥n]为叶结点，tree [n+1‥2n-1]为中间结点，根为tree [2n-1]}四、构造最优二叉树的算法。

1引言数据结构课程是计算机及相关专业的核心课程，是程序设计的重要理论技术基础[1].在动态查找表中，平衡二叉树被广泛的应用，平衡二叉树又称AVL 树,它是由Adel ，son-Vel ，skii 和Landis 两位数学家于1962年提出并用他们的名字来命名的.平衡二叉树或者是一棵空树，或者是满足下列条件的二叉排序树：二叉排序树的所有结点的平衡因子为-1、0和1.所谓平衡因子BF （BalanceFactor ）可定义为某结点左子树的深度减去右子树的深度[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.3M 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--解决了学生的困惑.3平衡二叉树的调整方法根据平衡二叉树的定义可知，插入和删除结点造成平衡二叉树不平衡的原因是产生2或者-2的平衡因子，其实，调整的方法只需将以平衡因子为2或者-2为根结点的子二叉排序树重新找一个根结点建立新的子二叉排序树.从而使二叉排序树中的平衡因子都为-1、0或者1，即调整成为平衡二叉树.问题的关键是如何找根结点，即序列中的第一个结点，具体方法如下文所示规则.3.1插入结点的调整插入结点时，可以利用规则一、规则二进行：规则一某结点的平衡因子为2时，把以该结点为根的树采用中序遍历的方法进行遍历，即得到一个递增的子序列，同时看该结点的左孩子的平衡因子.（1）若左孩子的平衡因子为-1时，则取该左孩子的右孩子结点，并将其移动到序列的最前面，得到一个新的序列，对该序列构造二叉排序树.（2）若左孩子的平衡因子为1时，则取该左孩子结点，并将其移动到序列的最前面，得到一个新序列，对该序列构造二叉排序树.规则二某结点的平衡因子为-2时，把以该结点为根的树采用中序遍历的方法进行遍历，即得到一个递增的子序列，同时看该结点的右孩子的平衡因子.（1）若右孩子的平衡因子为-1时，则取该右孩子结点，并将其移动到序列的最前面，得到一个新的序列，对该序列构造二叉排序树.（2）若右孩子的平衡因子为1时，则取该右孩子的左孩子结点，并将其移动到序列的最前面，得到一个新序列，对该序列构造二叉排序树.3.2删除结点的调整删除结点时，要确定删除的结点是否是叶子结点，具体方法见规则三.规则三（1）若删除的是叶子结点，直接删除，并且自底向下查看树中的平衡因子，若发现存在平衡因子为2时，采用规则一进行调整，若平衡因子为-2时，则采用规则二进行调整.（2）若不是叶子结点，首先按照二叉排序树非叶子结点的删除方法即用该结点左子树的最大值（或者右子树的最小值）代替该结点，然后在从二叉排序树中删去它的最大值（或者最小值），同样，自底向下查看树中的平衡因子，若发现存在平衡因子为2时，采用规则一进行调整，若平衡因子为-2时，则采用规则二进行调整.4算法描述4.1插入结点的算法平衡二叉树的插入实现算法步骤：（1）插入结点L（L总是作为新的叶子结点插入的），插入的方法同一般的二叉排序树插入结点一样.（2）沿着插入结点L的路线返回，逐层回溯.必要时修改L的祖先的平衡因子，发现平衡因子为2或-2时，则利用规则一、规则二找到结点R.（3）把该二叉排序树进行中序遍历，得到一递增序列，并把结点R移动到该序列的最前面，然后对新形成的序列构造二叉排序树.同时检查树中其它结点，若发现平衡因子为2或-2的结点，进行调整.重复（2）（3）直到所有的结点都保持平衡为止.（4）回到（1），继续插入新的结点，直到所有的结点都插入完为止.实例1：输入关键字序列{16,3,7,11,9,26,18, 14,15}，构造一棵平衡二叉树[2].图1利用规则一、规则二构造AVL树的过程20 --4.2删除结点的算法平衡二叉树的删除实现算法步骤：（1）用二叉排序树的删除算法找到并删除结点L.（2）从被删除结点到根结点逐层向上回溯，必要时修改L的祖先结点的平衡因子，发现平衡因子为2或-2时，则利用规则一、规则二找到结点R.（3）把该二叉排序树进行中序遍历，得到一递增序列，并把结点R移动到该序列的最前面，然后对新形成的序列构造二叉排序树.（4）如果调整之后，子树的总高度比调整前降低了，仍然要继续回溯，直到所有结点平衡因子都为-1、0、1时，即都保持平衡为止.实例2：对实例1生成的AVL树，给出删除结点11,9,14的步骤[2].5结束语平衡二叉树的调整是数据结构教学中的重点和难点，学生在学习的过程中对该部分内容难以理解和接受，为了打破这种局面，作者通过阅读大量的资料，总结了此方法，该方法“只需找到新的根结点，重新构造成二叉排序树”即可，通过教学实践发现，本文采用的方法容易被学生理解和掌握，在教学中得到了良好的效果，得到学生的认可.———————————————————参考文献：〔1〕严蔚敏，吴伟民．数据结构(C语言版)[M]．北京：清华大学出版社，2007．〔2〕李春葆.数据结构教程（第2版）.北京：清华大学出版社，2007.〔3〕朱宇，张红彬．平衡二叉树的选择调整算法[J]．中国科学院研究生院学报，2006，23（4）:527-533．〔4〕胡云．快速构建AVL树[J]．安阳师范学院学报，2007（6）：61-63．〔5〕杜薇薇，张翼燕，瞿春柳．基于平衡因子的AVL 树设计实现[J]．计算机技术与发展，2010，20（3）: 24-27．〔6〕刘绍翰，高天行，黄志球．一种简化的AVL树的实现方法[J]．三峡大学学报(自然科学版)，2011，33（1）:85-87．图2删除AVL中结点的过程21--。