devbox
IT小白
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

平衡二叉树(java)_java实现平衡二叉树

作者：IT小白 | 2024-05-27 13:01:00

赞

踩

java实现平衡二叉树

一、基本概念

平衡二叉树也叫平衡二叉搜索树 (Self-balancingbinarysearch tree) 又被称为AVL树，可以保证查询效率较高。

具有以下特点:它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1.并且左右两个子树都是一棵平衡二叉树。

二、原理图

左旋转示意

 有旋转示意

 需要双旋转(根节点左子树进行左旋转后，根节点进行右旋转，反之亦然)

 三、代码

  1. /**
  2.  * 创建节点
  3.  */
  4. public class Node {
  5.     int value;
  6.  
  7.     Node left;
  8.  
  9.     Node right;
  10.  
  11.     public Node(int value) {
  12.         this.value = value;
  13.     }
  14.  
  15.     /**
  16.      * 左旋转
  17.      */
  18.     private void leftRotate() {
  19.         //    创建新的节点，以当前根节点的值
  20.         Node newNode = new Node(value);
  21.         //    把新的节点的左子树，设置成为当前节点的左子树
  22.         newNode.left = left;
  23.         //    把新的节点的右子树设置成，复制节点的右子树的左子树
  24.         newNode.right = right.left;
  25.         //    把当前节点的值替换成右子节点的值
  26.         value = right.value;
  27.         //    把当前节点的右子树，设置为右子树的右子树
  28.         right = right.right;
  29.         //    吧当前节点的左子树设置新的节点
  30.         left = newNode;
  31.     }
  32.  
  33.     /**
  34.      * 有旋转
  35.      */
  36.     private void rightRotate() {
  37.         Node newNode = new Node(value);
  38.         newNode.right = right;
  39.         newNode.left = left.right;
  40.         value = left.value;
  41.         left = left.left;
  42.         right = newNode;
  43.     }
  44.  
  45.     /**
  46.      * 返回左子树的高度
  47.      *
  48.      * @return
  49.      */
  50.     public int leftHeight() {
  51.         if (left != null) {
  52.             return left.height();
  53.         } else {
  54.             return 0;
  55.         }
  56.     }
  57.  
  58.     /**
  59.      * 返回右子树的高度
  60.      *
  61.      * @return
  62.      */
  63.     public int rightHeight() {
  64.         if (right == null) {
  65.             return 0;
  66.         }
  67.         return right.height();
  68.     }
  69.  
  70.     /**
  71.      * 返回当前节点的高度
  72.      *
  73.      * @return
  74.      */
  75.     public int height() {
  76.         return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
  77.     }
  78.  
  79.     /**
  80.      * 添加节点
  81.      *
  82.      * @param node
  83.      */
  84.     public void add(Node node) {
  85.         if (node == null) {
  86.             return;
  87.         }
  88.         //    判断传入节点的值，和当前子树根节点的关系
  89.         if (node.value < this.value) {
  90.             if (this.left != null) {
  91.                 //左子树递归
  92.                 this.left.add(node);
  93.             } else {
  94.                 this.left = node;
  95.             }
  96.         } else {
  97.             if (this.right != null) {
  98.                 //右子树递归
  99.                 this.right.add(node);
  100.             } else {
  101.                 this.right = node;
  102.             }
  103.         }
  104.         //    当添加完一个节点后,右子树高度-左子树高度>1
  105.         if (rightHeight() - leftHeight() > 1) {
  106.             //当右子树的左子树高度大于它的右子树的高度
  107.             if(right!=null&&right.leftHeight()>right.rightHeight()){
  108.                 right.rightRotate();
  109.             }
  110.             leftRotate();
  111.             return;
  112.         }
  113.         //左子树高度>右子树高度
  114.         if (leftHeight() - rightHeight() > 1) {
  115.             //当左子树的右子树高度大于它的左子树高度
  116.             if(left!=null&&left.rightHeight()>left.leftHeight()){
  117.                 left.leftRotate();
  118.             }
  119.             rightRotate();
  120.         }
  121.     }
  122.  
  123.     /**
  124.      * 查找要删除的节点的值
  125.      *
  126.      * @param value 希望删除的值
  127.      * @return 返回该节点，默认返回null
  128.      */
  129.     public Node search(int value) {
  130.         if (value == this.value) {
  131.             return this;
  132.         } else if (value < this.value) {
  133.             //查找的值小于当前节点的值
  134.             if (this.left == null) {
  135.                 return null;
  136.             }
  137.             return this.left.search(value);
  138.         } else {
  139.             //查找的值大于当前节点的值
  140.             if (this.right == null) {
  141.                 return null;
  142.             }
  143.             return this.right.search(value);
  144.         }
  145.     }
  146.  
  147.     /**
  148.      * 查找要删除的父节点
  149.      *
  150.      * @param value
  151.      * @return
  152.      */
  153.     public Node searchParent(int value) {
  154.         //    如果当前节点就是要删除的节点的父节点，直接返回
  155.         if ((this.right != null && this.right.value == value) ||
  156.                 (this.left != null && this.left.value == value)) {
  157.             return this;
  158.         } else {
  159.             // 向左子树递归
  160.             if (value < this.value && this.left != null) {
  161.                 return this.left.searchParent(value);
  162.             } else if (value >= this.value && this.right != null) {
  163.                 //向右子树递归
  164.                 return this.right.searchParent(value);
  165.             } else {
  166.                 return null;
  167.             }
  168.         }
  169.     }
  170.  
  171.     /**
  172.      * 中序遍历
  173.      */
  174.     public void infixOrder() {
  175.         if (this.left != null) {
  176.             this.left.infixOrder();
  177.         }
  178.         System.out.println(this);
  179.         if (this.right != null) {
  180.             this.right.infixOrder();
  181.         }
  182.     }
  183.  
  184.     @Override
  185.     public String toString() {
  186.         return "Node{" +
  187.                 "value=" + value +
  188.                 '}';
  189.     }
  190. }
  1. public class AVLTree {
  2.     private Node root;
  3.  
  4.     public void delNode(int value) {
  5.         if (root == null) {
  6.             return;
  7.         }
  8.         //    查找要删除的节点
  9.         Node targetNode = search(value);
  10.         //    如果没有找到要删除的节点
  11.         if (targetNode == null) {
  12.             return;
  13.         }        //二叉树只有一个节点，切删除的为此节点
  14.         if (root.left == null && root.right == null) {
  15.             root = null;
  16.             return;
  17.         }
  18.         //查找父节点
  19.         Node parentNode = searchParent(value);
  20.         //    如果删除的是叶子节点
  21.         if (targetNode.left == null && targetNode.right == null) {
  22.             //    如果是父节点的左子节点
  23.             if (parentNode.left != null && parentNode.left.value == value) {
  24.                 parentNode.left = null;
  25.             } else if (parentNode.right != null && parentNode.right.value == value) {
  26.                 // 如果是父节点的右子节点
  27.                 parentNode.right = null;
  28.             }
  29.         } else if (targetNode.left != null && targetNode.right != null) {
  30.             //    删除节点有左右两个子树(删除当前节点右节点的最小值，或者当前节点左节点的最大值)
  31.             int minVal = delRightTreeMin(targetNode.right);
  32.             targetNode.value = minVal;
  33.  
  34.         } else {
  35.             //    只有一颗子树的节点
  36.             //    如果要删除的节点有左子节点
  37.             if (targetNode.left != null) {
  38.                 //    如果targetNode是parent的左子节点
  39.                 if (parentNode != null) {
  40.                     if (parentNode.left.value == value) {
  41.                         parentNode.left = targetNode.left;
  42.                     } else {
  43.                         parentNode.right = targetNode.left;
  44.                     }
  45.                 } else {
  46.                     root = targetNode.left;
  47.                 }
  48.  
  49.             } else {
  50.                 //    如果删除的节点有右子节点
  51.                 if (parentNode != null) {
  52.                     if (parentNode.left.value == value) {
  53.                         parentNode.left = targetNode.right;
  54.                     } else {
  55.                         parentNode.right = targetNode.right;
  56.                     }
  57.                 } else {
  58.                     root = targetNode.right;
  59.                 }
  60.  
  61.             }
  62.  
  63.         }
  64.     }
  65.  
  66.     /**
  67.      * 返回以node根节点的二叉排序树的最小节点的值
  68.      * 删除最小节点，返回最小节点的值
  69.      *
  70.      * @param node
  71.      * @return
  72.      */
  73.     public int delRightTreeMin(Node node) {
  74.         Node target = node;
  75.         //    循环找到左子节点，找到最小值
  76.         while (target.left != null) {
  77.             target = target.left;
  78.         }
  79.         //    删除最小节点
  80.         delNode(target.value);
  81.         return target.value;
  82.     }
  83.  
  84.     /**
  85.      * 查找要删除的节点
  86.      *
  87.      * @param value
  88.      * @return
  89.      */
  90.     public Node search(int value) {
  91.         if (root == null) {
  92.             return null;
  93.         } else {
  94.             return root.search(value);
  95.         }
  96.     }
  97.  
  98.     /**
  99.      * 查找父节点
  100.      *
  101.      * @param value
  102.      * @return
  103.      */
  104.     public Node searchParent(int value) {
  105.         if (root == null) {
  106.             return null;
  107.         } else {
  108.             return root.searchParent(value);
  109.         }
  110.     }
  111.  
  112.     /**
  113.      * 添加节点方法
  114.      *
  115.      * @param node 新节点
  116.      */
  117.     public void add(Node node) {
  118.         if (root == null) {
  119.             root = node;
  120.         } else {
  121.             root.add(node);
  122.         }
  123.     }
  124.  
  125.     /**
  126.      * 创建二叉排序树
  127.      */
  128.     public void infixOrder() {
  129.         System.out.println("中序遍历二叉排序树");
  130.         if (root == null) {
  131.             System.out.println("节点为空");
  132.         } else {
  133.             root.infixOrder();
  134.         }
  135.     }
  136.  
  137.     public Node getRoot() {
  138.         return root;
  139.     }
  140. }
  141.

四、测试 

  1. public class AVLTreeDemo {
  2.     public static void main(String[] args) {
  3.         //int[] arr = {4, 3, 6, 5, 7, 8};
  4.         //int[] arr = {10,12,8,9,7,6};
  5.         int[] arr = {10,11,7,6,8,9};
  6.         //创建一个AVLTree对象
  7.         AVLTree avlTree = new AVLTree();
  8.         //    添加节点
  9.         for (int i = 0; i < arr.length; i++) {
  10.             avlTree.add(new Node(arr[i]));
  11.         }
  12.         //    遍历
  13.         avlTree.infixOrder();
  14.         System.out.println("树的高度；" + avlTree.getRoot().height());
  15.         System.out.println("左子树的高度；" + avlTree.getRoot().leftHeight());
  16.         System.out.println("右子树的高度；" + avlTree.getRoot().rightHeight());
  17.  
  18.     }
  19. }
  1. 中序遍历二叉排序树
  2. Node{value=6}
  3. Node{value=7}
  4. Node{value=8}
  5. Node{value=9}
  6. Node{value=10}
  7. Node{value=11}
  8. 树的高度；3
  9. 左子树的高度；2
  10. 右子树的高度；2

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/632105
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号