天天看點
傳回

Java--算法--平衡二叉樹(AVL樹)

  1. 平衡二叉樹的基本介紹
  2. 平衡二叉排序樹的左旋轉與右旋轉：
  1. Java--算法--平衡二叉樹(AVL樹)
  2. Java--算法--平衡二叉樹(AVL樹)
  3. Java--算法--平衡二叉樹(AVL樹)
  4. Java--算法--平衡二叉樹(AVL樹)
package com.model.tree;

/**
 * @Description:測試類
 * @Author: 張紫韓
 * @Crete 2021/7/16 20:07
 * 示範平衡二叉排序樹的建立（AVL）
 */
public class TreeDemo09 {
    public static void main(String[] args) {
        int[] array={4,3,6,5,7,8};
        AVCTree avcTree = new AVCTree();//平衡二叉搜尋樹
        for (int i = 0; i < array.length; i++) {
            avcTree.add(new AVLNode(array[i]));
        }
        avcTree.infixOrder();
        avcTree.leftRotation();//左旋轉
        avcTree.rightRotation();//右旋轉
        System.out.println(avcTree.getHeight());
        System.out.println(avcTree.getLeftHeight());
        System.out.println(avcTree.getRightHeight());

        System.out.println("-------------------------");
        int[] array1={8,7,6,5,4,2,1};
        AVCTree avcTree1 = new AVCTree();
        for (int i = 0; i < array1.length; i++) {
            avcTree1.add(new AVLNode(array1[i]));
        }
        while (Math.abs(avcTree1.getLeftHeight()-avcTree1.getRightHeight())>1) {
            avcTree1.rightRotation();
            avcTree1.leftRotation();
        }

        System.out.println(avcTree1.getHeight());
        System.out.println(avcTree1.getLeftHeight());
        System.out.println(avcTree1.getRightHeight());



    }
}
class AVCTree{
    private AVLNode root;

//    右旋轉
    public void rightRotation(){
        if (root==null){
            return;
        }else {
            if (getLeftHeight()-getRightHeight()>1){
                root.rightRotation();
            }
        }
    }
    //左旋轉
    public void leftRotation(){
        if (root==null){
            return;
        }else {
            if (getRightHeight()-getLeftHeight()>1){
                root.leftRotation();
            }
        }
    }
//    中序周遊節點
    public void infixOrder(){
        if (root==null){
            System.out.println("樹為空，無法進行周遊");
            return;
        }else {
            root.infixOrder();
        }

    }
//    添加節點
    public void add(AVLNode node){
        if (root==null){
            root=node;
        }else {
            root.add(node);
        }
    }
//    獲得目前樹的高度
    public int getHeight(){
        if (root==null){
            return 0;
        }else {
            return root.getHeight();
        }
    }
    public int getLeftHeight(){
        if (root==null){
            return 0;
        }else {
            if (root.getLeft()==null){
                return 0;
            }else {
                return root.getLeft().getHeight();
            }
        }
    }
    public int getRightHeight(){
        if (root==null){
            return 0;
        }else {
            if (root.getRight()==null){
                return 0;
            }else {
                return root.getRight().getHeight();
            }
        }
    }
    public AVCTree(AVLNode root) {
        this.root = root;
    }

    public AVCTree() {
    }

    public AVLNode getRoot() {
        return root;
    }

    public void setRoot(AVLNode root) {
        this.root = root;
    }
}
class AVLNode{
    private int value;
    private AVLNode left;
    private AVLNode right;
//    右旋轉
    public void rightRotation(){
        AVLNode newRoot = new AVLNode(this.value);
        newRoot.right=this.right;
        newRoot.left=this.left.right;
        this.value=this.left.value;
        this.left=this.left.left;
        this.right=newRoot;

    }
//左旋轉
    public void leftRotation(){
        AVLNode newRoot = new AVLNode(this.value);
        newRoot.left=this.left;
        newRoot.right=this.right.left;
        this.value=this.right.value;
        this.right=this.right.right;
        this.left=newRoot;
    }
//    統計目前節點的高度
    public int getHeight(){
       return Math.max(this.left==null?1:this.left.getHeight()+1,this.right==null?1:this.right.getHeight()+1);
    }
    public void infixOrder(){
        if (this.left!=null){
            this.left.infixOrder();
        }
        System.out.println(this.toString());
        if (this.right!=null){
            this.right.infixOrder();
        }
    }
    public void add(AVLNode node){
        if (node==null){
         return;
        }else {
            if (this.value>node.value){
                if (this.left==null) {
                    this.left = node;
                }else {
                    this.left.add(node);
                }
            }else{
                if (this.right==null) {
                    this.right = node;
                }else {
                    this.right.add(node);
                }
            }
        }
    }
    @Override
    public String toString() {
        return "AVLNode{" +
                "value=" + value +
                '}';
    }

    public int getValue() {
        return value;
    }

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

    public AVLNode getLeft() {
        return left;
    }

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

    public AVLNode getRight() {
        return right;
    }

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

    public AVLNode(int value) {
        this.value = value;
    }
}
  1.  平衡二叉排序樹的雙旋轉：
  1. Java--算法--平衡二叉樹(AVL樹)
  2. Java--算法--平衡二叉樹(AVL樹)
  3. Java--算法--平衡二叉樹(AVL樹)
package com.model.tree;

/**
 * @Description:測試類
 * @Author: 張紫韓
 * @Crete 2021/7/16 20:07
 * 示範平衡二叉排序樹的建立（AVL）
 */
