欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构[一] 平衡二叉树 AVL树结构详解 [Java实现]

程序员文章站 2022-05-06 23:44:15
...

##博客思维导图

数据结构[一] 平衡二叉树 AVL树结构详解 [Java实现]

###简述

先不说平衡二叉树,我们单开来说,这样比较方便理解。 **先说二叉树,再说平衡条件,没那么多花里胡哨的理论,我只是想让大家看完能明白,能写出来**

###二叉树

什么是二叉树?二叉树数据结构,顾名思义,只有两个叉,在数据结构中,操作性能要远高于线性结构,有O(height)的索引性能。与线性结构有相同的空间复杂度,特性如下:
  • 每个节点最多只有两个儿子节点
  • 左儿子小,右儿子大 (大小按照我们默认的比较规则,本例用int来比较)

####线性找7与二叉树找7

数据结构[一] 平衡二叉树 AVL树结构详解 [Java实现] $ $ 线性找7
数据结构[一] 平衡二叉树 AVL树结构详解 [Java实现] $ $ 二叉树找7
okay,我想大家聪明人已经看出来了,二叉树搜索用了2次,而线性结构却用了5次。 说白了,二叉树结构,我每次问一个节点,都会离着我的目标越来越近,但是线性的则不然,我必须一个个问。 说到这儿,我想会有博友提出质疑了,如果线性查找,7恰好就在第一个呢?那不是一下就找到了吗? 哈哈,你怎么不上天呢 - -。还第一个。开个小玩笑。 这就是二叉树索引的好处。相比看图比码字要清楚的多。

####平衡条件

那么,什么叫平衡呢?其实很简单,任何一个节点的子节点高度差必须小于2

数据结构[一] 平衡二叉树 AVL树结构详解 [Java实现] $ $ 第一个二叉平衡树
  • 从下往上数,第一个高度为1(比较符合日常生活数数),那我们数数吧
  • 5:————1高度 | 4,7,23,71 ————2高度| 6,50 ————3高度 | 15 ————4高度
  • 比如节点6,那么4和7的高度都是2,那就2-2 < 2 。平衡!!

####难点一 递归

数据结构[一] 平衡二叉树 AVL树结构详解 [Java实现] $ $ 递归查找

我又加入了一些节点,方便大家理解递归深度

  • 每一次正向橙色线条的滚动,就是一次递归查找
  • 每一次正向橙色线条的滚动,方法的入栈!
  • 递归的深度,取决于线条走了几次,那就有多大的栈深度
  • 本次查找,刨除root,共4次进栈



####难点二 回溯

数据结构[一] 平衡二叉树 AVL树结构详解 [Java实现] $ $ 插入回溯

先不要关心这个旋转操作,如图所示,我们在递归的基础上,沿着线条理解一下回溯

  • 每一次逆向橙色线条的滚动,就是一次回溯
  • 操作递归的每一个节点,都会在回溯的轨迹上
  • 正因为每一次递归,都有每一次回溯,那么,我们就可以先完成相关操作(增加或删除)之后,判定平衡



####4种旋转

数据结构[一] 平衡二叉树 AVL树结构详解 [Java实现] $ $ 左左类型旋转
博主尽量放慢了速度,让大家看清楚究竟旋转是如何进行的,这是一个插入操作,我们看到在不平衡的时候,进行了左旋转,这里我们看到
  • 正向插入,递归3-2-1
  • 逆向回溯,1-2 判断平衡条件 ,是平衡的
  • 再次回溯,2-3,3的左边高度为2,右边没有节点为0,那么2-0 > 1,不平衡!

到这里我们基本上理解了平衡的判断,下面正式说一下旋转:

  • 判断不平衡边 在3节点判定,不平衡,那么左边高,我们需要调整左边,获取左边节点2
  • 判断旋转类型 这时候我们拿到节点2,判断节点2哪边高。左边高,为左左类型。右边高为左右旋转类型,我们先不管
  • 旋转操作 3.left = 2.right; 2.right = 3; 重新计算,2和3节点的高度
数据结构[一] 平衡二叉树 AVL树结构详解 [Java实现] $ $ 右右类型旋转[同上,不再叙述]



