目前为止，我们学的数据结构分为两种，数组和链表

数组存储分析

  • 优点：访问速度快，还可以通过二分查找增加速度
  • 缺点：如果要插入值需要整体移动，效率较低

链表存储分析

  • 优点：在一定程度上对数组存储上进行优化，插入删除变得十分遍历
  • 缺点：检索效率低，需要检索值的时候每次都要从头开始遍历。

现在我们既想插入的快点一点，又想遍历的快一点怎么办？
接下来我们引入一个新的数据结构：树，来解决这个问题

image.png
上边的树是一个有序树，7是树的根节点，3是7的左子节点，10是7的右子节点，7是10和3的父节点。
而有序树是什么呢，左子节点比父节点小，右子节点比父节点大。
仔细看上图会发现每一个节点都是如此。

而无序树的话，就随意存放了。

现在这个树是有序树，我们分析一下，如果我们需要找到5这个节点。
首先5比7小，那么5一定在7的左边，5再和3比较，比3大，那么5一定在3的右边，这样是不是有种二分查找的感觉了？没错，这样我们遍历起来也很快。而插入和删除的时候，我们只需要改变链接指向就可以了。这样我们删除和插入也会很快。

树的基础概念

image.png
树有很多种，最多只能有两个节点的树称为二叉树

  • 二叉树不存在度大于2的结点
  • 左右子树是有顺序的，即使某结点只有一棵子树，也要区分它是左子树还是右子树
  • 二叉树具有五种基本形态：空二叉树、只有一个根节点、只有左子树、只有右子树、左右子树都有
  • 二叉树第i层上至多有2^(i-1)个结点(i≥1)
  • 深度为k的二叉树至多有2^k - 1个结点(k≥1)，此时为满二叉树
  • 结点拥有的子树数称为结点的度，度为0的结点称为叶子结点
  • 对任何一棵二叉树T，如果其叶子结点数为n0，度为2的结点数为n2，则n0 = n2 + 1。这个的推导：设结点数为n，可以知道结点间连接线数为n-1。于是有两个式子：n-1 = n1 + 2*n2 和 n = n0 + n1 +n2，联合解出n0 = n2 + 1
  • 若设二叉树的深度为k，除第 k 层外，其它各层 (1～k-1) 的结点数都达到最大个数，第k 层所有的结点都连续集中在最左边，这就是完全二叉树。

image.png

  • 对于完全二叉树，在有左右子结点的情况下，设根结点的编号是n(这个编号从1开始)，则左孩子的编号是2n，右孩子的编号是2n+1

    二叉树的前中后序遍历

    image.png
    对图中的树进行分析
    前序遍历：12354
    中序遍历：21534
    后序遍历：25431

代码实现

  1. public class Node {
  2.     int id;
  3.     Node left;
  4.     Node right;
  6.     @Override
  7.     public String toString() {
  8.         return "Node{" +
  9.                 "id=" + id +
  10.                 '}';
  11.     }
  13.     public Node(int id) {
  14.         this.id = id;
  15.     }
  16. }
  1. public class BinaryTreeDemo {
  3.     public static void main(String[] args) {
  4.         BinaryTree binaryTree = new BinaryTree();
  5.         Node root = new Node(1);
  6.         Node node2 = new Node(2);
  7.         Node node3 = new Node(3);
  8.         Node node4 = new Node(4);
  9.         Node node5 = new Node(5);
  10.         root.left = node2;
  11.         root.right = node3;
  12.         node3.left = node5;
  13.         node3.right = node4;
  15.         binaryTree.setRoot(root);
  16. //        binaryTree.preOrder(root);
  17. //        binaryTree.midOrder(root);
  18.         binaryTree.postOrder(root);
  19.     }
  21. }
  23. class BinaryTree {
  24.     //根节点
  25.     private Node root;
  27.     public void setRoot(Node root) {
  28.         this.root = root;
  29.     }
  31.     //前序遍历
  32.     public void preOrder(Node root) {
  33.         //首先输出父节点
  34.         System.out.println(root);
  35.         //判断左节点是否为空
  36.         if (root.left != null) {
  37.             preOrder(root.left);
  38.         }
  39.         if (root.right != null) {
  40.             preOrder(root.right);
  41.         }
  42.     }
  43.     //中序遍历
  44.     public void midOrder(Node root) {
  45.         //判断左节点是否为空
  46.         if (root.left != null) {
  47.             midOrder(root.left);
  48.         }
  49.         //输出父节点
  50.         System.out.println(root);
  51.         //判断右节点
  52.         if (root.right != null) {
  53.             midOrder(root.right);
  54.         }
  55.     }
  56.     //后序遍历
  57.     public void postOrder(Node root) {
  58.         //判断左节点是否为空
  59.         if (root.left != null) {
  60.             postOrder(root.left);
  61.         }
  62.         //判断右节点
  63.         if (root.right != null) {
  64.             postOrder(root.right);
  65.         }
  66.         //输出父节点
  67.         System.out.println(root);
  68.     }
  69. }