public class TreeDemo09 {
    public static void main(String[] args) {
        int[] array={4,3,6,5,7,8};
        AVCTree avcTree = new AVCTree();//平衡二叉搜尋樹
        for (int i = 0; i < array.length; i++) {
            avcTree.add(new AVLNode(array[i]));
        }
        avcTree.infixOrder();
        avcTree.leftRotation();//左旋轉
        avcTree.rightRotation();//右旋轉
        System.out.println(avcTree.getHeight());
        System.out.println(avcTree.getLeftHeight());
        System.out.println(avcTree.getRightHeight());

        System.out.println("-------------------------");
        int[] array1={8,7,6,5,4,2,1};
        AVCTree avcTree1 = new AVCTree();
        for (int i = 0; i < array1.length; i++) {
            avcTree1.add(new AVLNode(array1[i]));
        }
        while (Math.abs(avcTree1.getLeftHeight()-avcTree1.getRightHeight())>1) {
            avcTree1.rightRotation();
            avcTree1.leftRotation();
        }
        System.out.println(avcTree1.getHeight());
        System.out.println(avcTree1.getLeftHeight());
        System.out.println(avcTree1.getRightHeight());
        System.out.println("----------------------");
        AVCTree tree = new AVCTree();
        tree.add(new AVLNode(10));
        tree.add(new AVLNode(11));
        tree.add(new AVLNode(7));
        tree.add(new AVLNode(6));
        tree.add(new AVLNode(8));
        tree.add(new AVLNode(9));
        tree.rightRotation();
        System.out.println(tree.getLeftHeight());
        System.out.println(tree.getRightHeight());
        System.out.println(tree.getHeight());
        System.out.println(tree.getRoot());
        tree.infixOrder();


    }
}
class AVCTree{
    private AVLNode root;

//    右旋轉
    public void rightRotation(){
        if (root==null){
            return;
        }else {
            if (getLeftHeight()-getRightHeight()>1){
//                檢查是否需要進行雙旋轉
                if (root.getLeft()!=null){
                    if (root.getLeft().getRight()!=null&&root.getLeft().getLeft()!=null){
                        if (root.getLeft().getRight().getHeight()>root.getLeft().getLeft().getHeight()){
                            root.getLeft().leftRotation();
                        }
                    }
                }
                root.rightRotation();
            }
        }
    }
    //左旋轉
    public void leftRotation(){
        if (root==null){
            return;
        }else {
            if (getRightHeight()-getLeftHeight()>1){
                //                檢查是否需要進行雙旋轉
                if (root.getRight()!=null){
                    if (root.getRight().getLeft()!=null&&root.getRight().getRight()!=null){
                        if (root.getRight().getLeft().getHeight()>root.getRight().getRight().getHeight()){
                            root.getRight().rightRotation();
                        }
                    }
                }
                root.leftRotation();
            }
        }
    }
//    中序周遊節點
    public void infixOrder(){
        if (root==null){
            System.out.println("樹為空，無法進行周遊");
            return;
        }else {
            root.infixOrder();
        }

    }
//    添加節點
    public void add(AVLNode node){
        if (root==null){
            root=node;
        }else {
            root.add(node);
        }
    }
//    獲得目前樹的高度
    public int getHeight(){
        if (root==null){
            return 0;
        }else {
            return root.getHeight();
        }
    }
    public int getLeftHeight(){
        if (root==null){
            return 0;
        }else {
            if (root.getLeft()==null){
                return 0;
            }else {
                return root.getLeft().getHeight();
            }
        }
    }
    public int getRightHeight(){
        if (root==null){
            return 0;
        }else {
            if (root.getRight()==null){
                return 0;
            }else {
                return root.getRight().getHeight();
            }
        }
    }
    public AVCTree(AVLNode root) {
        this.root = root;
    }

    public AVCTree() {
    }

    public AVLNode getRoot() {
        return root;
    }

    public void setRoot(AVLNode root) {
        this.root = root;
    }
}
class AVLNode{
    private int value;
    private AVLNode left;
    private AVLNode right;
//    右旋轉
    public void rightRotation(){
        AVLNode newRoot = new AVLNode(this.value);
        newRoot.right=this.right;
        newRoot.left=this.left.right;
        this.value=this.left.value;
        this.left=this.left.left;
        this.right=newRoot;

    }
//左旋轉
    public void leftRotation(){
        AVLNode newRoot = new AVLNode(this.value);
        newRoot.left=this.left;
        newRoot.right=this.right.left;
        this.value=this.right.value;
        this.right=this.right.right;
        this.left=newRoot;
    }
//    統計目前節點的高度
    public int getHeight(){
       return Math.max(this.left==null?1:this.left.getHeight()+1,this.right==null?1:this.right.getHeight()+1);
    }
    public void infixOrder(){
        if (this.left!=null){
            this.left.infixOrder();
        }
        System.out.println(this.toString());
        if (this.right!=null){
            this.right.infixOrder();
        }
    }
    public void add(AVLNode node){
        if (node==null){
         return;
        }else {
            if (this.value>node.value){
                if (this.left==null) {
                    this.left = node;
                }else {
                    this.left.add(node);
                }
            }else{
                if (this.right==null) {
                    this.right = node;
                }else {
                    this.right.add(node);
                }
            }
        }
    }
    @Override
    public String toString() {
        return "AVLNode{" +
                "value=" + value +
                '}';
    }

    public int getValue() {
        return value;
    }

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

    public AVLNode getLeft() {
        return left;
    }

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

    public AVLNode getRight() {
        return right;
    }

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

    public AVLNode(int value) {
        this.value = value;
    }
}
  1.  　 
i++ 二叉排序樹 中序周遊 添加節點 ide
上一篇: Java 平衡二叉樹和AVL
下一篇: UITableview delegate dataSource調用探究

繼續閱讀