这里有一些不太合理的代码，比如把AVL树专属的平衡因子加入到了树的定义上，这是最开始遗留的问题，暂时没改，等以后敲其他树的算法的时候再改一下吧
package com.bn;
public abstract class Tree{
//左孩子
private Tree left;
//右孩子
private Tree right;
//父亲节点
private Tree father;
//数据
private int entry;
//树的高度
private int height;
//树的平衡因子,左子树高度-右子树高度
private int balance;
public Tree(int value){
//节点数值随便现给定一个
entry=value;
//此时是叶子节点，高度为1
height=1;
//叶子节点必然平衡
balance=0;
left=null;
right=null;
father=null;
}
public void setLeftSon(Tree son){
this.left=son;
//我们可以往子树上插入空树，此时就无需设定子树的父亲
if (son!=null){
son.father=this;
}
}
//设置右子树
public void setRightSon(Tree son){
this.right=son;
//我们可以往子树上插入空树，此时就无需设定子树的父亲
if (son!=null){
son.father=this;
}
}
//将当前树替换为t树
//不会改变父亲与当前树的关系
//这里不是深度copy,子树并没有重新构造对象，必须保证替换后t树的不再被引用
//否则会存在两颗树同时指向一个子树的BUG
public void replace(Tree t){
// this.father=t.father; 除了爸爸，其他每一个都复制一下
this.setLeftSon(t.left);
this.setRightSon(t.right);
this.height=t.height;
this.balance=t.balance;
this.entry=t.entry;
}
//判断其是不是父亲的左孩子
public boolean isFatherLeftSon(){
return this==father.left;
}
//更新树的高度，只能从该位置开始,如果需要更新全部节点高度，
//只能争对每一个叶子节点使用一次，建议建树的时候就开始更新
//返回第一个失衡点的引用,传送的时候需要传送一个空应用
public Tree updateHeight(Tree firstBreakBalanceTree){
//先假定一个不可能的数值
int newHeight=-1;
//两颗子树都存在
if(left!=null&&right!=null){
//当前高度为，两颗子树高度的最大值加1
newHeight=Math.max(left.height, right.height)+1;
//调整平衡因子
balance=left.height-right.height;
}else if(left==null&&right==null){//此时为叶子节点
//叶子节点高度为0
newHeight=1;
//调整平衡因子
balance=0;
}else if(left!=null){//如果左子树不是空树，且右子树是空树
newHeight=left.height+1;
//调整平衡因子
balance=left.height;
}else if(right!=null){//如果右子树不是空树，且左子树是空树
newHeight=right.height+1;
//调整平衡因子
balance=-right.height;
}
//这棵树破坏平衡，并且我们还没有找到破坏平衡的树
if ((balance<-1||balance>1)&&firstBreakBalanceTree==null){
//那么这个第一棵破坏平衡的树就是他了
firstBreakBalanceTree=this;
}
//前后两次高度不相等，说明树高度变化
if(height!=newHeight){
height=newHeight;
//如果存在父节点
if(father!=null){
//开始递归
return father.updateHeight(firstBreakBalanceTree);
}
}
//返回第一棵破坏平衡的数
return firstBreakBalanceTree;
}
public void setBalance(int balance) { this.balance = balance; }
public void setHeight(int height) { this.height = height; }
public void setEntry(int entry){ this.entry=entry; }
//获得数据
public int getEntry() { return entry; }
//获得高度
public int getHeight() {
return height;
}
//获得平衡因子
public int getBalance() {
return balance;
}
//获得父亲节点
public Tree getFather() {
return father;
}
//获得左子树
public Tree left() {
return left;
}
//获得右子树
public Tree right() { return right; }
//递归插入树，内部调用
public abstract void insert_rec(Tree newTree);
//插入一个数据到树中，开放给别人使用
public abstract void insert(int value);
//递归删除一颗树
public abstract void delete_rec();
//删除一颗树，其数值等于value的数值
public abstract void delete(int value);
//查找一颗树，其数值等于value的数值
public abstract Tree search(int value);
//打印一棵树
public abstract void printTree();
public void Preorder(){
if(left!=null){
left.Preorder();
}
System.out.print(this.entry+" ");
if (right!=null){
right.Preorder();
}
}
//树的字符串表现形式
@Override
public String toString() {
//如果是空树就打印____符
if (entry==-10){
return "{entry=null}t";
}else{
return "{entry="+entry+",height="+height+",balance="+balance+"}t";
}
}
}
二、AVL定义（AVL）
想要表述的都写在注释里面啦，第一次尝试敲AVL，如有错误的地方欢迎指出，有不懂的地方也可以私信我
package com.bn;
import java.util.Queue;
import java.util.concurrent.ArrayBlockingQueue;
public class AVL extends Tree
{
final static int TYPE_RR=0;
final static int TYPE_LL=1;
final static int TYPE_RL=2;
final static int TYPE_LR=3;
final static int TYPE_R0=5;
final static int TYPE_L0=6;
final static int TYPE_ERROR=4;
public static void main(String[] args){
int[] array={4,8,16,5,3,15,14,9,6,13,7,11,12,10,1,2,19,18,17};
AVL avl=null;
for(int i:array){
if (avl==null){
avl=new AVL(i);
}else{
avl.insert(i);
System.out.println("======插入"+i+"后======");
avl.printTree();
System.out.println();
}
}
avl.Preorder();
for(int i:array){
System.out.println("n======删除"+i+"后======");
avl.delete(i);
avl.printTree();
}
}
//生成一颗树
public AVL(int entry){
super(entry);
}
//返回自己平衡的类型
public int breakBalanceType(){
int balance=this.getBalance();
Tree left=this.left();
Tree right=this.right();
//左子树高度高了2
if(balance==2){
//左子树的左子树高，为LL形状
if(left.getBalance()==1){
return TYPE_LL;
}else if(left.getBalance()==-1){//如果是左子树的右子树高，则为LR形状
return TYPE_LR;
}else if (left.getBalance()==0){//删除子树的时候会出现这种情况，具体情形见调整部分
return TYPE_L0;
}
}else if(balance==-2){//右子树高了2
//右子树的右子树高，为RR形状
if(right.getBalance()==-1){
return TYPE_RR;
}else if(right.getBalance()==1){//如果是右子树的左子树高,则为RL形状
return TYPE_RL;
}else if (right.getBalance()==0){//删除子树的时候会出现这种情况，具体情形见调整部分
return TYPE_R0;
}
}
//不是这几种情况的都是错误的
//如果自己是平衡树，也不该调用这个方法，所以返回ERROR
return TYPE_ERROR;
}
//调整RR型
public void adjustLL(){
//A,B,C,D,E为中序遍历序列对应编号、x
//A,B,两棵树需要大改动，故重新建立节点
AVL A=new AVL(this.getEntry());
AVL B=new AVL(this.left().getEntry());
//C,D,E三棵子树只需调整位置，无需改动
AVL C=(AVL) this.left().left();
AVL D=(AVL) this.left().right();
AVL E=(AVL) this.right();
B.setLeftSon(C);
B.setRightSon(A);
A.setLeftSon(D);
A.setRightSon(E);
//假设调整情况如上图,由于A是我们新new的根节点，高度为1而不是2
//调整后高度任然为1，此时就会认为A的高度没有发生改变
//自然不会去递归的调整B的高度，但是实际上A的高度是发生改变的
//故我们需要将A的高度设定为一个不可能的数值，调整A节点后必然回去调整B节点
A.setHeight(-1);
//调整A的高度后会递归的调整B的高度
A.updateHeight(null);
//用新树替换this
//这里只是将新树中除father的成员拷贝到this中
this.replace(B);
}
//调整LL型
public void adjustRR(){
//A,C,两棵树需要大改动，故重新建立节点
AVL A=new AVL(this.getEntry());
AVL C=new AVL(this.right().getEntry());
//C,D,E三棵子树只需调整位置，无需改动
AVL D=(AVL) this.right().left();
AVL E=(AVL) this.right().right();
AVL B=(AVL) this.left();
C.setLeftSon(A);
C.setRightSon(E);
A.setLeftSon(B);
A.setRightSon(D);
//情况同上
A.setHeight(-1);
//调整A的高度后会递归的调整C的高度
A.updateHeight(null);
//用新树替换this
//这里只是将新树中除father的成员拷贝到this中
this.replace(C);
}
//调整LR型
public void adjustLR(){
//A,B,D节点变动较大，就不采用原本节点
Tree A=new AVL(this.getEntry());
Tree B=new AVL(this.left().getEntry());
Tree D=new AVL(this.left().right().getEntry());
//剩余树只是改变了父亲节点，无需改动，故不重新建树
Tree C=this.left().left();
Tree E=this.left().right().left();
Tree F=this.left().right().right();
Tree G=this.right();
D.setLeftSon(B);
D.setRightSon(A);
B.setLeftSon(C);
B.setRightSon(E);
A.setLeftSon(F);
A.setRightSon(G);
//情况同上
A.setHeight(-1);
B.setHeight(-1);
//只需调整A，C节点，D节点自动就调整好了
A.updateHeight(null);
B.updateHeight(null);
//用新树替换this
//这里只是将新树中除father的成员拷贝到this中
this.replace(D);
}
//调整RL型
public void adjustRL(){
//A,C,D节点变动较大，就不采用原本节点
Tree A=new AVL(this.getEntry());
Tree C=new AVL(this.right().getEntry());
Tree D=new AVL(this.right().left().getEntry());
//剩余树只是改变了父亲节点，无需改动，故不重新建树
Tree B=this.left();
Tree E=this.right().left().left();
Tree F=this.right().left().right();
Tree G=this.right().right();
D.setLeftSon(A);
D.setRightSon(C);
A.setLeftSon(B);
A.setRightSon(E);
C.setLeftSon(F);
C.setRightSon(G);
//情况同上
A.setHeight(-1);
C.setHeight(-1);
//只需调整A，C节点，D节点自动就调整好了
A.updateHeight(null);
C.updateHeight(null);
//用新树替换this
//这里只是将新树中除father的成员拷贝到this中
this.replace(D);
}
//调整R0型 删除后A平衡因子变为-2，C为0
public void adjustR0() {
//A,C节点变动较大，就不采用原本节点
Tree A=new AVL(this.getEntry());
Tree C=new AVL(this.right().getEntry());
//剩余树只是改变了父亲节点，无需改动，故不重新建树
Tree B=this.left();
Tree D=this.right().left();
Tree E=this.right().right();
C.setRightSon(E);
C.setLeftSon(A);
A.setRightSon(D);
A.setLeftSon(B);
//情况同上
A.setHeight(-1);
//只需调整A，C节点，D节点自动就调整好了
A.updateHeight(null);
//用新树替换this
//这里只是将新树中除father的成员拷贝到this中
this.replace(C);
}
//调整L0型 删除后A平衡因子变为2，B为0
public void adjustL0() {
//A,B节点变动较大，就不采用原本节点
Tree A=new AVL(this.getEntry());
Tree B=new AVL(this.left().getEntry());
//剩余树只是改变了父亲节点，无需改动，故不重新建树
Tree C=this.right();
Tree D=this.left().left();
Tree E=this.left().right();
B.setRightSon(A);
B.setLeftSon(D);
A.setRightSon(C);
A.setLeftSon(E);
//情况同上
A.setHeight(-1);
//只需调整A，C节点，D节点自动就调整好了
A.updateHeight(null);
//用新树替换this
//这里只是将新树中除father的成员拷贝到this中
this.replace(B);
}
//如果当前树不平衡，会将当前树调整至平衡树
//调整后的树依旧保持原来的父子树关系
public void adjustTree(){
//判断本树不平衡类型
int type=this.breakBalanceType();
//根据非平衡类型进行调整
switch (type){
case TYPE_RR://RR型
adjustRR();
break;
case TYPE_LL://LL型
adjustLL();
break;
case TYPE_RL://RL型
adjustRL();
break;
case TYPE_LR://LR型
adjustLR();
break;
case TYPE_R0://R0型,删除后可能出现的类型
adjustR0();
break;
case TYPE_L0://L0型，删除后可能出现的类型
adjustL0();
break;
case TYPE_ERROR://如果树已经平衡，或者出现了逻辑错误，我的思路下是不会出现这种情况的
System.out.println(this+" 出现错误");
break;
}
}
//check的同时会更新树的高度
//检查当前树是否平衡，不平衡则调整，之后递归的检查父节点是否平衡
public void check(){
//调整树高和平衡因子，并且检查返回第一个破坏平衡的树
AVL bbt=(AVL) this.updateHeight(null);
//如果存在不平衡的树，则需要对其进行调整
if (bbt!=null){
//调整bbt为平衡树，其父亲不一定是平衡树
bbt.adjustTree();
//先找到父亲节点
AVL father=(AVL)bbt.getFather();
//父亲不是根节点
if (father!=null){
//检查父亲节点是否平衡
father.check();
}
}
}
@Override
public void insert(int value) {
this.insert_rec(new AVL(value));
}
@Override
//newTree里面必须放的是AVL的引用，所以建议插入数据使用insert方法而不是这个
public void insert_rec(Tree newTree){
//小于应该去左子树
if(newTree.getEntry()this.getEntry()){//大于则去右子树
//如果正好没有右子树
if(this.right()==null){
//将新节点插入右子树
this.setRightSon(newTree);
//当前树的高度和平衡因子都有可能发生改变
//调整高度和平衡因子，并且检查是否出现失衡
//如果失衡则调整
this.check();
}else{//如果已经存在右子树
//则将节点插入到右子树
this.right().insert_rec(newTree);
}
}
}
public Tree search(int value){
//小于应该去左子树
if(valuethis.getEntry()){//大于则去右子树
//如果存在右子树
if(this.right()!=null){
//去右子树搜索
return this.right().search(value);
}else{//如果右子树为空，代表元素不在书中
System.out.println("==="+value+"不在本树中===");
return null;
}
}else{//正好等于，当前树就是我们要找的树
return this;
}
}
@Override
public void delete_rec() {
AVL father=(AVL)this.getFather();
Tree t=this.left();
AVL left=(AVL)this.left();
AVL right=(AVL)this.right();
//此时分为四种情况
if(left==null&&right==null){//第一种情况，要删除的点正好是叶子节点
//判断当前树是否为父亲的左子树
if(this.isFatherLeftSon()){
//删除该节点,方法结束后，delTree会变为野指针，自动会被GC回收
father.setLeftSon(null);
}else {
father.setRightSon(null);
}
//父亲有可能不平衡
//此时调整父亲节点直到平衡
if(father!=null){//如果delTree不是根节点的话
father.check();
}
}else if(left!=null&&right!=null){//左子树和右子树都存在
//找到左子树的最右边的节点E，用这个节点的值替换A的值，并且删除E节点,找右子树的最左节点也可
AVL E=left;
while (E.right()!=null){
E=(AVL) E.right();
}
//将E中的数值赋给A
this.setEntry(E.getEntry());
//删除E节点
E.delete_rec();
//删除节点后，父亲节点的高度可能发生变化，需要检查父亲节点是否平衡
if(father!=null){//如果delTree不是根节点的话
father.check();
}
}else if(left!=null){//只存在左子树，右子树不存在
//直接用左子树替代当前树即可
this.replace(this.left());
//删除节点后，父亲节点的高度可能发生变化，需要检查父亲节点是否平衡
if(father!=null){//如果delTree不是根节点的话
father.check();
}
}else if(right!=null){//只存在右子树，与只存在左子树类似
this.replace(this.right());
//删除节点后，父亲节点的高度可能发生变化，需要检查父亲节点是否平衡
if(father!=null){//如果delTree不是根节点的话
father.check();
}
}
}
//
@Override
public void delete(int value) {
//先查找值在不在树中
Tree delTree=this.search(value);
//如果数值不在树中，我们自然也无法删除这个值
if(delTree==null){
System.out.println("===删除失败===");
return;
}else if(this.getFather()==null&&this.getHeight()==1){
//节点高度为1并且无父亲节点，也就是单个节点的树，自然不能删除
System.out.println("n该树只剩值为"+value+"这一个节点，无法删除");
return;
}
//将这颗树删除
delTree.delete_rec();
}
//打印一棵树看看
@Override
public void printTree(){
//当前访问节点指针
Tree p;
//当前访问了几个节点
int visitedCount=0;
//当前访问的节点在第几层
int curLevel=0;
//高度为k的平衡树，至多2^k-1个节点,但是我这里又多画了一层空树，空树之多为2*n+1，n是节点数
int maxNodeCount=2*((int)Math.pow(2,getHeight())-1)+1;
//保证队列足够长
Queue queue=new ArrayBlockingQueue<>(maxNodeCount);
//根节点入队
queue.add(this);
//当队列中还有着元素时
while (!queue.isEmpty()){
//第一个元素出队
p=queue.remove();
//当前访问的元素自增
visitedCount++;
//节点所在层数
int newLevel=(int) Math.floor(Math.log(visitedCount)/Math.log(2))+1;
//换层即换行
if(newLevel!=curLevel){
System.out.println();
System.out.println("Level "+newLevel+":");
curLevel=newLevel;
}
//打印树的信息
System.out.print(p);
//记录当前指针的1左右子树
Tree left=p.left();
Tree right=p.right();
//多打印一层空树,-10判断当前树是否为空树
if (left==null&&p.getEntry()!=-10){
//创建一棵值为-10的树
left=new AVL(-10);
//调整树高度
left.updateHeight(null);
}
if (right==null&&p.getEntry()!=-10){
//创建一棵值为-10的树
right=new AVL(-10);
//调整树高度
right.updateHeight(null);
}
if(left!=null){
queue.add(left);
}
if(right!=null){
queue.add(right);
}
}
}
}
三、输出结果
运行代码后会 依次插入4,8,16,5,3,15,14,9,6,13,7,11,12,10,1,2,19,18,17这些节点构造树，并且再依次删除。每次插入删除都会打印一下树的形状，采取层次遍历的方式打印树，打印的时候如过一个节点存在空子树，会把空子树在下一层也打印一遍，不过空子树的空子树不会打印，第四层的两颗null树分别是第三层值为5的节点的两颗空子树，差不多就是这个规律吧。等以后有时间我把具体过程写上。
Level 1:
{entry=8,height=3,balance=1}
Level 2:
{entry=4,height=2,balance=-1} {entry=16,height=1,balance=0}
Level 3:
{entry=null} {entry=5,height=1,balance=0} {entry=null} {entry=null}
Level 4:
{entry=null} {entry=null}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）