线索化二叉树

image.png
图中我们可以发现，它的中序遍历顺序为 8，3，10，1，14，6
但叶子节点8，10，14的左右指针和 节点6的右指针都没用上。
为了不让它空闲，充分利用空间
我们可以让它们的 左指针指向前驱节点，右指针指向后继节点
image.png
这样我们可以快速得到遍历顺序。
这样的二叉树，我们称之为线索化二叉树。

代码实现

为了能够区分一个节点的左指针到底指向的是前驱节点还是左子节点，我们有必要用一个变量来区分一下

  1. public class Node {
  2.     int id;
  3.     Node left;
  4.     Node right;
  6.     //为了在线索化二叉树中区分
  7.     //0表示子节点，1表示前驱或后继结点
  8.     int leftType;
  9.     int rightType;
  11.     @Override
  12.     public String toString() {
  13.         return "Node{" +
  14.                 "id=" + id +
  15.                 '}';
  16.     }
  18.     public Node(int id) {
  19.         this.id = id;
  20.     }
  21. }

首先我们要对二叉树进行线索化。
以中序为例，不明白代码的，debug或者画图就会了解。

树 - 图7

然后我们之前的中序遍历方式毫无疑问已经不能用了，所以我们必须重新相出一个遍历方法从根节点开始

  • 先找到被线索化的节点curNode，遍历循环 curNode = curNode.left;
  • 如果找不到线索化的节点，输出当前节点
  • 如果 curNode.rightType = 1的话，一直遍历输出右指针类型为0
  • 现在rightType = 0了，我们让curNode = curNode.right ，再次回到第一步循环，直到curNode = null

我们对着图先来一遍过程：
首先找到了节点8，发现这个是被线索化的节点，curNode=8，那么我们一直遍历它的后继节点->3，这个时候我们发现3并不是被线索化的节点。那么我们只能让curNode = 3了，我们发现它没指向后继节点，那么我们就让curNode = curNode.right
现在curNode = 10了，我们继续来循环，遍历left发现，leftType = 1，那没事了，我们来遍历rightType = 1的时候。输出了1，发现1也没后继，那么curNode = curNode.right，
curNode = 6，发现6也不是被线索化的节点，我们就遍历left找到了14.然后就完事了。

  1. public class ThreadedBinaryTreeDemo {
  3.     //线索化二叉树的实现
  4.     public static void main(String[] args) {
  5.         ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
  6.         Node root = new Node(1);
  7.         Node node3 = new Node(3);
  8.         Node node8 = new Node(8);
  9.         Node node10 = new Node(10);
  10.         Node node14 = new Node(14);
  11.         Node node6 = new Node(6);
  12.         root.left = node3;
  13.         root.right = node6;
  14.         node3.left = node8;
  15.         node3.right = node10;
  16.         node6.left = node14;
  17.         threadedBinaryTree.setRoot(root);
  18. //        threadedBinaryTree.midOrder(root);
  19.         threadedBinaryTree.threadedNodes();
  20.         threadedBinaryTree.threadedList();
  23.     }
  25. }
  27. class ThreadedBinaryTree {
  28.     //根节点
  29.     private Node root;
  30.     //为了实现线索化，需要创建一个指向前驱结点的一个指针
  31.     private Node pre = null;
  33.     public void setRoot(Node root) {
  34.         this.root = root;
  35.     }
  37.     public void threadedNodes() {
  38.         this.threadedNodes(root);
  39.     }
  41.     /**
  42.      * 对当前节点进行线索化
  43.      * 中序线索化为例
  44.      * @param node
  45.      */
  46.     public void threadedNodes(Node node) {
  47.         //如果node == null，无法线索化
  48.         if (node == null){
  49.             return;
  50.         }
  52.         //先线索化左子树
  53.         threadedNodes(node.left);
  54.         //线索化当前节点
  55.         //处理前驱节点
  56.         if (node.left == null) {
  57.             //指向前驱节点
  58.             node.left = pre;
  59.             //修改当前节点的左指针类型
  60.             node.leftType = 1;
  61.         }
  63.         //指向后继节点(实际上是在第一次回溯的时候才开始进行)
  64.         //第一次 pre = null，当第一次回溯的时候，这里pre变成了前驱节点
  65.         if (pre != null && pre.right == null) {
  66.             pre.right = node;
  67.             pre.rightType = 1;
  68.         }
  70.         //最最重要的一条
  71.         pre = node;
  73.         //线索化右子树
  74.         threadedNodes(node.right);
  75.     }
  77.     //遍历线索化二叉树的方法(中序为例)
  78.     public void threadedList() {
  79.         //定义一个变量,存储当前遍历的节点
  80.         Node curNode = root;
  81.         while (curNode != null) {
  83.             //循环找到被线索化的节点 如果节点的leftType == 1，说明是线索化的有效节点
  84.             while (curNode.leftType == 0) {
  85.                 curNode = curNode.left;
  86.             }
  88.             System.out.println(curNode);
  90.             //如果当前节点的右指针指向的是后继节点，那么就一直输出。
  91.             while (curNode.rightType == 1) {
  92.                 curNode = curNode.right;
  93.                 System.out.println(curNode);
  94.             }
  96.             curNode = curNode.right;
  97.         }
  99.     }
  101. }

