数据结构-平衡二叉树Java实现

1,Node.java

package com.cnblogs.mufasa.BalanceBinaryTree;

public class Node {
    Node parent;
    Node leftChild;
    Node rightChild;
    int val;
    public Node(Node parent, Node leftChild, Node rightChild,int val) {
        super();
        this.parent = parent;
        this.leftChild = leftChild;
        this.rightChild = rightChild;
        this.val = val;
    }

    public Node(int val){
        this(null,null,null,val);
    }

    public Node(Node node,int val){
        this(node,null,null,val);
    }
}

 

 

图1 Node.java结构图

 

2,BalanceBinaryTree.java

package com.cnblogs.mufasa.BalanceBinaryTree;

import java.util.LinkedList;
import java.util.Queue;

public class BalanceBinaryTree {
    private final static int LEFT=0;
    private final static int RIGHT=1;
    private Node root;
    private int size;
    public BalanceBinaryTree(){
        super();
    }

    //LL型非平衡树，右旋转
    public Node rightRotation(Node node){
        System.out.println(node.val+"右旋");
        if(node != null){
            Node leftChild = node.leftChild;// 用变量存储node节点的左子节点
            node.leftChild = leftChild.rightChild;// 将leftChild节点的右子节点赋值给node节点的左节点
            if(leftChild.rightChild != null){// 如果leftChild的右节点存在，则需将该右节点的父节点指给node节点
                leftChild.rightChild.parent = node;
            }
            leftChild.parent = node.parent;
            if(node.parent == null){// 即表明node节点为根节点
                this.root = leftChild;
            }else if(node.parent.rightChild == node){// 即node节点在它原父节点的右子树中
                node.parent.rightChild = leftChild;
            }else if(node.parent.leftChild == node){
                node.parent.leftChild = leftChild;
            }
            leftChild.rightChild = node;
            node.parent = leftChild;
            return leftChild;
        }
        return null;
    }

    //RR型非平衡树，左旋
    public Node leftRotation(Node node){
        System.out.println(node.val+"左旋");
        if(node != null){
            Node rightChild = node.rightChild;
            node.rightChild = rightChild.leftChild;
            if(rightChild.leftChild != null){
                rightChild.leftChild.parent = node;
            }
            rightChild.parent = node.parent;
            if(node.parent == null){
                this.root = rightChild;
            }else if(node.parent.rightChild == node){
                node.parent.rightChild = rightChild;
            }else if(node.parent.leftChild == node){
                node.parent.leftChild = rightChild;
            }
            rightChild.leftChild = node;
            node.parent = rightChild;

        }
        return null;
    }

    //添加新元素
    public boolean put(int val){
        return putVal(root,val);
    }
    private boolean putVal(Node node,int val){
        if(node == null){// 初始化根节点
            node = new Node(val);
            root = node;
            size++;
            return true;
        }
        Node temp = node;
        Node p;
        int t;
        /**
         * 通过do while循环迭代获取最佳节点，
         */
        do{
            p = temp;
            t = temp.val-val;
            if(t > 0){
                temp = temp.leftChild;
            }else if(t < 0){
                temp = temp.rightChild;
            }else{
                temp.val = val;//插入数值有相同数据，不符合要求
                return false;
            }
        }while(temp != null);

        Node newNode = new Node(p, val);
        if(t > 0){
            p.leftChild = newNode;
        }else if(t < 0){
            p.rightChild = newNode;
        }
        rebuild(p);// 使二叉树平衡的方法，优化平衡
        size++;
        return true;
    }

    //平衡二叉树优化节点
    private void rebuild(Node p){
        while(p != null){
            if(calcNodeBalanceValue(p) == 2){// 说明左子树高，需要右旋或者 先左旋后右旋
                fixAfterInsertion(p,LEFT);// 调整操作
            }else if(calcNodeBalanceValue(p) == -2){// 说明右子树高
                fixAfterInsertion(p,RIGHT);
            }
            p = p.parent;
        }
    }

    //计算二叉树平衡因子①
    private int calcNodeBalanceValue(Node node){
        if(node != null){
            return getHeightByNode(node);
        }
        return 0;
    }

    //计算二叉树平衡因子②
    public int getHeightByNode(Node node){
        if(node == null){//多余
            return 0;
        }
        return getChildDepth(node.leftChild)-getChildDepth(node.rightChild);
    }

    // 计算node节点的高度，递归调用
    public int getChildDepth(Node node){
        if(node == null){
            return 0;
        }
        return 1+Math.max(getChildDepth(node.leftChild),getChildDepth(node.rightChild));
    }

    /**
     * 调整树结构，先后顺序需要换一下，先判断LR型和RL型进行二次旋转
     * @param p
     * @param type
     */
    private void fixAfterInsertion(Node p, int type) {
        if(type == 0){//需要右旋或者 先左旋后右旋
            final Node leftChild = p.leftChild;
            if(leftChild.rightChild != null){// 先左旋后右旋
                leftRotation(leftChild);
                rightRotation(p);
            }else if(leftChild.leftChild != null){//右旋
                rightRotation(p);
            }

        }else{
            final Node rightChild = p.rightChild;
            if(rightChild.leftChild != null){// 先右旋，后左旋
                rightRotation(p);
                leftRotation(rightChild);
            }else if(rightChild.rightChild != null){// 左旋
                leftRotation(p);
            }
        }
    }