数据结构[一] 平衡二叉树 AVL树结构详解 [Java实现] $ $ 左右类型旋转

数据结构[一] 平衡二叉树 AVL树结构详解 [Java实现] $ $ 右左类型旋转

到此旋转就说完了,希望大家好好的理解第一个左左类型!理解了一个也就都理解了 后续部分没有讲是因为说太多反而更乱。 后续的理解不了没关系,我们代码在看

####代码基础部分

node类

public static class AvlNodeInteger{
        private Integer value;
        private Integer height;
        private AvlNodeInteger left;
        private AvlNodeInteger right;

        public AvlNodeInteger(int t){
            initNode(t,null,null,1);
        }

        public AvlNodeInteger(int t,AvlNodeInteger left,AvlNodeInteger right){
            initNode(t,left,right,null);
        }
        
        private void initNode(int t,AvlNodeInteger left,AvlNodeInteger right,Integer height){
            this.setValue(t);
            this.left = left;
            this.right = right;
            this.height = height;
        }

        public Integer getValue() {
            return value;
        }

        public void setValue(Integer value) {
            this.value = value;
        }

        public Integer getHeight() {
            return height;
        }

        public void setHeight(Integer height) {
            this.height = height;
        }

        public AvlNodeInteger getLeft() {
            return left;
        }

        public void setLeft(AvlNodeInteger left) {
            this.left = left;
        }

        public AvlNodeInteger getRight() {
            return right;
        }

        public void setRight(AvlNodeInteger right) {
            this.right = right;
        }
    }

####高度计算

    /***
     * 求一个节点的高度
     * @param t
     * @return
     */
    private int height(AvlNodeInteger t){
        return null == t ? 0 : t.getHeight();
    }
    /***
     * 求左右子节点最大高度
     * @param left
     * @param right
     * @return
     */
    private int maxHeight(AvlNodeInteger left,AvlNodeInteger right){
        return height(left) > height(right) ? height(left)  : height(right);
    }

####插入操作

旋转

 /***
     * 左左旋转模型
     * @param node  旋转之前的parent node 节点
     * @return  旋转之后的parent node节点
     */
    private AvlNodeInteger leftLeftRotate(AvlNodeInteger node){
        AvlNodeInteger newRoot = node.getLeft();
        node.setLeft(newRoot.getRight());
        newRoot.setRight(node);

        //由此node的高度降低了,newRoot的高度提高了。
         //newRoot的高度由node的高度而来
        node.setHeight(maxHeight(node.getLeft(),node.getRight())+1);
        newRoot.setHeight(maxHeight(newRoot.getLeft(),newRoot.getRight())+1);
        return newRoot;
    }


    /***
     * 右右旋转模型
     * @param node
     * @return
     */
    private AvlNodeInteger rightRightRotate(AvlNodeInteger node){
        AvlNodeInteger newRoot = node.getRight();
        node.setRight(newRoot.getLeft());
        newRoot.setLeft(node);

        //由此node的高度降低了,newRoot的高度提高了。
        //newRoot的高度由node的高度而来
        node.setHeight(maxHeight(node.getLeft(),node.getRight()));
        newRoot.setHeight(maxHeight(newRoot.getLeft(),newRoot.getRight()));
        return newRoot;
    }

    /**
     * 左右模型,先右右,再左左
     * @param node
     * @return
     */
    private AvlNodeInteger leftRightRotate(AvlNodeInteger node){
        //注意传递的参数
        node.setLeft(rightRightRotate(node.getLeft()));
        return leftLeftRotate(node);
    }

    /***
     * 右左模型,先左左,在右右
     * @param node
     * @return
     */
    private AvlNodeInteger rightLeftRotate(AvlNodeInteger node){
        node.setRight(leftLeftRotate(node.getRight()));
        return rightRightRotate(node);
    }

insert