哈夫曼树（最优二叉树）

哈夫曼树，也被叫做最优二叉树，它的带权路径的值(WPL)为最小。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度。权值越大的节点，离根节点越近。
这样说可能有点晦涩

举个例子：

image.png
wpl = 13 2 + 7 2 + 8 2 + 3 2
13 为叶子节点的值，2为路径长度（根节点到该叶子节点的长度）。但是这并不是哈夫曼树

权值越大的节点，离根节点越近

image.png这样才是最优二叉树

现在一组数据，我们将它变为二叉树
13, 7, 8, 3, 29, 6, 1
从中找出两个最小的 值（可以一开始先排好序）组成一个二叉树，根节点的值为 两个最小值的和，然后将这个值放进数组中
image.png
现在数组变为了 13, 7, 8, 29, 6, 4
再次从中找两个最小值，4，6，组成一个二叉树。将4 + 6 =10放入到数组中。
image.png
现在数组变为13, 7, 8, 29,10
再次找出最小值 7 和 8，我们发现与我们上边组成的树毫无关系，那么我们只能新组一个树。
然后将15放入数组
image.png
现在数组变为13，29,10，15
两个最小值为13和10，现在我们将13和10组成树，23放入到数组中
image.png
现在数组变为 29，15，23
两个最小值为15和23，38放进数组
image.png
数组只剩下29和38了，我们放入树中，哈夫曼树完成！
image.png

代码实现

  1. public class HuffmanTree {
  3.     //哈夫曼树
  4.     public static void main(String[] args) {
  5.         int[] arr = {13, 7, 8, 3, 29, 6, 1};
  7.         //创建哈夫曼树
  8.         HuffmanNode root = createHuffman(arr);
  9.         preOrder(root);
  10.     }
  12.     //创建哈夫曼树
  13.     private static HuffmanNode createHuffman(int[] arr) {
  14.         //首先转化成list方便操作
  15.         List<HuffmanNode> data = new LinkedList<>();
  17.         for (int i = 0; i < arr.length; i++) {
  18.             data.add(new HuffmanNode(arr[i]));
  19.         }
  21.         while (data.size() > 1) {
  22.             //进行排序（也可以自己手写）
  23.             data = data.stream().sorted((o1, o2) -> o1.val - o2.val).collect(Collectors.toList());
  25.             //去除两个最小的值
  26.             HuffmanNode leftNode = data.get(0);
  27.             HuffmanNode rightNode = data.get(1);
  29.             //生成树
  30.             HuffmanNode parent = new HuffmanNode(leftNode.val + rightNode.val);
  31.             parent.left = leftNode;
  32.             parent.right = rightNode;
  34.             data.remove(leftNode);
  35.             data.remove(rightNode);
  36.             data.add(parent);
  37.         }
  39.         //返回根节点。
  40.         return data.get(0);
  42.     }
  44.     public static void preOrder(HuffmanNode root) {
  45.         //首先输出父节点
  46.         System.out.println(root);
  47.         //判断左节点是否为空
  48.         if (root.left != null) {
  49.             preOrder(root.left);
  50.         }
  51.         if (root.right != null) {
  52.             preOrder(root.right);
  53.         }
  54.     }
  56. }
  58. class HuffmanNode {
  59.     int val;
  60.     HuffmanNode left;
  61.     HuffmanNode right;
  63.     public HuffmanNode(int val) {
  64.         this.val = val;
  65.     }
  67.     @Override
  68.     public String toString() {
  69.         return "HuffmanNode{" +
  70.                 "val=" + val +
  71.                 '}';
  72.     }
  73. }