    //删除元素
    public boolean delete(int val){
        Node node = getNode(val);//搜索这个节点的数值
        if(node == null){
            return false;
        }
        boolean flag = false;
        Node p = null;
        Node parent = node.parent;
        Node leftChild = node.leftChild;
        Node rightChild = node.rightChild;
        //以下所有父节点为空的情况，则表明删除的节点是根节点
        if(leftChild == null && rightChild == null){//没有子节点
            if(parent != null){
                if(parent.leftChild == node){
                    parent.leftChild = null;
                }else if(parent.rightChild == node){
                    parent.rightChild = null;
                }
            }else{//不存在父节点，则表明删除节点为根节点
                root = null;
            }
            p = parent;
            node = null;
            flag =  true;
        }else if(leftChild == null && rightChild != null){// 只有右节点
            if(parent != null && parent.val > val){// 存在父节点，且node位置为父节点的左边
                parent.leftChild = rightChild;
            }else if(parent != null && parent.val < val){// 存在父节点，且node位置为父节点的右边
                parent.rightChild = rightChild;
            }else{
                root = rightChild;
            }
            p = parent;
            node = null;
            flag =  true;
        }else if(leftChild != null && rightChild == null){// 只有左节点
            if(parent != null && parent.val > val){// 存在父节点，且node位置为父节点的左边
                parent.leftChild = leftChild;
            }else if(parent != null && parent.val < val){// 存在父节点，且node位置为父节点的右边
                parent.rightChild = leftChild;
            }else{
                root = leftChild;
            }
            p = parent;
            flag =  true;
        }else if(leftChild != null && rightChild != null){// 两个子节点都存在
            Node successor = getSuccessor(node);// 这种情况，一定存在后继节点
            int temp = successor.val;
            boolean delete = delete(temp);
            if(delete){
                node.val = temp;
            }
            p = successor;
            successor = null;
            flag =  true;
        }
        if(flag){
            rebuild(p);
        }
        return flag;
    }

    /**
     * 搜索节点
     * @param val
     * @return
     */
    public Node getNode(int val){
        Node temp = root;
        int t;
        do{//直接使用循环遍历的方法
            t = temp.val-val;
            if(t > 0){
                temp = temp.leftChild;
            }else if(t < 0){
                temp = temp.rightChild;
            }else{
                return temp;
            }
        }while(temp != null);
        return null;
    }

    //获取后继节点
    private Node getSuccessor(Node node){
        if(node.rightChild != null){
            Node rightChild = node.rightChild;
            while(rightChild.leftChild != null){
                rightChild = rightChild.leftChild;
            }
            return rightChild;
        }
        Node parent = node.parent;
        while(parent != null && (node == parent.rightChild)){
            node = parent;
            parent = parent.parent;
        }
        return parent;
    }

    /**
     * 平衡二叉树节点遍历
     * @param type  0前序，1中序，2后续，3层序
     */
    public void print(int type){
        if(type==0){//前序
            printPre(root);
        }else if(type==1){
            printMid(root);
        }else if(type==2){
            printEnd(root);
        }else if(type==3){
            printLevel(root);
        }
    }

    //前序遍历
    private void printPre(Node root){
        if(root != null){
            System.out.println(root.val);// 位置在中间，则中序，若在前面，则为先序，否则为后续
            printPre(root.leftChild);
            printPre(root.rightChild);
        }
    }

    //中序遍历
    private void printMid(Node root){
        if(root != null){
            printMid(root.leftChild);
            System.out.println(root.val);// 位置在中间，则中序，若在前面，则为先序，否则为后续
            printMid(root.rightChild);
        }
    }

    //后序遍历
    private void printEnd(Node root){
        if(root != null){
            printEnd(root.leftChild);
            printEnd(root.rightChild);
            System.out.println(root.val);// 位置在中间，则中序，若在前面，则为先序，否则为后续
        }
    }

    //层次遍历
    private void printLevel(Node root){
        if(root == null){
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        Node temp = null;
        queue.add(root);
        while(!queue.isEmpty()){
            temp = queue.poll();
            System.out.print("节点值："+temp.val+",平衡值:"+calcNodeBalanceValue(temp)+"\n");
            if(temp.leftChild != null){
                queue.add(temp.leftChild);
            }
            if(temp.rightChild != null){
                queue.add(temp.rightChild);
            }
        }
    }
}

 

图2，BalanceBinaryTree.java结构图

 

3,JavaDemo.java

package com.cnblogs.mufasa.BalanceBinaryTree;

public class JavaDemo {
    public static void main(String[] args) {
        BalanceBinaryTree bbt=new BalanceBinaryTree();
//        bbt.put(10);
//        bbt.put(9);
//        bbt.put(11);
//        bbt.put(7);
//        bbt.put(12);
//        bbt.put(8);
//        bbt.put(38);
//        bbt.put(24);
//        bbt.put(17);
//        bbt.put(4);
//        bbt.put(3);

        bbt.put(11);
        bbt.put(7);
        bbt.put(15);
        bbt.put(4);
        bbt.put(9);
        bbt.put(10);
        bbt.print(3);
    }
}

 

4，特别鸣谢

https://www.cnblogs.com/qm-article/p/9349681.html