/****
     * 对外开放,插入操作
     * @param val
     * @throws Exception
     */
    public void insert(Integer val) throws Exception {
        if(null == root){
            initRoot(val);
            size++;
            return;
        }

        if(contains(val)) throw new Exception("The value is already exist!");

        insertNode(this.root,val);
        size++;
    }
    

    /**
     * 递归插入
     * parent == null 到最底部插入前节点判断情况
     * @param parent
     * @param val
     * @return
     */
    private AvlNodeInteger insertNode(AvlNodeInteger parent,Integer val){
        if(parent == null){
           return createSingleNode(val);
        }
        if(val < parent.getValue()){    //插入判断,小于父节点,插入到右边
            //注意理解回溯,这里最终返回的是插入完成节点
            //每一层回溯,都会返回相应当时递归的节点!!!
            parent.setLeft(insertNode(parent.getLeft(),val));

            //判断平衡,不要在意这里的parent是谁,
            //这个parent肯定是递归层级上,回溯的一个节点!每一个节点都需要判断平衡
            if(height(parent.getLeft()) - height(parent.getRight()) > 1){
                Integer compareVal = (Integer) parent.getLeft().getValue();
                //左左旋转类型
                if(val < Integer.valueOf(compareVal)){
                    parent = leftLeftRotate(parent);
                }else{                  //左右旋转类型
                    parent = leftRightRotate(parent);
                }
            }
        }
        if(val > parent.getValue()){   //插入判断,小于父节点,插入到右边
            //注意理解回溯,这里最终返回的是插入完成节点
            //每一层回溯,都会返回相应当时递归的节点!!!
            parent.setRight(insertNode(parent.getRight(),val));

            //判断平衡,不要在意这里的parent是谁,
            //这个parent肯定是递归层级上,回溯的一个节点!每一个节点都需要判断平衡
            if(height(parent.getRight()) - height(parent.getLeft()) > 2){
                Integer compareVal = (Integer) parent.getLeft().getValue();
                if(val > compareVal){
                    parent = rightRightRotate(parent);
                }else{
                    parent = rightLeftRotate(parent);
                }
            }
        }

        parent.setHeight((maxHeight(parent.getLeft(),parent.getRight()))+1);
        return parent;
    }

####删除操作

  public void remove(Integer val) {
        if(null == val || null == root){
            return;
        }
        if(!contains(val)){
            return;
        }
        remove(root,val);
    }


    /****
     * AVL删除,平衡树实现
     * @param parent
     * @param val
     * @return
     */
    private AvlNodeInteger remove(AvlNodeInteger parent,Integer val){
        if(val < parent.getValue()){        //左子树递归查询
            //删除以后返回替换的新节点
            AvlNodeInteger newLeft = remove(parent.getLeft(),val);
            parent.setLeft(newLeft);
            //检查是否平衡,删除的左边,那么用右边-左边
            if(height(parent.getRight()) - height(parent.getLeft()) > 1){
                AvlNodeInteger tempNode = parent.getRight();
                if(height(tempNode.getLeft()) > height(tempNode.getRight())){       //RL类型
                    rightLeftRotate(parent);
                }else{      //RR类型
                    rightRightRotate(parent);
                }
            }
        }else if(val > parent.getValue()){  //右子树递归查找
            //删除以后返回替换的新节点
            AvlNodeInteger newRight = remove(parent.getRight(),val);
            parent.setRight(newRight);
            //检查是否平衡
            if(height(parent.getLeft()) - height(parent.getRight()) > 1){
                    AvlNodeInteger tempNode = parent.getLeft();
                    if(height(tempNode.getLeft()) > height(tempNode.getRight())){   //LL类型
                        leftLeftRotate(parent);
                    }else{             //LR类型
                        leftRightRotate(parent);
                    }
            }
        }else{   //相等,匹配成功
            if(null != parent.getLeft() && null != parent.getRight()){  //左右子节点都不为空
                //判断高度,高的一方,拿到最大(左),最小(右)的节点,作为替换节点。
                //删除原来匹配节点
                //左边更高,获取到左边最大的节点
                if(parent.getLeft().getHeight() > parent.getRight().getHeight()){
                    AvlNodeInteger leftMax = getMax(parent.getLeft());
                    parent.setLeft(remove(parent.getLeft(),leftMax.getValue()));
                    leftMax.setLeft(parent.getLeft());
                    leftMax.setRight(parent.getRight());
                    leftMax.setHeight(maxHeight(leftMax.getLeft(),leftMax.getRight()));
                    parent = leftMax;
                }else{                  //右边更高,获取到右边最小的节点
                    AvlNodeInteger rightMin = getMin(parent.getRight());
                    parent.setRight(remove(parent.getRight(),rightMin.getValue()));
                    rightMin.setLeft(parent.getLeft());
                    rightMin.setRight(parent.getRight());
                    rightMin.setHeight(maxHeight(parent.getLeft(),parent.getRight())+1);
                    parent = rightMin;
                }
            }else{
                //有任意一方节点为空,则不为空的那一方作为替换节点,删除原来的节点
                parent = null;
            }
        }

        return parent;
    }


    /***
     * 删除时用到,获取当前节点子节点最大值
     * @param currentRoot
     * @return
     */
    private AvlNodeInteger getMax(AvlNodeInteger currentRoot){
            if(currentRoot.getRight() != null){
                currentRoot = getMax(currentRoot.getRight());
            }
            return currentRoot;
    }

    /***
     * 删除时用到,获取当前节点子节点最小值
     * @param currentRoot
     * @return
     */
    private AvlNodeInteger getMin(AvlNodeInteger currentRoot){
            if(currentRoot.getLeft() != null){
                currentRoot = getMin(currentRoot.getLeft());
            }
            return currentRoot;
    }

