1.     // 删除
    2.     public void delete(int value) {
    4.         if (root == null) {
    5.             return;
    6.         }
    7.         // 获取目标节点
    8.         Node targetNode = root.search(value);
    9.         // 获取父节点
    10.         Node parentNode = root.searchParent(value);
    12.         if (targetNode == null) {
    13.             return;
    14.         }
    16.         // 特殊情况
    17.         if (parentNode == null && (targetNode.left == null || targetNode.right == null)){
    18.             if (targetNode.left != null) {
    19.                 root = targetNode.left;
    20.                 return;
    21.             }else {
    22.                 root = targetNode.right;
    23.                 return;
    24.             }
    25.         }
    27.         // 如果该二叉树只有一个节点，且要删除的结就是该节点
    28.         if (root.left == null && root.right == null) {
    29.             root = null;
    30.             return;
    31.         }
    33.         // 如果目标节点是叶子节点
    34.         if (targetNode.left == null && targetNode.right == null) {
    36.             // 判断目标节点是其父节点的左节点还是右节点
    37.             if (parentNode.left == targetNode) {
    38.                 parentNode.left = null;
    39.             } else {
    40.                 parentNode.right = null;
    41.             }
    42.         }
    44.         // 如果目标节点只有一个子树
    45.         if ((targetNode.left != null && targetNode.right == null
    46.                 || (targetNode.left == null && targetNode.right != null))) {
    48.             // 判断目标节点是其父节点的左节点还是右节点
    49.             if (parentNode.left == targetNode) {
    50.                 // 将目标节点的子节点和目标节点的父节点相连
    51.                 if (targetNode.left != null) {
    52.                     parentNode.left = targetNode.left;
    53.                 }else {
    54.                     parentNode.left = targetNode.right;
    55.                 }
    56.             }else {
    57.                 // 将目标节点的子节点和目标节点的父节点相连
    58.                 if (targetNode.left != null) {
    59.                     parentNode.right = targetNode.left;
    60.                 }else {
    61.                     parentNode.right = targetNode.right;
    62.                 }
    63.             }
    64.         }
    67.         // 如果目标节点有两个子树
    68.         if (targetNode.left != null && targetNode.right != null) {
    69.             // 寻找targetNode节点的右子树的最小节点
    70.             Node temp = targetNode.right;
    71.             // 因为最小值只会出现在左子树，即在右子树中找最底层的左子树
    72.             while (temp.left != null) {
    73.                 temp = temp.left;
    74.             }
    75.             // 删除这个最小节点（这个必是叶子节点）
    76.             delete(temp.value);
    77.             // 将targetNode的值换为temp的值
    78.             targetNode.value = temp.value;
    79.         }
    81.     }
    1.     // 查找要删除的节点
    3.     /**
    4.      * @param value 希望删除的节点的值
    5.      * @return 返回该节点
    6.      */
    7.     public Node search(int value) {
    8.         if (this.value == value) {
    9.             return this;
    10.         }
    11.         // 向左递归查找
    12.         if (value < this.value) {
    13.             // 判断this的左节点是否为空
    14.             if (this.left == null) {
    15.                 return null;
    16.             } else {
    17.                 return this.left.search(value);
    18.             }
    19.         }
    20.         // 向右递归查找
    21.         if (value > this.value) {
    22.             // 判断this的右节点是否为空
    23.             if (this.right == null) {
    24.                 return null;
    25.             } else {
    26.                return this.right.search(value);
    27.             }
    28.         }
    29.         return null;
    30.     }
    32.     // 查找目标节点的父节点
    34.     /**
    35.      * @param value 要删除节点的值
    36.      * @return 要删除节点的父节点
    37.      */
    38.     public Node searchParent(int value) {
    39.         // 如果this节点就是目标节点的父节点
    40.         if ((this.left != null && this.left.value == value) ||
    41.                 (this.right != null && this.right.value == value)) {
    42.             return this;
    43.         }
    44.         // 向左递归
    45.         if (value < this.value && this.left != null) {
    46.             return this.left.searchParent(value);
    47.         }
    49.         // 向右递归
    50.         if (value >= this.value && this.right != null) {
    51.             return this.right.searchParent(value);
    52.         }
    54.         return null;
    55.     }

    总代码

    1. package com.atguigu.binarysorttree;
    3. /**
    4.  * 二叉排序树
    5.  *
    6.  * @author Dxkstart
    7.  * @create 2022-04-10-15:48
    8.  */
    9. public class BinarySortTreeDemo {
    10.     public static void main(String[] args) {
    12.         int[] arr = new int[]{7, 3, 10, 12, 5, 1, 9, 2};
    14.         BinarySortTree binarySortTree = new BinarySortTree();
    16.         // 向树中添加
    17.         for (int i = 0; i < arr.length; i++) {
    18.             binarySortTree.add(new Node(arr[i]));
    19.         }
    21.         // 遍历
    22.         binarySortTree.infixOrder();
    25.         System.out.println("=========删除测试=========");
    27.         binarySortTree.delete(3);
    29.         System.out.println("---新的---");
    30.         // 遍历
    31.         binarySortTree.infixOrder();
    33.     }
    34. }
    36. // 创建二叉排序树
    37. class BinarySortTree {
    39.     private Node root;
    41.     // 添加节点的方法
    42.     public void add(Node node) {
    43.         // 如果是空树
    44.         if (root == null) {
    45.             root = node;
    46.         } else {
    47.             root.add(node);
    48.         }
    49.     }
    51.     // 中序遍历
    52.     public void infixOrder() {
    53.         if (root != null) {
    54.             root.infixOrder();
    55.         } else {
    56.             System.out.println("此二叉排序树为空");
    57.         }
    58.     }
    61.     // 删除
    62.     public void delete(int value) {
    64.         if (root == null) {
    65.             return;
    66.         }
    67.         // 获取目标节点
    68.         Node targetNode = root.search(value);
    69.         // 获取父节点
    70.         Node parentNode = root.searchParent(value);
    72.         if (targetNode == null) {
    73.             return;
    74.         }
    76.         // 特殊情况
    77.         if (parentNode == null && (targetNode.left == null || targetNode.right == null)){
    78.             if (targetNode.left != null) {
    79.                 root = targetNode.left;
    80.                 return;
    81.             }else {
    82.                 root = targetNode.right;
    83.                 return;
    84.             }
    85.         }
    87.         // 如果该二叉树只有一个节点，且要删除的结就是该节点
    88.         if (root.left == null && root.right == null) {
    89.             root = null;
    90.             return;
    91.         }
    93.         // 如果目标节点是叶子节点
    94.         if (targetNode.left == null && targetNode.right == null) {
    96.             // 判断目标节点是其父节点的左节点还是右节点
    97.             if (parentNode.left == targetNode) {
    98.                 parentNode.left = null;
    99.             } else {
    100.                 parentNode.right = null;
    101.             }
    102.         }
    104.         // 如果目标节点只有一个子树
    105.         if ((targetNode.left != null && targetNode.right == null
    106.                 || (targetNode.left == null && targetNode.right != null))) {
    108.             // 判断目标节点是其父节点的左节点还是右节点
    109.             if (parentNode.left == targetNode) {
    110.                 // 将目标节点的子节点和目标节点的父节点相连
    111.                 if (targetNode.left != null) {
    112.                     parentNode.left = targetNode.left;
    113.                 }else {
    114.                     parentNode.left = targetNode.right;
    115.                 }
    116.             }else {
    117.                 // 将目标节点的子节点和目标节点的父节点相连
    118.                 if (targetNode.left != null) {
    119.                     parentNode.right = targetNode.left;
    120.                 }else {
    121.                     parentNode.right = targetNode.right;
    122.                 }
    123.             }
    124.         }
    127.         // 如果目标节点有两个子树
    128.         if (targetNode.left != null && targetNode.right != null) {
    129.             // 寻找targetNode节点的右子树的最小节点
    130.             Node temp = targetNode.right;
    131.             // 因为最小值只会出现在左子树，即在右子树中找最底层的左子树
    132.             while (temp.left != null) {
    133.                 temp = temp.left;
    134.             }
    135.             // 删除这个最小节点（这个必是叶子节点）
    136.             delete(temp.value);
    137.             // 将targetNode的值换为temp的值
    138.             targetNode.value = temp.value;
    139.         }
    141.     }
    143. }
    145. // 创建Node节点
    146. class Node {
    148.     int value;
    149.     Node left;
    150.     Node right;
    152.     public Node(int value) {
    153.         this.value = value;
    154.     }
    156.     // 查找要删除的节点
    158.     /**
    159.      * @param value 希望删除的节点的值
    160.      * @return 返回该节点
    161.      */
    162.     public Node search(int value) {
    163.         if (this.value == value) {
    164.             return this;
    165.         }
    166.         // 向左递归查找
    167.         if (value < this.value) {
    168.             // 判断this的左节点是否为空
    169.             if (this.left == null) {
    170.                 return null;
    171.             } else {
    172.                 return this.left.search(value);
    173.             }
    174.         }
    175.         // 向右递归查找
    176.         if (value > this.value) {
    177.             // 判断this的右节点是否为空
    178.             if (this.right == null) {
    179.                 return null;
    180.             } else {
    181.                return this.right.search(value);
    182.             }
    183.         }
    184.         return null;
    185.     }
    187.     // 查找目标节点的父节点
    189.     /**
    190.      * @param value 要删除节点的值
    191.      * @return 要删除节点的父节点
    192.      */
    193.     public Node searchParent(int value) {
    194.         // 如果this节点就是目标节点的父节点
    195.         if ((this.left != null && this.left.value == value) ||
    196.                 (this.right != null && this.right.value == value)) {
    197.             return this;
    198.         }
    199.         // 向左递归
    200.         if (value < this.value && this.left != null) {
    201.             return this.left.searchParent(value);
    202.         }
    204.         // 向右递归
    205.         if (value >= this.value && this.right != null) {
    206.             return this.right.searchParent(value);
    207.         }
    209.         return null;
    210.     }
    212.     // 添加节点的方法
    213.     public void add(Node node) {
    215.         if (node == null) {
    216.             return;
    217.         }
    219.         // 判断传入的节点的值，和当前子树的根节点的值的关系
    220.         if (node.value < this.value) {
    221.             // 如果当前节点的左节点为空
    222.             if (this.left == null) {
    223.                 // 直接将该节点挂在this节点的左边
    224.                 this.left = node;
    225.                 return;
    226.             } else {
    227.                 // 继续向左递归
    228.                 this.left.add(node);
    229.             }
    230.             // 当前节点大于this节点的值
    231.         } else if (node.value > this.value) {
    232.             // 如果this节点的右节点为空
    233.             if (this.right == null) {
    234.                 // 直接将该节点挂在this节点的右边
    235.                 this.right = node;
    236.                 return;
    237.             } else {
    238.                 //继续向右递归
    239.                 this.right.add(node);
    240.             }
    241.         }
    243.     }
    246.     // 中序遍历
    247.     public void infixOrder() {
    248.         if (this.left != null) {
    249.             // 向左递归
    250.             this.left.infixOrder();
    251.         }
    253.         // 中间节点
    254.         System.out.println(this.value);
    256.         if (this.right != null) {
    257.             // 向右递归
    258.             this.right.infixOrder();
    259.         }
    260.     }
    263.     @Override
    264.     public String toString() {
    265.         return "Node{" +
    266.                 "value=" + value +
    267.                 '}';
    268.     }
    269. }