JAVA代码实现
package main.com.Tree;
class AvlNode{
//每个节点中储存的数据
int data;
//左孩子节点
AvlNode lNode;
//右节点
AvlNode rNode;
//树的高度,用于判断树是否平衡
int height;
public AvlNode(int data){
this.data=data;
//初始高度是1，即只有一个根节点
this.height=1;
}
}
public class AvlTree {
//获取一棵树的高度
public static int height(AvlNode node){
//如果树是空，那么高度也就是0
return node==null ? 0 : node.height;
}
//判断当前树是否平衡，用来判断树是否需要旋转
public static boolean isBalanced(AvlNode node){
//如果高度小于等于1，那么就是一个只有根节点，是平衡树。
if(height(node)<=1){return true;}
//计算左右分支的高度差，小于等于1的就是平衡树
return Math.abs(height(node.lNode)-height(node.rNode))<=1;
}
//右旋
/*
----->
3 2
/ /
2 1 3
/
1
*/
public static AvlNode Right_Rotate(AvlNode node){
//用来存放根节点
AvlNode root;
//左旋操作
root=node.lNode;
node.lNode=root.rNode;
root.rNode=node;
//重新计算计算节点高度
node.height=Math.max(height(node.lNode),height(node.rNode))+1;
root.height=Math.max(height(root.lNode),height(root.rNode))+1;
//返回旋转之后的树
return root;
}
/*左旋
----->
1 2
/
2 1 3
3
*/
public static AvlNode Left_Rotate(AvlNode node){
AvlNode root;
root=node.rNode;
node.rNode=root.lNode;
root.lNode=node;
//上面只对node节点（也就是图中的1节点）root节点（也就是2节点）进行了操作，所以下面对其进行高度的重新计算
node.height=Math.max(height(node.lNode),height(node.rNode))+1;
root.height= Math.max(height(root.lNode),height(root.rNode))+1;
return root;
}
/*左右，先左旋，再右旋
------> ------->
3 3 2
/ / /
1 2 1 3
/
2 1
*/
public static AvlNode Left_Right_Rotate(AvlNode node){
AvlNode root;
//先将node的左子树左旋
node.lNode=Left_Rotate(node.lNode);
//然后将node右旋
root=Right_Rotate(node);
return root;
}
/*先右旋，再左旋。
---------> ---------->
3 3 4
/
5 4 3 5
/
4 5
*/
public static AvlNode Right_Left_Rotate(AvlNode node){
AvlNode root;
//将右子树右旋
node=Right_Rotate(node.rNode);
//再将node树左旋
root=Left_Rotate(node);
return root;
}
//node：是目标树。
//data：要插入到目标树的数据
public static AvlNode insert(AvlNode node,int data){
AvlNode insertNode=new AvlNode(data);
//首先判断node是不是空
if(node==null) {
//如果是空那么新插入的节点就是跟节点
return insertNode;
}
if(data>node.data){
//插入数据大于当前节点，遍历右节点
node.rNode=insert(node.rNode,data);
//插入完成后计算节点的高度
node.height=Math.max(height(node.lNode),height(node.rNode))+1;
//进行平衡操作
if(!isBalanced(node)){
//如果树不平衡，则进行平衡操作。
//因为是插入的右节点。所以只可能是：右-右型和左右型
if(data<node.rNode.data){
//如果插入的数据小于node的右节点就是：右左型
node=Right_Left_Rotate(node);
}else{
//否则就是：右右型
node=Left_Rotate(node);
}
}
}else{
//小于等于都往左边插入
node.lNode=insert(node.lNode,data);
//插入完成后计算节点的高度
node.height=Math.max(height(node.lNode),height(node.rNode))+1;
//处理平衡
if(!isBalanced(node)){
if(data>node.lNode.data){
//左右型
node=Left_Right_Rotate(node);
}else{
//左左型
node=Right_Rotate(node);
}
}
}
return node;
}
}
测试代码
public class TreeTest {
public static void main(String[] args) {
AvlNode tree=AvlTree.insert(null,1);
tree=AvlTree.insert(tree,2);
tree=AvlTree.insert(tree,3);
tree=AvlTree.insert(tree,4);
tree=AvlTree.insert(tree,5);
tree=AvlTree.insert(tree,6);
tree=AvlTree.insert(tree,7);
tree=AvlTree.insert(tree,8);
}
}
可以使用IDEA的debug查看树的结构
