zcq

    1. package com.atguigu.avl;
    5. public class AVLTreeDemo {
    7.     public static void main(String[] args) {
    8.         //int[] arr = {4,3,6,5,7,8};
    9.         //int[] arr = { 10, 12, 8, 9, 7, 6 };
    10.         int[] arr = { 10, 11, 7, 6, 8, 9 };  
    11.         //创建一个 AVLTree对象
    12.         AVLTree avlTree = new AVLTree();
    13.         //添加结点
    14.         for(int i=0; i < arr.length; i++) {
    15.             avlTree.add(new Node(arr[i]));
    16.         }
    18.         //遍历
    19.         System.out.println("中序遍历");
    20.         avlTree.infixOrder();
    22.         System.out.println("在平衡处理~~");
    23.         System.out.println("树的高度=" + avlTree.getRoot().height()); //3
    24.         System.out.println("树的左子树高度=" + avlTree.getRoot().leftHeight()); // 2
    25.         System.out.println("树的右子树高度=" + avlTree.getRoot().rightHeight()); // 2
    26.         System.out.println("当前的根结点=" + avlTree.getRoot());//8
    29.     }
    31. }
    33. // 创建AVLTree
    34. class AVLTree {
    35.     private Node root;
    37.     public Node getRoot() {
    38.         return root;
    39.     }
    41.     // 查找要删除的结点
    42.     public Node search(int value) {
    43.         if (root == null) {
    44.             return null;
    45.         } else {
    46.             return root.search(value);
    47.         }
    48.     }
    50.     // 查找父结点
    51.     public Node searchParent(int value) {
    52.         if (root == null) {
    53.             return null;
    54.         } else {
    55.             return root.searchParent(value);
    56.         }
    57.     }
    59.     // 编写方法:
    60.     // 1. 返回的 以node 为根结点的二叉排序树的最小结点的值
    61.     // 2. 删除node 为根结点的二叉排序树的最小结点
    62.     /**
    63.      * 
    64.      * @param node
    65.      *            传入的结点(当做二叉排序树的根结点)
    66.      * @return 返回的 以node 为根结点的二叉排序树的最小结点的值
    67.      */
    68.     public int delRightTreeMin(Node node) {
    69.         Node target = node;
    70.         // 循环的查找左子节点，就会找到最小值
    71.         while (target.left != null) {
    72.             target = target.left;
    73.         }
    74.         // 这时 target就指向了最小结点
    75.         // 删除最小结点
    76.         delNode(target.value);
    77.         return target.value;
    78.     }
    80.     // 删除结点
    81.     public void delNode(int value) {
    82.         if (root == null) {
    83.             return;
    84.         } else {
    85.             // 1.需求先去找到要删除的结点 targetNode
    86.             Node targetNode = search(value);
    87.             // 如果没有找到要删除的结点
    88.             if (targetNode == null) {
    89.                 return;
    90.             }
    91.             // 如果我们发现当前这颗二叉排序树只有一个结点
    92.             if (root.left == null && root.right == null) {
    93.                 root = null;
    94.                 return;
    95.             }
    97.             // 去找到targetNode的父结点
    98.             Node parent = searchParent(value);
    99.             // 如果要删除的结点是叶子结点
    100.             if (targetNode.left == null && targetNode.right == null) {
    101.                 // 判断targetNode 是父结点的左子结点，还是右子结点
    102.                 if (parent.left != null && parent.left.value == value) { // 是左子结点
    103.                     parent.left = null;
    104.                 } else if (parent.right != null && parent.right.value == value) {// 是由子结点
    105.                     parent.right = null;
    106.                 }
    107.             } else if (targetNode.left != null && targetNode.right != null) { // 删除有两颗子树的节点
    108.                 int minVal = delRightTreeMin(targetNode.right);
    109.                 targetNode.value = minVal;
    111.             } else { // 删除只有一颗子树的结点
    112.                 // 如果要删除的结点有左子结点
    113.                 if (targetNode.left != null) {
    114.                     if (parent != null) {
    115.                         // 如果 targetNode 是 parent 的左子结点
    116.                         if (parent.left.value == value) {
    117.                             parent.left = targetNode.left;
    118.                         } else { // targetNode 是 parent 的右子结点
    119.                             parent.right = targetNode.left;
    120.                         }
    121.                     } else {
    122.                         root = targetNode.left;
    123.                     }
    124.                 } else { // 如果要删除的结点有右子结点
    125.                     if (parent != null) {
    126.                         // 如果 targetNode 是 parent 的左子结点
    127.                         if (parent.left.value == value) {
    128.                             parent.left = targetNode.right;
    129.                         } else { // 如果 targetNode 是 parent 的右子结点
    130.                             parent.right = targetNode.right;
    131.                         }
    132.                     } else {
    133.                         root = targetNode.right;
    134.                     }
    135.                 }
    137.             }
    139.         }
    140.     }
    142.     // 添加结点的方法
    143.     public void add(Node node) {
    144.         if (root == null) {
    145.             root = node;// 如果root为空则直接让root指向node
    146.         } else {
    147.             root.add(node);
    148.         }
    149.     }
    151.     // 中序遍历
    152.     public void infixOrder() {
    153.         if (root != null) {
    154.             root.infixOrder();
    155.         } else {
    156.             System.out.println("二叉排序树为空，不能遍历");
    157.         }
    158.     }
    159. }
    161. // 创建Node结点
    162. class Node {
    163.     int value;
    164.     Node left;
    165.     Node right;
    167.     public Node(int value) {
    169.         this.value = value;
    170.     }
    172.     // 返回左子树的高度
    173.     public int leftHeight() {
    174.         if (left == null) {
    175.             return 0;
    176.         }
    177.         return left.height();
    178.     }
    180.     // 返回右子树的高度
    181.     public int rightHeight() {
    182.         if (right == null) {
    183.             return 0;
    184.         }
    185.         return right.height();
    186.     }
    188.     // 返回 以该结点为根结点的树的高度
    189.     public int height() {
    190.         return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
    191.     }
    193.     //左旋转方法
    194.     private void leftRotate() {
    196.         //创建新的结点，以当前根结点的值
    197.         Node newNode = new Node(value);
    198.         //把新的结点的左子树设置成当前结点的左子树
    199.         newNode.left = left;
    200.         //把新的结点的右子树设置成带你过去结点的右子树的左子树
    201.         newNode.right = right.left;
    202.         //把当前结点的值替换成右子结点的值
    203.         value = right.value;
    204.         //把当前结点的右子树设置成当前结点右子树的右子树
    205.         right = right.right;
    206.         //把当前结点的左子树(左子结点)设置成新的结点
    207.         left = newNode;
    210.     }
    212.     //右旋转
    213.     private void rightRotate() {
    214.         Node newNode = new Node(value);
    215.         newNode.right = right;
    216.         newNode.left = left.right;
    217.         value = left.value;
    218.         left = left.left;
    219.         right = newNode;
    220.     }
    222.     // 查找要删除的结点
    223.     /**
    224.      * 
    225.      * @param value
    226.      *            希望删除的结点的值
    227.      * @return 如果找到返回该结点，否则返回null
    228.      */
    229.     public Node search(int value) {
    230.         if (value == this.value) { // 找到就是该结点
    231.             return this;
    232.         } else if (value < this.value) {// 如果查找的值小于当前结点，向左子树递归查找
    233.             // 如果左子结点为空
    234.             if (this.left == null) {
    235.                 return null;
    236.             }
    237.             return this.left.search(value);
    238.         } else { // 如果查找的值不小于当前结点，向右子树递归查找
    239.             if (this.right == null) {
    240.                 return null;
    241.             }
    242.             return this.right.search(value);
    243.         }
    245.     }
    247.     // 查找要删除结点的父结点
    248.     /**
    249.      * 
    250.      * @param value
    251.      *            要找到的结点的值
    252.      * @return 返回的是要删除的结点的父结点，如果没有就返回null
    253.      */
    254.     public Node searchParent(int value) {
    255.         // 如果当前结点就是要删除的结点的父结点，就返回
    256.         if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {
    257.             return this;
    258.         } else {
    259.             // 如果查找的值小于当前结点的值, 并且当前结点的左子结点不为空
    260.             if (value < this.value && this.left != null) {
    261.                 return this.left.searchParent(value); // 向左子树递归查找
    262.             } else if (value >= this.value && this.right != null) {
    263.                 return this.right.searchParent(value); // 向右子树递归查找
    264.             } else {
    265.                 return null; // 没有找到父结点
    266.             }
    267.         }
    269.     }
    271.     @Override
    272.     public String toString() {
    273.         return "Node [value=" + value + "]";
    274.     }
    276.     // 添加结点的方法
    277.     // 递归的形式添加结点，注意需要满足二叉排序树的要求
    278.     public void add(Node node) {
    279.         if (node == null) {
    280.             return;
    281.         }
    283.         // 判断传入的结点的值，和当前子树的根结点的值关系
    284.         if (node.value < this.value) {
    285.             // 如果当前结点左子结点为null
    286.             if (this.left == null) {
    287.                 this.left = node;
    288.             } else {
    289.                 // 递归的向左子树添加
    290.                 this.left.add(node);
    291.             }
    292.         } else { // 添加的结点的值大于 当前结点的值
    293.             if (this.right == null) {
    294.                 this.right = node;
    295.             } else {
    296.                 // 递归的向右子树添加
    297.                 this.right.add(node);
    298.             }
    300.         }
    302.         //当添加完一个结点后，如果: (右子树的高度-左子树的高度) > 1 , 左旋转
    303.         if(rightHeight() - leftHeight() > 1) {
    304.             //如果它的右子树的左子树的高度大于它的右子树的右子树的高度
    305.             if(right != null && right.leftHeight() > right.rightHeight()) {
    306.                 //先对右子结点进行右旋转
    307.                 right.rightRotate();
    308.                 //然后在对当前结点进行左旋转
    309.                 leftRotate(); //左旋转..
    310.             } else {
    311.                 //直接进行左旋转即可
    312.                 leftRotate();
    313.             }
    314.             return ; //必须要!!!
    315.         }
    317.         //当添加完一个结点后，如果 (左子树的高度 - 右子树的高度) > 1, 右旋转
    318.         if(leftHeight() - rightHeight() > 1) {
    319.             //如果它的左子树的右子树高度大于它的左子树的高度
    320.             if(left != null && left.rightHeight() > left.leftHeight()) {
    321.                 //先对当前结点的左结点(左子树)->左旋转
    322.                 left.leftRotate();
    323.                 //再对当前结点进行右旋转
    324.                 rightRotate();
    325.             } else {
    326.                 //直接进行右旋转即可
    327.                 rightRotate();
    328.             }
    329.         }
    330.     }
    332.     // 中序遍历
    333.     public void infixOrder() {
    334.         if (this.left != null) {
    335.             this.left.infixOrder();
    336.         }
    337.         System.out.println(this);
    338.         if (this.right != null) {
    339.             this.right.infixOrder();
    340.         }
    341.     }
    343. }