数据结构大作业(平衡二叉树)_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
数据结构大作业(平衡二叉树)
上传于||文档简介
&&本​程​序​的​功​能​就​是​将​二​叉​排​序​树​转​变​为​平​衡​二​叉​树​,​其​操​作​有​:​创​建​二​叉​树​、​插​入​数​据​、​删​除​数​据​、​输​出​、​销​毁​二​叉​树​和​退​出​。
阅读已结束，如果下载本文需要使用1下载券
想免费下载本文？
下载文档到电脑，查找使用更方便
还剩16页未读，继续阅读
你可能喜欢& & & 上一篇我们聊过，二叉查找树不是严格的O(logN)，导致了在真实场景中没有用武之地，谁也不愿意有O(N)的情况发生，
作为一名码农，肯定会希望能把&范围查找&做到地球人都不能优化的地步。
& & &当有很多数据灌到我的树中时，我肯定会希望最好是以&完全二叉树&的形式展现，这样我才能做到&查找&是严格的O(logN)，
比如把这种&树&调正到如下结构。
这里就涉及到了&树节点&的旋转，也是我们今天要聊到的内容。
一：平衡二叉树（AVL）
& & & &父节点的左子树和右子树的高度之差不能大于1，也就是说不能高过1层，否则该树就失衡了，此时就要旋转节点，在
编码时，我们可以记录当前节点的高度，比如空节点是-1，叶子节点是0，非叶子节点的height往根节点递增，比如在下图
中我们认为树的高度为h=2。
1 #region 平衡二叉树节点
/// &summary&
/// 平衡二叉树节点
/// &/summary&
/// &typeparam name="K"&&/typeparam&
/// &typeparam name="V"&&/typeparam&
public class AVLNode&K, V&
/// &summary&
/// 节点元素
/// &/summary&
/// &summary&
/// 增加一个高度信息
/// &/summary&
public int
/// &summary&
/// 节点中的附加值
/// &/summary&
public HashSet&V& attach = new HashSet&V&();
/// &summary&
/// 左节点
/// &/summary&
public AVLNode&K, V&
/// &summary&
/// 右节点
/// &/summary&
public AVLNode&K, V&
public AVLNode() { }
public AVLNode(K key, V value, AVLNode&K, V& left, AVLNode&K, V& right)
//KV键值对
this.key =
this.attach.Add(value);
this.left =
this.right =
#endregion
& & 节点再怎么失衡都逃不过4种情况，下面我们一一来看一下。
① 左左情况（左子树的左边节点）
我们看到，在向树中追加&节点1&的时候，根据定义我们知道这样会导致了&节点3"失衡，满足&左左情况&，可以这样想，把这
棵树比作齿轮，我们在&节点5&处把齿轮往下拉一个位置，也就变成了后面这样&平衡&的形式，如果用动画解释就最好理解了。
#region 第一种：左左旋转（单旋转）
/// &summary&
/// 第一种：左左旋转（单旋转）
/// &/summary&
/// &param name="node"&&/param&
/// &returns&&/returns&
public AVLNode&K, V& RotateLL(AVLNode&K, V& node)
//top：需要作为顶级节点的元素
var top = node.
//先截断当前节点的左孩子
node.left = top.
//将当前节点作为temp的右孩子
top.right =
//计算当前两个节点的高度
node.height = Math.Max(Height(node.left), Height(node.right)) + 1;
top.height = Math.Max(Height(top.left), Height(top.right)) + 1;
#endregion
② 右右情况（右子树的右边节点）
同样，&节点5&满足&右右情况&，其实我们也看到，这两种情况是一种镜像，当然操作方式也大同小异，我们在&节点1&的地方
将树往下拉一位，最后也就形成了我们希望的平衡效果。
#region 第二种：右右旋转（单旋转）
/// &summary&
/// 第二种：右右旋转（单旋转）
/// &/summary&
/// &param name="node"&&/param&
/// &returns&&/returns&
public AVLNode&K, V& RotateRR(AVLNode&K, V& node)
//top：需要作为顶级节点的元素
var top = node.
//先截断当前节点的右孩子
node.right = top.
//将当前节点作为temp的右孩子
top.left =
//计算当前两个节点的高度
node.height = Math.Max(Height(node.left), Height(node.right)) + 1;
top.height = Math.Max(Height(top.left), Height(top.right)) + 1;
#endregion
③左右情况（左子树的右边节点）
从图中我们可以看到，当我们插入&节点3&时，&节点5&处失衡，注意，找到&失衡点&是非常重要的，当面对&左右情况&时，我们将
失衡点的左子树进行"右右情况旋转"，然后进行&左左情况旋转&，经过这样两次的旋转就OK了，很有意思，对吧。
#region 第三种：左右旋转（双旋转）
/// &summary&
/// 第三种：左右旋转（双旋转）
/// &/summary&
/// &param name="node"&&/param&
/// &returns&&/returns&
public AVLNode&K, V& RotateLR(AVLNode&K, V& node)
//先进行RR旋转
node.left = RotateRR(node.left);
//再进行LL旋转
return RotateLL(node);
#endregion
④右左情况(右子树的左边节点）
这种情况和&情景3&也是一种镜像关系，很简单，我们找到了&节点15&是失衡点，然后我们将&节点15&的右子树进行&左左情况旋转&，
然后进行&右右情况旋转&，最终得到了我们满意的平衡。
#region 第四种：右左旋转（双旋转）
/// &summary&
/// 第四种：右左旋转（双旋转）
/// &/summary&
/// &param name="node"&&/param&
/// &returns&&/returns&
public AVLNode&K, V& RotateRL(AVLNode&K, V& node)
//执行左左旋转
node.right = RotateLL(node.right);
//再执行右右旋转
return RotateRR(node);
#endregion
& & 如果我们理解了上面的这几种旋转，那么添加方法简直是轻而易举，出现了哪一种情况调用哪一种方法而已。
#region 添加操作
/// &summary&
/// 添加操作
/// &/summary&
/// &param name="key"&&/param&
/// &param name="value"&&/param&
/// &param name="tree"&&/param&
/// &returns&&/returns&
public AVLNode&K, V& Add(K key, V value, AVLNode&K, V& tree)
if (tree == null)
tree = new AVLNode&K, V&(key, value, null, null);
if (pareTo(tree.key) & 0)
tree.left = Add(key, value, tree.left);
//如果说相差等于2就说明这棵树需要旋转了
if (Height(tree.left) - Height(tree.right) == 2)
//说明此时是左左旋转
if (pareTo(tree.left.key) & 0)
tree = RotateLL(tree);
//属于左右旋转
tree = RotateLR(tree);
if (pareTo(tree.key) & 0)
tree.right = Add(key, value, tree.right);
if ((Height(tree.right) - Height(tree.left) == 2))
//此时是右右旋转
if (pareTo(tree.right.key) & 0)
tree = RotateRR(tree);
//属于右左旋转
tree = RotateRL(tree);
//将value追加到附加值中（也可对应重复元素）
if (pareTo(tree.key) == 0)
tree.attach.Add(value);
//计算高度
tree.height = Math.Max(Height(tree.left), Height(tree.right)) + 1;
#endregion
删除方法跟添加方法也类似，当删除一个结点的时候，可能会引起祖先结点的失衡，所以在每次&结点&回退的时候计算结点高度。
1 #region 删除当前树中的节点
/// &summary&
/// 删除当前树中的节点
/// &/summary&
/// &param name="key"&&/param&
/// &param name="tree"&&/param&
/// &returns&&/returns&
public AVLNode&K, V& Remove(K key, V value, AVLNode&K, V& tree)
if (tree == null)
return null;
if (pareTo(tree.key) & 0)
tree.left = Remove(key, value, tree.left);
//如果说相差等于2就说明这棵树需要旋转了
if (Height(tree.left) - Height(tree.right) == 2)
//说明此时是左左旋转
if (pareTo(tree.left.key) & 0)
tree = RotateLL(tree);
//属于左右旋转
tree = RotateLR(tree);
if (pareTo(tree.key) & 0)
tree.right = Remove(key, value, tree.right);
if ((Height(tree.right) - Height(tree.left) == 2))
//此时是右右旋转
if (pareTo(tree.right.key) & 0)
tree = RotateRR(tree);
//属于右左旋转
tree = RotateRL(tree);
/*相等的情况*/
if (pareTo(tree.key) == 0)
//判断里面的HashSet是否有多值
if (tree.attach.Count & 1)
//实现惰性删除
tree.attach.Remove(value);
//有两个孩子的情况
if (tree.left != null && tree.right != null)
//根据平衡二叉树的中顺遍历，需要找到&有子树&的最小节点
tree.key = FindMin(tree.right).
//删除右子树的指定元素
tree.right = Remove(tree.key, value, tree.right);
//自减高度
tree = tree.left == null ? tree.right : tree.
//如果删除的是叶子节点直接返回
if (tree == null)
return null;
//统计高度
tree.height = Math.Max(Height(tree.left), Height(tree.right)) + 1;
#endregion
不像上一篇不能在二叉树中灌有序数据，平衡二叉树就没关系了，我们的需求是检索 4:00:00 到
的登陆用户的ID，数据量在500w，看看平衡二叉树是如何秒杀对手。
2 using System.Collections.G
3 using System.L
4 using System.T
5 using System.T
6 using System.IO;
7 using System.D
9 namespace DataStruct
class Program
static void Main(string[] args)
AVLTree&int, int& avl = new AVLTree&int, int&();
Dictionary&DateTime, int& dic = new Dictionary&DateTime, int&();
AVLTree&DateTime, int& tree = new AVLTree&DateTime, int&();
for (int i = 1; i & 5000000; i++)
dic.Add(DateTime.Now.AddMinutes(i), i);
tree.Add(DateTime.Now.AddMinutes(i), i);
//检索 4:00:00 到
5:00:00的登陆人数
var min = Convert.ToDateTime(" 4:00:00");
var max = Convert.ToDateTime(" 5:00:00");
var watch = Stopwatch.StartNew();
var result1 = dic.Keys.Where(i =& i &= min && i &= max).Select(i =& dic[i]).ToList();
watch.Stop();
Console.WriteLine("字典查找耗费时间:{0}ms", watch.ElapsedMilliseconds);
watch = Stopwatch.StartNew();
var result2 = tree.SearchRange(min, max);
watch.Stop();
Console.WriteLine("平衡二叉树查找耗费时间:{0}ms", watch.ElapsedMilliseconds);
#region 平衡二叉树节点
/// &summary&
/// 平衡二叉树节点
/// &/summary&
/// &typeparam name="K"&&/typeparam&
/// &typeparam name="V"&&/typeparam&
public class AVLNode&K, V&
/// &summary&
/// 节点元素
/// &/summary&
/// &summary&
/// 增加一个高度信息
/// &/summary&
public int
/// &summary&
/// 节点中的附加值
/// &/summary&
public HashSet&V& attach = new HashSet&V&();
/// &summary&
/// 左节点
/// &/summary&
public AVLNode&K, V&
/// &summary&
/// 右节点
/// &/summary&
public AVLNode&K, V&
public AVLNode() { }
public AVLNode(K key, V value, AVLNode&K, V& left, AVLNode&K, V& right)
//KV键值对
this.key =
this.attach.Add(value);
this.left =
this.right =
#endregion
public class AVLTree&K, V& where K : IComparable
public AVLNode&K, V& node = null;
#region 添加操作
/// &summary&
/// 添加操作
/// &/summary&
/// &param name="key"&&/param&
/// &param name="value"&&/param&
public void Add(K key, V value)
node = Add(key, value, node);
#endregion
#region 添加操作
/// &summary&
/// 添加操作
/// &/summary&
/// &param name="key"&&/param&
/// &param name="value"&&/param&
/// &param name="tree"&&/param&
/// &returns&&/returns&
public AVLNode&K, V& Add(K key, V value, AVLNode&K, V& tree)
if (tree == null)
tree = new AVLNode&K, V&(key, value, null, null);
if (pareTo(tree.key) & 0)
tree.left = Add(key, value, tree.left);
//如果说相差等于2就说明这棵树需要旋转了
if (Height(tree.left) - Height(tree.right) == 2)
//说明此时是左左旋转
if (pareTo(tree.left.key) & 0)
tree = RotateLL(tree);
//属于左右旋转
tree = RotateLR(tree);
if (pareTo(tree.key) & 0)
tree.right = Add(key, value, tree.right);
if ((Height(tree.right) - Height(tree.left) == 2))
//此时是右右旋转
if (pareTo(tree.right.key) & 0)
tree = RotateRR(tree);
//属于右左旋转
tree = RotateRL(tree);
//将value追加到附加值中（也可对应重复元素）
if (pareTo(tree.key) == 0)
tree.attach.Add(value);
//计算高度
tree.height = Math.Max(Height(tree.left), Height(tree.right)) + 1;
#endregion
#region 计算当前节点的高度
/// &summary&
/// 计算当前节点的高度
/// &/summary&
/// &param name="node"&&/param&
/// &returns&&/returns&
public int Height(AVLNode&K, V& node)
return node == null ? -1 : node.
#endregion
#region 第一种：左左旋转（单旋转）
/// &summary&
/// 第一种：左左旋转（单旋转）
/// &/summary&
/// &param name="node"&&/param&
/// &returns&&/returns&
public AVLNode&K, V& RotateLL(AVLNode&K, V& node)
//top：需要作为顶级节点的元素
var top = node.
//先截断当前节点的左孩子
node.left = top.
//将当前节点作为temp的右孩子
top.right =
//计算当前两个节点的高度
node.height = Math.Max(Height(node.left), Height(node.right)) + 1;
top.height = Math.Max(Height(top.left), Height(top.right)) + 1;
#endregion
#region 第二种：右右旋转（单旋转）
/// &summary&
/// 第二种：右右旋转（单旋转）
/// &/summary&
/// &param name="node"&&/param&
/// &returns&&/returns&
public AVLNode&K, V& RotateRR(AVLNode&K, V& node)
//top：需要作为顶级节点的元素
var top = node.
//先截断当前节点的右孩子
node.right = top.
//将当前节点作为temp的右孩子
top.left =
//计算当前两个节点的高度
node.height = Math.Max(Height(node.left), Height(node.right)) + 1;
top.height = Math.Max(Height(top.left), Height(top.right)) + 1;
#endregion
#region 第三种：左右旋转（双旋转）
/// &summary&
/// 第三种：左右旋转（双旋转）
/// &/summary&
/// &param name="node"&&/param&
/// &returns&&/returns&
public AVLNode&K, V& RotateLR(AVLNode&K, V& node)
//先进行RR旋转
node.left = RotateRR(node.left);
//再进行LL旋转
return RotateLL(node);
#endregion
#region 第四种：右左旋转（双旋转）
/// &summary&
/// 第四种：右左旋转（双旋转）
/// &/summary&
/// &param name="node"&&/param&
/// &returns&&/returns&
public AVLNode&K, V& RotateRL(AVLNode&K, V& node)
//执行左左旋转
node.right = RotateLL(node.right);
//再执行右右旋转
return RotateRR(node);
#endregion
#region 是否包含指定元素
/// &summary&
/// 是否包含指定元素
/// &/summary&
/// &param name="key"&&/param&
/// &returns&&/returns&
public bool Contain(K key)
return Contain(key, node);
#endregion
#region 是否包含指定元素
/// &summary&
/// 是否包含指定元素
/// &/summary&
/// &param name="key"&&/param&
/// &param name="tree"&&/param&
/// &returns&&/returns&
public bool Contain(K key, AVLNode&K, V& tree)
if (tree == null)
return false;
if (pareTo(tree.key) & 0)
return Contain(key, tree.left);
if (pareTo(tree.key) & 0)
return Contain(key, tree.right);
return true;
#endregion
#region 树的指定范围查找
/// &summary&
/// 树的指定范围查找
/// &/summary&
/// &param name="min"&&/param&
/// &param name="max"&&/param&
/// &returns&&/returns&
public HashSet&V& SearchRange(K min, K max)
HashSet&V& hashSet = new HashSet&V&();
hashSet = SearchRange(min, max, hashSet, node);
return hashS
#endregion
#region 树的指定范围查找
/// &summary&
/// 树的指定范围查找
/// &/summary&
/// &param name="range1"&&/param&
/// &param name="range2"&&/param&
/// &param name="tree"&&/param&
/// &returns&&/returns&
public HashSet&V& SearchRange(K min, K max, HashSet&V& hashSet, AVLNode&K, V& tree)
if (tree == null)
return hashS
//遍历左子树（寻找下界）
if (pareTo(tree.key) & 0)
SearchRange(min, max, hashSet, tree.left);
//当前节点是否在选定范围内
if (pareTo(tree.key) &= 0 && pareTo(tree.key) &= 0)
//等于这种情况
foreach (var item in tree.attach)
hashSet.Add(item);
//遍历右子树（两种情况：①:找min的下限 ②：必须在Max范围之内）
if (pareTo(tree.key) & 0 || pareTo(tree.key) & 0)
SearchRange(min, max, hashSet, tree.right);
return hashS
#endregion
#region 找到当前树的最小节点
/// &summary&
/// 找到当前树的最小节点
/// &/summary&
/// &returns&&/returns&
public AVLNode&K, V& FindMin()
return FindMin(node);
#endregion
#region 找到当前树的最小节点
/// &summary&
/// 找到当前树的最小节点
/// &/summary&
/// &param name="tree"&&/param&
/// &returns&&/returns&
public AVLNode&K, V& FindMin(AVLNode&K, V& tree)
if (tree == null)
return null;
if (tree.left == null)
return FindMin(tree.left);
#endregion
#region 找到当前树的最大节点
/// &summary&
/// 找到当前树的最大节点
/// &/summary&
/// &returns&&/returns&
public AVLNode&K, V& FindMax()
return FindMin(node);
#endregion
#region 找到当前树的最大节点
/// &summary&
/// 找到当前树的最大节点
/// &/summary&
/// &param name="tree"&&/param&
/// &returns&&/returns&
public AVLNode&K, V& FindMax(AVLNode&K, V& tree)
if (tree == null)
return null;
if (tree.right == null)
return FindMax(tree.right);
#endregion
#region 删除当前树中的节点
/// &summary&
/// 删除当前树中的节点
/// &/summary&
/// &param name="key"&&/param&
/// &returns&&/returns&
public void Remove(K key, V value)
node = Remove(key, value, node);
#endregion
#region 删除当前树中的节点
/// &summary&
/// 删除当前树中的节点
/// &/summary&
/// &param name="key"&&/param&
/// &param name="tree"&&/param&
/// &returns&&/returns&
public AVLNode&K, V& Remove(K key, V value, AVLNode&K, V& tree)
if (tree == null)
return null;
if (pareTo(tree.key) & 0)
tree.left = Remove(key, value, tree.left);
//如果说相差等于2就说明这棵树需要旋转了
if (Height(tree.left) - Height(tree.right) == 2)
//说明此时是左左旋转
if (pareTo(tree.left.key) & 0)
tree = RotateLL(tree);
//属于左右旋转
tree = RotateLR(tree);
if (pareTo(tree.key) & 0)
tree.right = Remove(key, value, tree.right);
if ((Height(tree.right) - Height(tree.left) == 2))
//此时是右右旋转
if (pareTo(tree.right.key) & 0)
tree = RotateRR(tree);
//属于右左旋转
tree = RotateRL(tree);
/*相等的情况*/
if (pareTo(tree.key) == 0)
//判断里面的HashSet是否有多值
if (tree.attach.Count & 1)
//实现惰性删除
tree.attach.Remove(value);
//有两个孩子的情况
if (tree.left != null && tree.right != null)
//根据平衡二叉树的中顺遍历，需要找到&有子树&的最小节点
tree.key = FindMin(tree.right).
//删除右子树的指定元素
tree.right = Remove(tree.key, value, tree.right);
//自减高度
tree = tree.left == null ? tree.right : tree.
//如果删除的是叶子节点直接返回
if (tree == null)
return null;
//统计高度
tree.height = Math.Max(Height(tree.left), Height(tree.right)) + 1;
#endregion
wow,相差98倍，这个可不是一个级别啊...AVL神器。
阅读(...) 评论()叶子节点有n个，求平衡二叉树的深度最多是多少？哪位大侠会，跟小弟说说啊。。
[问题点数：100分，结帖人romeprince]
叶子节点有n个，求平衡二叉树的深度最多是多少？哪位大侠会，跟小弟说说啊。。
[问题点数：100分，结帖人romeprince]
不显示删除回复
显示所有回复
显示星级回复
显示得分回复
只显示楼主
2010年6月 专题开发/技术/项目大版内专家分月排行榜第三
本帖子已过去太久远了，不再提供回复功能。Java 平衡二叉树初实现 - Jaward华仔 - 博客园
随笔 - 20, 文章 - 6, 评论 - 0, 引用 - 0
(12.21.12)之前有人问到排序不正确的问题，是因为pareTo(String)是由左至右按逐个字符ASCII码大小排序的，所以10比9小。
要区分数字和字符串，可参考以下代码
1 //使到数字按数字大小排序，字符按字典大小排序，数字永远比字符小
boolean compare(String s1, String s2) {
Pattern pattern = pile("[0-9]*");
if ( pattern.matcher(s1).matches()
&& pattern.matcher(s2).matches()) {
long a = Long.parseLong(s1);
long b = Long.parseLong(s2);
if ( a & b)
return true;
return false;
if ( pattern.matcher(s1).matches() )
return true;
if ( pattern.matcher(s2).matches() )
return false;
if ( s1.compareTo(s2) & 0)
return true;
return false;
1 package AVLT
import javax.swing.*;
import java.awt.*;
import java.io.*;
import java.util.S
public class Tree {
//结点数据
private int balF //结点平衡因子。只有0，1，-1态
private final int leftHigher = 1;
private final int equalHigh = 0;
private final int
rightHigher = -1;
private Tree LChild, RC
private boolean head = true;
private boolean
private Tree P
//用于创建叶子时记录双亲。
private boolean leftChildR //true创建左孩子，false创建右孩子
public Tree(String exampleData) {
this.data = exampleD
this.balFactor = 0;
this.LChild = null;
this.RChild = null;
boolean insertTree(Tree T, String keyData) {
//创建树根######################################################################################
if (this.head) {
T.data = keyD
this.taller = true;
this.head = false;
//遍历到叶子的时候#############################################################################
else if(T == null) {
if (leftChildRecord) {
//上次记录是左孩子的话
Parent.LChild = new Tree(keyData);
else { //否即是右孩子
Parent.RChild = new Tree(keyData);
this.taller = true;
//树枝的情况##################################################################################
if (T.data.equals(keyData)) {// 已有就不再录入了
this.taller = false;
return false;
else if (pareTo(T.data) & 0) {
//将从T的左子树进行搜索，先进行记录
Parent = T;
leftChildRecord = true;
if (insertTree(T.LChild, keyData) == false) {
//没有插入
return false;
else if(this.taller) {
switch (T.balFactor) {//检查T的平衡度
case leftHigher://原来的左子树就已经比右子树高，需左平衡
LeftBalance(T);
this.taller = false;
case equalHigh://原来等高
T.balFactor = leftH //现在左子树增高了一层
this.taller = true;
case rightHigher://原来右子树比坐姿势高
T.balFactor = equalH//现在等高
this.taller = false;
else {// 即 pareTo(T.data) &
0，与上边情况对称，不再作注释。
Parent = T;
leftChildRecord = false;
if (insertTree(T.RChild, keyData) == false) {
return false;
else if (this.taller) {
switch (T.balFactor) {
case leftHigher:
T.balFactor = equalH
this.taller = false;
case equalHigh:
T.balFactor = rightH
this.taller = true;
case rightHigher:
RightBalance(T);
this.taller = false;
return true;
//右旋操作
private void RightRotate (Tree T) {
Tree LeftK
LeftKid = T.LC
T.LChild = LeftKid.LC
LeftKid.LChild = LeftKid.RC
LeftKid.RChild = T.RC
T.RChild = LeftK
t = T. T.data = LeftKid. LeftKid.data =
//左旋操作,与右旋对称，不再画图了&&
private void LeftRotate (Tree T) {
Tree RightK
RightKid = T.RC
T.RChild = RightKid.RC
RightKid.RChild = RightKid.LC
RightKid.LChild = T.LC
T.LChild =
t = T. T.data = RightKid. RightKid.data =
private void LeftBalance ( Tree T) {
Tree LeftSubTree, LChildRightSubT
LeftSubTree = T.LC
switch (LeftSubTree.balFactor) {
case leftHigher: // T左孩子的左子树高了，作右旋处理
T.balFactor = equalH
LeftSubTree.balFactor = equalH
RightRotate(T);
case rightHigher://T左孩子的右子树高了，作双旋处理（因为每次都会及时处理掉，所以这是最底端的情况）
LChildRightSubTree = LeftSubTree.RC
switch (LChildRightSubTree.balFactor) {
case leftHigher:// T左孩子的右孩子的左子树高了
T.balFactor = rightH
LeftSubTree.balFactor = equalH
case equalHigh:
T.balFactor
LeftSubTree.balFactor = equalH
case rightHigher:
T.balFactor = equalH
LeftSubTree.balFactor = leftH
LChildRightSubTree.balFactor = equalH
//平衡过后T左孩子的右孩子恢复平衡
LeftRotate(T.LChild); //继续向上平衡
RightRotate(T);////继续向上平衡
// 右平衡，与左平衡对称，不再累述。
private void RightBalance ( Tree T) {
Tree RightSubTree, RChildLeftSubT
RightSubTree = T.RC
switch (RightSubTree.balFactor) {
case rightHigher:
T.balFactor = equalH
RightSubTree.balFactor = equalH
LeftRotate(T);
case leftHigher:
RChildLeftSubTree = RightSubTree.LC
switch (RChildLeftSubTree.balFactor) {
case rightHigher:
T.balFactor = leftH
RightSubTree.balFactor = equalH
case equalHigh:
T.balFactor
RightSubTree.balFactor = equalH
case leftHigher:
T.balFactor = equalH
RightSubTree.balFactor = rightH
RChildLeftSubTree.balFactor = equalH
RightRotate(T.RChild);
LeftRotate(T);
//中序遍历树
public void middle(Tree T) {
if (T == null) {
middle(T.LChild);
System.out.println(T.data);
middle(T.RChild);
public static void main(String[] args) throws IOException {
Tree Free = new Tree(null);
File file=new File("e:/test.txt");//源文件位置
FileReader fr=new FileReader(file);//创建文件输入流
BufferedReader in=new BufferedReader(fr);//包装文件输入流，可整行读取
while((line=in.readLine()) != null) {
String[] str=line.split(" ");
for (int i = 0; i & str. i++) {
Free.insertTree(Free, str[i]);
in.close();
Free.middle(Free);