以上就是难点插入和删除的实现了, 没有过多阐述,是因为大家如果真的理解了上面说明的理论, 那么应该没有问题来理解这些code。 当然有任何问题大家可以在评论区回复我 欢迎大家指正!

####4种遍历

  • 前序遍历 根左右
  • 中序遍历 左跟右
  • 后序遍历 左右根
  • 层级遍历 从root开始,一层层
 /***java
     * 前序遍历
     * 1-根节点
     * 2-左节点
     * 3-右节点
     * 根左右
     * @param parent
     */
    private void xianxu(AvlNodeInteger parent){
        System.out.println(parent.getValue());
        if(null != parent.getLeft()){
            xianxu(parent.getLeft());
        }
        if(null != parent.getRight()){
            xianxu(parent.getRight());
        }
    }

 /***
     * 中序遍历
     * 左节点
     * 根节点
     * 右节点
     * 
     * 左根右
     * @param parent
     */
    private void zhongxu(AvlNodeInteger parent){
        if(null != parent.getLeft()){
            zhongxu(parent.getLeft());
        }
        System.out.println(parent.getValue());

        if(null != parent.getRight()){
            zhongxu(parent.getRight());
        }
    }
	
	
    /***
     * 后续遍历
     * 左右根
     * 左节点
     * 右节点
     * 根节点
     */
    private void houxu(AvlNodeInteger parent){
        if(null != parent.getLeft()){
            houxu(parent.getLeft());
        }
        if(null != parent.getRight()){
            houxu(parent.getRight());
        }
        System.out.println(parent);
    }


    /***
     * 层级遍历
     * @param parent
     */
    private void cengji(List<AvlNodeInteger> parent){
        if(null == parent || parent.size() == 0) return;

        //打印当前层
        List<AvlNodeInteger> AvlNodeIntegers = new ArrayList<AvlNodeInteger>();
        int k = 0;
        for(int i = 0 ; i < parent.size() ; i++){
            AvlNodeInteger currentNode = parent.get(i);
            System.out.println(currentNode.getValue()+",");
            if(null != currentNode.getLeft()){
                AvlNodeIntegers.add(currentNode.getLeft());
                k++;
            }
            if(null != currentNode.getRight()){
                AvlNodeIntegers.add(currentNode.getRight());
                k++;
            }
        }
        System.out.println("--------------------------");
        cengji(AvlNodeIntegers);
    }

####完整源码:

package focus.zhishui.tree;

import java.util.ArrayList;
import java.util.List;

/**
 *
 * Created by Nero on 2018-09-11.
 */
public class AvlTreeInteger {
    /***
     * 遍历方式,
     * 1-前序遍历
     * 2-中序遍历
     * 3-后序遍历
     * 4-层级遍历
     */
    public static final int QIANXU = 1;
    public static final int ZHONGXU = 2;
    public static final int HOUXU = 3;
    public static final int CENGJI = 4;


    private AvlNodeInteger root;
    private int size;


    public AvlTreeInteger() {
    }
    public AvlTreeInteger(AvlNodeInteger root) {
        this.root = root;
    }