二叉排序树（BST）

image.png
二叉排序树的定义和创建都非常的简单，他的麻烦之处在于删除。
仔细观察二叉排序树，会发现它在查找的时候就有着二分的性质，这点让它既能快速的增删，也能快速的查找。

创建就没什么好说的了。比根节点大就放右边，小就放左边。
我们来说一下删除。
删除分三种情况

一种是删除叶子节点。比如说上图的2，5，9，12
删除叶子节点好说，我们只需要找到它的父节点，然后判断它是父节点的左子树还是右子树，让对应的left和right指针为null就行了。

删除只有一个子节点的节点。
比如说上图中的节点 1
我们首先要判断要删除的节点 （这里我们叫做targetNode） 是有左子树还是右子树
有左子树的情况
我们再判断targetNode是父节点（parentNode）的左子树还是右子树，然后对应的
parentNode.left = targetNode.left 或 parentNode.right = targetNode.left;
有右子树的情况则反之。
parentNode.left = targetNode.right 或 parentNode.right = targetNode.right;

最后一种情况就是，被删除的节点targetNode 有两个子节点。比如，3，7，10
这个时候，我们的做法应该是。
找出右子树中值最小的那个节点
也就是一直遍targetNode.right 的左边，直到找到 targetNode.right.left = null，targetNode的变成这个最小节点的值。

我们也可以选择找出左子树中最大的节点。

