数据结构与算法之平衡二叉树的构建和遍历

男娘i 2023-07-13 13:46 6阅读 0赞

**定义：**  
***平衡二叉树（Balanced Binary Tree）具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。***

**产生原因：**  
***如果待添加节点的值是有顺序的如\{1，3，5，8，9，13\}按照排序二叉树就会排列成如下图所示，这样它更像链表，添加效率高，遍历效率低，因为每次还要判断左节点是否为空，所以遍历效率比链表都要低所以产生了平衡二叉树又叫AVL树，它是一种平衡的排序二叉树；***

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpbjEyMTQwMDA5OTk_size_16_color_FFFFFF_t_70]

**构建方发：**  
***先按照生成二叉排序树的方法构造二叉树，直至二叉树变得不平衡，即出现这样的节点：左子树与右子树的高度差大于1。至于如何调整，要看插入的导致二叉树不平衡的节点的位置。主要有四种调整方式：LL（左旋）、RR（右旋）、LR（先左旋再右旋）、RL（先右旋再左旋）。***

**java代码实现**

package com.yg.tree.avlTree;/*
    @author  Mu_Mu
    @date    2020/3/11  14:22
    */
    
    import java.sql.SQLOutput;
    
    public class AvlTreeDemo {
        public static void main(String[] args) {
        int []arr={2,1,6,5,7,3};
        AvlTree avlTree=new AvlTree();
            for (int i = 0; i < arr.length; i++) {
                avlTree.add(new Node(arr[i]));
            }
    
            //遍历
            avlTree.infixOrder();
            System.out.println("树的高度："+avlTree.getRoot().getHeight());
            System.out.println("树的左子树高度："+avlTree.getRoot().getLeftHeight());
            System.out.println("树的右子树高度："+avlTree.getRoot().getRightHeight());
        }
    }
    
    class AvlTree {
        private Node root;
    
        public Node getRoot() {
            return root;
        }
    
        public void infixOrder() {
            if (root == null) {
                return;
            }
            root.infixOreder();
        }
    
        public void add(Node node) {
            if (root == null) {
                root = node;
            } else {
                root.add(node);
            }
    
        }
    }
    
    class Node {
        int value;
        Node left;
        Node right;
    
        public Node(int value) {
            this.value = value;
        }
    
        //中序遍历
        public void infixOreder() {
            if (this.left != null) {
                this.left.infixOreder();
            }
            System.out.println(this);
            if (this.right != null) {
                this.right.infixOreder();
            }
        }
    
        //添加节点
        public void add(Node node) {
            if (node == null) {
                return;
            }
            if (node.value < this.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);
    
                }
    
            }
            //构建平衡排序二叉树
            if (getRightHeight() - getLeftHeight() > 1) {//如果右边长度-左边长度大于1则需要左旋转
                //如果右子树的左子树大于右子树的右子树
                if (right != null && right.getLeftHeight() > right.getRightHeight()) {
                    right.rightRotate();
                }
                    leftRotate();
                return;
            }
            if (getLeftHeight() - getRightHeight() > 1) {//如果左边长度-右边长度大于1则需要右旋转
                //如果左子树的右子树大于左子树的左子树
                if (left!=null && left.getRightHeight()>left.getLeftHeight()) {
                    left.leftRotate();
                }
                rightRotate();
            }
        }
    
        //获取传入子树的长度
        public int getHeight() {
            return Math.max(left == null ? 0 : left.getHeight(), right == null ? 0 : right.getHeight()) + 1;
        }
    
        //获取左子树的长度
        public int getLeftHeight() {
            if (left == null) {
                return 0;
            }
            return left.getHeight();
        }
    
        //获取右子树的长度
        public int getRightHeight() {
            if (right == null) {
                return 0;
            }
            return right.getHeight();
        }
    
        //左旋转
        public void leftRotate() {
            //1.以当前节点的值创建一个新的节点
            Node Newnode = new Node(this.value);
            //2.新节点的左节点指向当前节点的左节点
            Newnode.left = this.left;
            //3.新节点的右节点指向当前节点的左节点
            Newnode.right = this.right.left;
            //4.当前节点的值变为右节点的值
            this.value = this.right.value;
            //5.当前节点的左节点指向新节点
            this.left = Newnode;
            //6.当前节点的右节点指向当前节点右节点的右节点
            this.right = this.right.right;
        }
    
        //右旋转
        public void rightRotate() {
            //1.以当前节点的值创建一个新的节点
            Node Newnode = new Node(this.value);
            //2.新节点的左节点指向当前节点的左节点的右节点
            Newnode.left = this.left.right;
            //3.新节点的右节点指向当前节点的右节点
            Newnode.right = this.right;
            //4.当前节点的值变为当前节点左节点的值
            this.value = this.left.value;
            //5.当前节点的右节点指向新节点
            this.right = Newnode;
            //6.当前节点的左节点指向当前节点左节点的左节点
            this.left = this.left.left;
        }
    
        @Override
        public String toString() {
            return "Node{" +
                    "value=" + value +
                    '}';
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpbjEyMTQwMDA5OTk_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200312154659192.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpbjEyMTQwMDA5OTk=,size_16,color_FFFFFF,t_70