    private void initRoot(Integer val){
        AvlNodeInteger AvlNodeInteger = new AvlNodeInteger(val);
        this.root = AvlNodeInteger;
        System.out.println(this.root.getValue());
    }

    /****
     * 对外开放,插入操作
     * @param val
     * @throws Exception
     */
    public void insert(Integer val) throws Exception {
        if(null == root){
            initRoot(val);
            size++;
            return;
        }

        if(contains(val)) throw new Exception("The value is already exist!");

        insertNode(this.root,val);
        size++;
    }


    private AvlNodeInteger createSingleNode(Integer val){
        return new AvlNodeInteger(val);
    }

    /**
     * 递归插入
     * parent == null 到最底部插入前节点判断情况
     * @param parent
     * @param val
     * @return
     */
    private AvlNodeInteger insertNode(AvlNodeInteger parent,Integer val){
        if(parent == null){
           return createSingleNode(val);
        }
        if(val < parent.getValue()){    //插入判断,小于父节点,插入到右边
            //注意理解回溯,这里最终返回的是插入完成节点
            //每一层回溯,都会返回相应当时递归的节点!!!
            parent.setLeft(insertNode(parent.getLeft(),val));

            //判断平衡,不要在意这里的parent是谁,
            //这个parent肯定是递归层级上,回溯的一个节点!每一个节点都需要判断平衡
            if(height(parent.getLeft()) - height(parent.getRight()) > 1){
                Integer compareVal = (Integer) parent.getLeft().getValue();
                //左左旋转类型
                if(val < Integer.valueOf(compareVal)){
                    parent = leftLeftRotate(parent);
                }else{                  //左右旋转类型
                    parent = leftRightRotate(parent);
                }
            }
        }
        if(val > parent.getValue()){   //插入判断,小于父节点,插入到右边
            //注意理解回溯,这里最终返回的是插入完成节点
            //每一层回溯,都会返回相应当时递归的节点!!!
            parent.setRight(insertNode(parent.getRight(),val));

            //判断平衡,不要在意这里的parent是谁,
            //这个parent肯定是递归层级上,回溯的一个节点!每一个节点都需要判断平衡
            if(height(parent.getRight()) - height(parent.getLeft()) > 2){
                Integer compareVal = (Integer) parent.getLeft().getValue();
                if(val > compareVal){
                    parent = rightRightRotate(parent);
                }else{
                    parent = rightLeftRotate(parent);
                }
            }
        }

        parent.setHeight((maxHeight(parent.getLeft(),parent.getRight()))+1);
        return parent;
    }


    /***
     * 左左旋转模型
     * @param node  旋转之前的parent node 节点
     * @return  旋转之后的parent node节点
     */
    private AvlNodeInteger leftLeftRotate(AvlNodeInteger node){
        AvlNodeInteger newRoot = node.getLeft();
        node.setLeft(newRoot.getRight());
        newRoot.setRight(node);

        //由此node的高度降低了,newRoot的高度提高了。
         //newRoot的高度由node的高度而来
        node.setHeight(maxHeight(node.getLeft(),node.getRight())+1);
        newRoot.setHeight(maxHeight(newRoot.getLeft(),newRoot.getRight())+1);
        return newRoot;
    }


    /***
     * 右右旋转模型
     * @param node
     * @return
     */
    private AvlNodeInteger rightRightRotate(AvlNodeInteger node){
        AvlNodeInteger newRoot = node.getRight();
        node.setRight(newRoot.getLeft());
        newRoot.setLeft(node);

        //由此node的高度降低了,newRoot的高度提高了。
        //newRoot的高度由node的高度而来
        node.setHeight(maxHeight(node.getLeft(),node.getRight()));
        newRoot.setHeight(maxHeight(newRoot.getLeft(),newRoot.getRight()));
        return newRoot;
    }

    /**
     * 左右模型,先右右,再左左
     * @param node
     * @return
     */
    private AvlNodeInteger leftRightRotate(AvlNodeInteger node){
        //注意传递的参数
        node.setLeft(rightRightRotate(node.getLeft()));
        return leftLeftRotate(node);
    }