代码实现

  1. public class BinarySortTreeDemo {
  3.     public static void main(String[] args) {
  5.         int[] arr = {7, 3, 10, 12, 5, 1, 9, 2};
  7.         BinarySortTree tree = new BinarySortTree();
  9.         for (int i = 0; i < arr.length; i++) {
  10.             Node node = new Node(arr[i]);
  11.             tree.add(node);
  12.         }
  14.         tree.midOrder(tree.root);
  15.         tree.delNode(2);
  16.         tree.delNode(5);
  17.         tree.delNode(9);
  18.         tree.delNode(12);
  19.         tree.delNode(7);
  20.         tree.delNode(3);
  21.         tree.delNode(10);
  22.         tree.delNode(1);
  23.         tree.midOrder(tree.root);
  25.     }
  27. }
  29. class BinarySortTree {
  31.     Node root;
  33.     public void add(Node node) {
  34.         if (root == null) {
  35.             root = node;
  36.         }else {
  37.             if (node == null) {
  38.                 return;
  39.             }
  40.             Node curNode =  root;
  41.             while (curNode != null) {
  42.                 if (curNode.id > node.id) {
  43.                     //说明curNode比新增节点大，新增节点应该在当前节点的左边
  44.                     if (curNode.left == null) {
  45.                         //如果当前节点的左子树为null，那么我们可以直接加入到curNode左边。
  46.                         curNode.left = node;
  47.                         return;
  48.                     }
  49.                     curNode = curNode.left;
  50.                 }else {
  51.                     if (curNode.right == null) {
  52.                         //如果当前节点的右子树为null，那么我们可以直接加入到curNode右边。
  53.                         curNode.right = node;
  54.                         return;
  55.                     }
  56.                     curNode = curNode.right;
  57.                 }
  58.             }
  60.         }
  61.     }
  63.     //中序遍历
  64.     public void midOrder(Node node) {
  65.         if (root == null) {
  66.             return;
  67.         }
  68.         if (node.left != null) {
  69.             midOrder(node.left);
  70.         }
  71.         System.out.println(node);
  72.         if (node.right != null) {
  73.             midOrder(node.right);
  74.         }
  75.     }
  76.     /**
  77.      * 查找要删除的节点
  78.      *
  79.      * @param value 希望删除的节点的值
  80.      */
  81.     public Node search(int value) {
  82.         return this.search(root, value);
  83.     }
  85.     public Node search(Node node,int value) {
  86.         if (node.id == value) {
  87.             return node;
  88.         } else if (value < node.id) {
  89.             if (node.left != null) {
  90.                 return search(node.left, value);
  91.             }
  92.             return null;
  93.         } else {
  94.             if (node.right != null) {
  95.                 return search(node.right, value);
  96.             }
  97.             return null;
  98.         }
  99.     }
  101.     //查找要删除节点的父节点
  102.     public Node searchParent(Node node, int value) {
  103.         //左子树不为null，并且左子树值相等 or（右子树不为null，右子树值相等）
  104.         if ((node.left != null && node.left.id == value) ||
  105.                 (node.right != null && node.right.id == value)){
  106.             return node;
  107.         }else {
  108.             //比当前节点值小，去递归左子树找，否则去右子树
  109.             if (value < node.id && node.left != null) {
  110.                 return searchParent(node.left, value);
  111.             }else if (value > node.id && node.right != null) {
  112.                 return searchParent(node.right, value);
  113.             }
  114.             //都不满足返回null
  115.             return null;
  116.         }
  117.     }
  119.     public void delNode(int value) {
  120.         if (root != null) {
  121.             //当前树只有根节点的情况，我们可以直接置空
  122.             if (root.left == null && root.right ==null) {
  123.                 root = null;
  124.                 return;
  125.             }
  126.             Node targetNode = search(value);
  127.             //没找到要和删除的节点
  128.             if (targetNode == null) {
  129.                 return;
  130.             }
  131.             //找到要删除节点的父节点
  132.             Node parentNode = searchParent(root,value);
  134.             //如果当前节点为叶子节点
  135.             if (targetNode.left == null && targetNode.right == null){
  136.                 //判断当前节点是父节点左子树还是右子树
  137.                 if (parentNode.left != null && value == parentNode.left.id) {
  138.                     parentNode.left = null;
  139.                 }else if (parentNode.right != null && value == parentNode.right.id){
  140.                     parentNode.right = null;
  141.                 }
  142.             }else if (targetNode.left != null && targetNode.right != null) {
  143.                 //当前节点有两个子节点,即有两个左右子树
  144.                 int min = delRightTreeMin(targetNode.right);
  145.                 targetNode.id = min;
  147.             }else {
  148.                 //当前节点有一个子节点
  149.                 //如果要删除的节点有左子树
  150.                 if (targetNode.left != null) {
  151.                     //如果父节点为null，那么该节点为根节点
  152.                     if (parentNode != null) {
  153.                         //并且当前节点 为父节点的左子树
  154.                         if (value == parentNode.left.id) {
  155.                             parentNode.left = targetNode.left;
  156.                         }else {
  157.                             //当前节点为父节点的右子节点
  158.                             parentNode.right = targetNode.left;
  159.                         }
  160.                     }else {
  161.                         root = targetNode.left;
  162.                     }
  163.                 }else {
  164.                     if (parentNode != null) {
  165.                         //要删除的节点有右子节点
  166.                         //并且当前节点 为父节点的左子树
  167.                         if (value == parentNode.left.id) {
  168.                             parentNode.left = targetNode.right;
  169.                         }else {
  170.                             //当前节点为父节点的右子节点
  171.                             parentNode.right = targetNode.right;
  172.                         }
  173.                     }else {
  174.                         root = targetNode.right;
  175.                     }
  176.                 }
  178.             }
  181.         }
  182.     }
  184.     /**
  185.      * 查找右子树中的最小节点
  186.      * @param node
  187.      * @return
  188.      */
  189.     public int delRightTreeMin(Node node) {
  190.         Node target = node;
  191.         //循环的查找左子节点,就会找到最小值
  192.         while (target.left != null) {
  193.             target = target.left;
  194.         }
  195.         //这时target已经指向了最小节点,我们需要把这个节点给删掉
  196.         delNode(target.id);
  197.         return target.id;
  198.     }
  200. }

现在我们已经很清楚如何对一个二叉排序树进行基本操作了。
但是如果现在有一组数据为1，2，3，4，5，那么我们来变成一个二叉排序树看看
image.png
这个时候我们会发现，这个树变回单链表了对吧？它的查找速度毫无疑问变慢了，甚至因为一些多余的操作，比原来的单链表还要慢，完全没有发挥出我们原有的二叉排序树的特性，我们该这么办？
为了解决这个问题，我们要引入二叉平衡树。