    /***
     * 右左模型,先左左,在右右
     * @param node
     * @return
     */
    private AvlNodeInteger rightLeftRotate(AvlNodeInteger node){
        node.setRight(leftLeftRotate(node.getRight()));
        return rightRightRotate(node);
    }




    /***
     * 求左右子节点最大高度
     * @param left
     * @param right
     * @return
     */
    private int maxHeight(AvlNodeInteger left,AvlNodeInteger right){
        return height(left) > height(right) ? height(left)  : height(right);
    }

    /***
     * 求一个节点的高度
     * @param t
     * @return
     */
    private int height(AvlNodeInteger t){
        return null == t ? 0 : t.getHeight();
    }


    
    public boolean contains(Integer val) {
        AvlNodeInteger curNode = root;
        if(null == curNode) return false;

        while(null != curNode){
            if(val > curNode.getValue()){
                curNode = curNode.getRight();
            }else if(val < curNode.getValue()){
                curNode = curNode.getLeft();
            }else{
                return true;
            }
        }
        return false;
    }





    
    public void remove(Integer val) {
        if(null == val || null == root){
            return;
        }
        if(!contains(val)){
            return;
        }
        remove(root,val);
    }


    /****
     * AVL删除,平衡树实现
     * @param parent
     * @param val
     * @return
     */
    private AvlNodeInteger remove(AvlNodeInteger parent,Integer val){
        if(val < parent.getValue()){        //左子树递归查询
            //删除以后返回替换的新节点
            AvlNodeInteger newLeft = remove(parent.getLeft(),val);
            parent.setLeft(newLeft);
            //检查是否平衡,删除的左边,那么用右边-左边
            if(height(parent.getRight()) - height(parent.getLeft()) > 1){
                AvlNodeInteger tempNode = parent.getRight();
                if(height(tempNode.getLeft()) > height(tempNode.getRight())){       //RL类型
                    rightLeftRotate(parent);
                }else{      //RR类型
                    rightRightRotate(parent);
                }
            }
        }else if(val > parent.getValue()){  //右子树递归查找
            //删除以后返回替换的新节点
            AvlNodeInteger newRight = remove(parent.getRight(),val);
            parent.setRight(newRight);
            //检查是否平衡
            if(height(parent.getLeft()) - height(parent.getRight()) > 1){
                    AvlNodeInteger tempNode = parent.getLeft();
                    if(height(tempNode.getLeft()) > height(tempNode.getRight())){   //LL类型
                        leftLeftRotate(parent);
                    }else{             //LR类型
                        leftRightRotate(parent);
                    }
            }
        }else{   //相等,匹配成功
            if(null != parent.getLeft() && null != parent.getRight()){  //左右子节点都不为空
                //判断高度,高的一方,拿到最大(左),最小(右)的节点,作为替换节点。
                //删除原来匹配节点
                //左边更高,获取到左边最大的节点
                if(parent.getLeft().getHeight() > parent.getRight().getHeight()){
                    AvlNodeInteger leftMax = getMax(parent.getLeft());
                    parent.setLeft(remove(parent.getLeft(),leftMax.getValue()));
                    leftMax.setLeft(parent.getLeft());
                    leftMax.setRight(parent.getRight());
                    leftMax.setHeight(maxHeight(leftMax.getLeft(),leftMax.getRight()));
                    parent = leftMax;
                }else{                  //右边更高,获取到右边最小的节点
                    AvlNodeInteger rightMin = getMin(parent.getRight());
                    parent.setRight(remove(parent.getRight(),rightMin.getValue()));
                    rightMin.setLeft(parent.getLeft());
                    rightMin.setRight(parent.getRight());
                    rightMin.setHeight(maxHeight(parent.getLeft(),parent.getRight())+1);
                    parent = rightMin;
                }
            }else{
                //有任意一方节点为空,则不为空的那一方作为替换节点,删除原来的节点
                parent = null;
            }
        }

        return parent;
    }


    /***
     * 删除时用到,获取当前节点子节点最大值
     * @param currentRoot
     * @return
     */
    private AvlNodeInteger getMax(AvlNodeInteger currentRoot){
            if(currentRoot.getRight() != null){
                currentRoot = getMax(currentRoot.getRight());
            }
            return currentRoot;
    }

    /***
     * 删除时用到,获取当前节点子节点最小值
     * @param currentRoot
     * @return
     */
    private AvlNodeInteger getMin(AvlNodeInteger currentRoot){
            if(currentRoot.getLeft() != null){
                currentRoot = getMin(currentRoot.getLeft());
            }
            return currentRoot;
    }



    
    public AvlNodeInteger findMax() {
        if(null == root) return null;

        AvlNodeInteger temp = root;
        while(null != temp.getRight()){
            temp = temp.getRight();
        }
        return temp;
    }

    
    public AvlNodeInteger findMin() {
        if(null == root) return null;
        AvlNodeInteger temp = root;
        while(null != temp.getLeft()){
            temp = temp.getLeft();
        }
        return temp;
    }

    
    public int getNodeSize() {
        return size;
    }

    
    public void printGraph(int style) {
        if(root == null){
            return;
        }

        if(style == 1){
            xianxu(root);
        }else if(style == 2){
            zhongxu(root);
        }else if(style == 3){
            houxu(root);
        }else if(style == 4){
            List a = new ArrayList<>();
            a.add(root);
            cengji(a);
        }
    }

    /***
     * 前序编译
     * 1-根节点
     * 2-左节点
     * 3-右节点
     * 根左右
     * @param parent
     */
    private void xianxu(AvlNodeInteger parent){
        System.out.println(parent.getValue());
        if(null != parent.getLeft()){
            xianxu(parent.getLeft());
        }
        if(null != parent.getRight()){
            xianxu(parent.getRight());
        }
    }

    /***
     * 中序遍历
     * 左节点
     * 根节点
     * 右节点
     *
     *
     * 左根右
     * @param parent
     */
    private void zhongxu(AvlNodeInteger parent){
        if(null != parent.getLeft()){
            zhongxu(parent.getLeft());
        }
        System.out.println(parent.getValue());

        if(null != parent.getRight()){
            zhongxu(parent.getRight());
        }
    }


    /***
     * 后续遍历
     * 左右根
     * 左节点
     * 右节点
     * 根节点
     */
    private void houxu(AvlNodeInteger parent){
        if(null != parent.getLeft()){
            houxu(parent.getLeft());
        }
        if(null != parent.getRight()){
            houxu(parent.getRight());
        }
        System.out.println(parent);
    }

    /***
     * 层级遍历
     * @param parent
     */
    private void cengji(List<AvlNodeInteger> parent){
        if(null == parent || parent.size() == 0) return;

        //打印当前层
        List<AvlNodeInteger> AvlNodeIntegers = new ArrayList<AvlNodeInteger>();
        int k = 0;
        for(int i = 0 ; i < parent.size() ; i++){
            AvlNodeInteger currentNode = parent.get(i);
            System.out.println(currentNode.getValue()+",");
            if(null != currentNode.getLeft()){
                AvlNodeIntegers.add(currentNode.getLeft());
                k++;
            }
            if(null != currentNode.getRight()){
                AvlNodeIntegers.add(currentNode.getRight());
                k++;
            }
        }
        System.out.println("--------------------------");
        cengji(AvlNodeIntegers);
    }



    public static class AvlNodeInteger{
        private Integer value;
        private Integer height;
        private AvlNodeInteger left;
        private AvlNodeInteger right;

        public AvlNodeInteger(int t){
            initNode(t,null,null,1);
        }

        public AvlNodeInteger(int t,AvlNodeInteger left,AvlNodeInteger right){
            initNode(t,left,right,null);
        }

        private void initNode(int t,AvlNodeInteger left,AvlNodeInteger right,Integer height){
            this.setValue(t);
            this.left = left;
            this.right = right;
            this.height = height;
        }

        public Integer getValue() {
            return value;
        }

        public void setValue(Integer value) {
            this.value = value;
        }

        public Integer getHeight() {
            return height;
        }

        public void setHeight(Integer height) {
            this.height = height;
        }

        public AvlNodeInteger getLeft() {
            return left;
        }

        public void setLeft(AvlNodeInteger left) {
            this.left = left;
        }

        public AvlNodeInteger getRight() {
            return right;
        }

        public void setRight(AvlNodeInteger right) {
            this.right = right;
        }
    }



}