二叉平衡树（AVL）

image.png
AVL是对二叉排序树的一种改进。
当它的两个子树的高度差值大于1的时候，就会出现旋转。

左旋

如果右子树的高度 - 左子树的高度 > 1，那么会进行左旋转，降低右子树的高度。
我们来分析一波数据，4, 3, 6, 5, 7, 8
image.png
毫无疑问，根节点左子树的高度为3 - 根节点左子树高度为1 = 2 > 1，这个时候我们要进行左旋转。
左旋转步骤

  • 1-首先创建一个新节点，值为当前节点的值
  • 2-新节点left 指向当前节点的left
  • 3-新节点的right 指向当前节点的右子树的左子树
  • 4-当前节点的值替换成右子树的值
  • 5-当前节点右子树设置成当前节点的右子树的右子树
  • 6-当前节点的左子树设置成新的节点

步骤如下图：
image.png

右旋

如果左子树的高度 - 右子树的高度 > 1，那么会进行右旋转，降低左子树的高度。
一组数据：10, 12, 8, 9, 7, 6
image.png
毫无疑问，左子树高度3 - 右子树高度1 = 2 > 1，要进行右旋转
右旋转的步骤：

  • 1-首先创建一个新节点，值为当前节点的值
  • 2-新节点right 指向当前节点的right
  • 3-新节点left 指向当前节点的left的right
  • 4-当前节点的值替换成左子树的值
  • 5-当前节点左子树设置成当前节点的左子树的左子树
  • 6-当前节点的右子树设置成新的节点

步骤如图：
image.png

我们我们在进行转为平衡树的时候，只需要一次左旋转和一次右旋转，这样就能解决问题了吗？
并不，有的时候，我们需要双旋转，即一次左旋加右旋（或一次右旋加左旋）

双旋

一组数据：10, 11, 7, 6, 8, 9
我们来看看它的树结构，会发现确实左子树高度 > 右子树高度，于是我们进行了一次右旋，发现变成了右子树高度大于左子树高度了，这并不是我们所期望的二叉树
image.png
这种情况怎么办呢？
我们在进行右旋之前，先要判断根节点的左子树的情况。
如果左子树的右子树高度 > 左子树的左子树高度，那么我们要对根节点的左子树进行一次左旋。
image.png
同理在进行左旋之前
我们要判断根节点右子树的情况
如果根节点右子树的左子树的高度 > 右子树的右子树的高度，那么我们要先对根节点的右子树右旋
这里就不画图了，根上边步骤差不多。

代码实现

  1. public class AVLTreeDemo {
  3.     public static void main(String[] args) {
  5.         //左旋转
  6.         //int[] arr = {4, 3, 6, 5, 7, 8};
  7.         //右旋转
  8.         //int[] arr = {10, 12, 8, 9, 7, 6};
  9.         //这组数据会发现，单旋转并不能让我们的树变为平衡二叉树
  10.         int[] arr = {10, 11, 7, 6, 8, 9};
  11.         AVLTree avlTree = new AVLTree();
  12.         for (int i = 0; i < arr.length; i++) {
  13.             avlTree.add(new AVLNode(arr[i]));
  14.         }
  15.         avlTree.midOrder(avlTree.root);
  16.         System.out.println("当前根节点为" + avlTree.root);
  17.         System.out.println("树的高度" + avlTree.root.height());
  18.         System.out.println("左子树的高度" + avlTree.root.leftHeight());
  19.         System.out.println("右子树的高度" + avlTree.root.rightHeight());
  20.     }
  22. }
  24. class AVLTree {
  25.     AVLNode root;
  27.     /**
  28.      * 因为右子树高度 - 左子树高度 > 1
  29.      * 左旋转 变为平衡二叉树
  30.      *
  31.      * @param node 在非双旋（左右都要旋转）的情况下，为root
  32.      */
  33.     public void leftRotate(AVLNode node) {
  34.         //首先创建一个新节点，值为当前节点的值
  35.         AVLNode newNode = new AVLNode(node.id);
  36.         //新节点left 指向当前节点的left
  37.         newNode.left = node.left;
  38.         //新节点的right 指向当前节点的右子树的左子树
  39.         newNode.right = node.right.left;
  40.         //当前节点的值替换成右子树的值
  41.         node.id = node.right.id;
  42.         //当前节点右子树设置成当前节点的右子树的右子树
  43.         node.right = node.right.right;
  44.         //当前节点的左子树设置成新的节点
  45.         node.left = newNode;
  46.     }
  48.     /**
  49.      * 左子树高度 - 右子树高度 > 1
  50.      * 右旋转 变为平衡二叉树
  51.      * @param node 在非双旋的情况下，为root
  52.      */
  53.     public void rightRotate(AVLNode node) {
  54.         //首先创建一个新节点，值为当前节点的值
  55.         AVLNode newNode = new AVLNode(node.id);
  56.         //新节点right 指向当前节点的right
  57.         newNode.right = node.right;
  58.         //新节点left 指向当前节点的left的right
  59.         newNode.left = node.left.right;
  60.         //当前节点的值替换成左子树的值
  61.         node.id = node.left.id;
  62.         node.left = node.left.left;
  63.         node.right = newNode;
  64.     }
  66.     //以下代码就是二叉排序数的代码,add方法要修改
  67.     public void add(AVLNode node) {
  68.         if (root == null) {
  69.             root = node;
  70.             return;
  71.         }
  73.         if (node == null) {
  74.             return;
  75.         }
  77.         AVLNode curNode =  root;
  78.         while (curNode != null) {
  79.             if (curNode.id > node.id) {
  80.                 //说明curNode比新增节点大，新增节点应该在当前节点的左边
  81.                 if (curNode.left == null) {
  82.                     //如果当前节点的左子树为null，那么我们可以直接加入到curNode左边。
  83.                     curNode.left = node;
  84.                     break;
  85.                 }
  86.                 curNode = curNode.left;
  87.             }else {
  88.                 if (curNode.right == null) {
  89.                     //如果当前节点的右子树为null，那么我们可以直接加入到curNode右边。
  90.                     curNode.right = node;
  91.                     break;
  92.                 }
  93.                 curNode = curNode.right;
  94.             }
  95.         }
  96.         int leftHeight = root.leftHeight();
  97.         int rightHeight = root.rightHeight();
  98.         //判断是否需要左旋转
  99.         if (rightHeight - leftHeight > 1) {
  100.             System.out.println("左旋转");
  101.             //如果右子树的左子树高度大于右子树的右子树高度的话，那么我们还要进行一次右旋转
  102.             if (root.right != null && root.right.leftHeight() > root.right.rightHeight()) {
  103.                 //右节点
  104.                 System.out.println("右子树右旋转");
  105.                 leftRotate(root.right);
  106.             }
  107.             leftRotate(root);
  108.             return;
  109.         }
  111.         //判断是否需要右旋转
  112.         if (leftHeight - rightHeight > 1) {
  113.             System.out.println("右旋转");
  114.             //如果左子树的右子树高度大于左子树的左子树高度的话，那么我们还要进行一次左旋转
  115.             if (root.left != null && root.left.rightHeight() > root.left.leftHeight()) {
  116.                 //左节点
  117.                 System.out.println("左子树左旋转");
  118.                 leftRotate(root.left);
  119.             }
  120.             rightRotate(root);
  121.         }
  123.     }
  125.     //中序遍历
  126.     public void midOrder(AVLNode node) {
  127.         if (root == null) {
  128.             return;
  129.         }
  130.         if (node.left != null) {
  131.             midOrder(node.left);
  132.         }
  133.         System.out.println(node);
  134.         if (node.right != null) {
  135.             midOrder(node.right);
  136.         }
  137.     }
  138.     /**
  139.      * 查找要删除的节点
  140.      *
  141.      * @param value 希望删除的节点的值
  142.      */
  143.     public AVLNode search(int value) {
  144.         return this.search(root, value);
  145.     }
  147.     public AVLNode search(AVLNode node,int value) {
  148.         if (node.id == value) {
  149.             return node;
  150.         } else if (value < node.id) {
  151.             if (node.left != null) {
  152.                 return search(node.left, value);
  153.             }
  154.             return null;
  155.         } else {
  156.             if (node.right != null) {
  157.                 return search(node.right, value);
  158.             }
  159.             return null;
  160.         }
  161.     }
  163.     //查找要删除节点的父节点
  164.     public AVLNode searchParent(AVLNode node, int value) {
  165.         //左子树不为null，并且左子树值相等 or（右子树不为null，右子树值相等）
  166.         if ((node.left != null && node.left.id == value) ||
  167.                 (node.right != null && node.right.id == value)){
  168.             return node;
  169.         }else {
  170.             //比当前节点值小，去递归左子树找，否则去右子树
  171.             if (value < node.id && node.left != null) {
  172.                 return searchParent(node.left, value);
  173.             }else if (value > node.id && node.right != null) {
  174.                 return searchParent(node.right, value);
  175.             }
  176.             //都不满足返回null
  177.             return null;
  178.         }
  179.     }
  181.     public void delNode(int value) {
  182.         if (root != null) {
  183.             //当前树只有根节点的情况，我们可以直接置空
  184.             if (root.left == null && root.right ==null) {
  185.                 root = null;
  186.                 return;
  187.             }
  188.             AVLNode targetNode = search(value);
  189.             //没找到要和删除的节点
  190.             if (targetNode == null) {
  191.                 return;
  192.             }
  193.             //找到要删除节点的父节点
  194.             AVLNode parentNode = searchParent(root,value);
  196.             //如果当前节点为叶子节点
  197.             if (targetNode.left == null && targetNode.right == null){
  198.                 //判断当前节点是父节点左子树还是右子树
  199.                 if (parentNode.left != null && value == parentNode.left.id) {
  200.                     parentNode.left = null;
  201.                 }else if (parentNode.right != null && value == parentNode.right.id){
  202.                     parentNode.right = null;
  203.                 }
  204.             }else if (targetNode.left != null && targetNode.right != null) {
  205.                 //当前节点有两个子节点,即有两个左右子树
  206.                 int min = delRightTreeMin(targetNode.right);
  207.                 targetNode.id = min;
  209.             }else {
  210.                 //当前节点有一个子节点
  211.                 //如果要删除的节点有左子树
  212.                 if (targetNode.left != null) {
  213.                     //如果父节点为null，那么该节点为根节点
  214.                     if (parentNode != null) {
  215.                         //并且当前节点 为父节点的左子树
  216.                         if (value == parentNode.left.id) {
  217.                             parentNode.left = targetNode.left;
  218.                         }else {
  219.                             //当前节点为父节点的右子节点
  220.                             parentNode.right = targetNode.left;
  221.                         }
  222.                     }else {
  223.                         root = targetNode.left;
  224.                     }
  225.                 }else {
  226.                     if (parentNode != null) {
  227.                         //要删除的节点有右子节点
  228.                         //并且当前节点 为父节点的左子树
  229.                         if (value == parentNode.left.id) {
  230.                             parentNode.left = targetNode.right;
  231.                         }else {
  232.                             //当前节点为父节点的右子节点
  233.                             parentNode.right = targetNode.right;
  234.                         }
  235.                     }else {
  236.                         root = targetNode.right;
  237.                     }
  238.                 }
  240.             }
  243.         }
  244.     }
  246.     /**
  247.      * 查找右子树中的最小节点
  248.      * @param node
  249.      * @return
  250.      */
  251.     public int delRightTreeMin(AVLNode node) {
  252.         AVLNode target = node;
  253.         //循环的查找左子节点,就会找到最小值
  254.         while (target.left != null) {
  255.             target = target.left;
  256.         }
  257.         //这时target已经指向了最小节点,我们需要把这个节点给删掉
  258.         delNode(target.id);
  259.         return target.id;
  260.     }
  262. }
  264. class AVLNode {
  265.     int id;
  266.     AVLNode left;
  267.     AVLNode right;
  269.     @Override
  270.     public String toString() {
  271.         return "AVLNode{" +
  272.                 "id=" + id +
  273.                 '}';
  274.     }
  276.     public AVLNode(int id) {
  277.         this.id = id;
  278.     }
  280.     //返回以当前节点为根节点的树的高度(当前节点+子树有多高)
  281.     public int height() {
  282.         return Math.max(left == null ? 0 : left.height(),right == null ? 0 : right.height()) + 1;
  283.     }
  285.     //返回左子树的高度
  286.     public int leftHeight() {
  287.         if (left == null) {
  288.             return 0;
  289.         }
  290.         return left.height();
  291.     }
  293.     public int rightHeight() {
  294.         if (right == null) {
  295.             return 0;
  296.         }
  297.         return right.height();
  298.     }
  300. }