理论指导实践 二叉树用left(左子树) 和 right(右子树) 在删除的时候会遇到找parent的问题，如果引入parent节点会简单很多

    • 查找节点
      • 三种遍历方式找数据
    • 插入节点
      • 找到比较插入谁就可以了，找到对应节点的左子树和右子树，并作为他们的左子和右子
    • 遍历树
    • 删除节点
      • 删除叶子
      • 删除中间节点
      • 删除root(特殊的中间节点)

        删除是这里最为复杂的

        • 删除叶子节点，找到parent节点，将其parent节点指向null即可
        • 删除中间节点，找到左子树中最大的节点 或者 是右子树中最小的节点，然后该节点的数据修改为中间节点的数据，并将叶子节点删除。
        • root节点同上
    1. package io.github.chenshun00.web.tree;
    3. /**
    4.  * <ul>
    5.  *     <li>查找节点</li>
    6.  *     <li>插入节点</li>
    7.  *     <li>遍历树</li>
    8.  *     <li>查找最大值和最小值</li>
    9.  *     <li>删除节点
    10.  *         <ul>
    11.  *             <li>叶子节点</li>
    12.  *             <li>删除有一个子节点的节点</li>
    13.  *             <li>删除有两个子节点的节点</li>
    14.  *         </ul>
    15.  *     </li>
    16.  *     <li>二叉树的效率</li>
    17.  * </ul>
    18.  *
    19.  * @author chenshun00@gmail.com
    20.  * @since 2021/7/25 1:46 下午
    21.  */
    22. public class BinaryTree {
    24.     /**
    25.      * binaryTree.insertNode(10);
    26.      * binaryTree.insertNode(9);
    27.      * binaryTree.insertNode(8);
    28.      * binaryTree.insertNode(9);
    29.      * binaryTree.insertNode(11);
    30.      * binaryTree.insertNode(12);
    31.      * binaryTree.insertNode(13);
    32.      * binaryTree.insertNode(231);
    33.      * binaryTree.insertNode(22);
    34.      *
    35.      * @param args
    36.      */
    37.     public static void main(String[] args) {
    38.         BinaryTree binaryTree = new BinaryTree();
    40.         binaryTree.insertNode(22);
    41.         binaryTree.insertNode(1);
    42.         binaryTree.insertNode(4);
    43.         binaryTree.insertNode(3);
    44.         binaryTree.insertNode(10);
    45.         binaryTree.insertNode(9);
    46.         binaryTree.insertNode(9);
    47.         binaryTree.insertNode(8);
    48.         binaryTree.insertNode(190);
    49.         binaryTree.insertNode(11);
    50.         binaryTree.insertNode(12);
    51.         binaryTree.insertNode(13);
    52.         binaryTree.insertNode(231);
    53.         binaryTree.insertNode(22);
    54.         binaryTree.traverse();
    55.         System.out.println("删除节点:===>" + binaryTree.deleteNode(9));
    56.         binaryTree.traverse();
    57.         System.out.println("删除节点:===>" + binaryTree.deleteNode(13));
    58.         binaryTree.traverse();
    59.         System.out.println("删除节点:===>" + binaryTree.deleteNode(22));
    60.         binaryTree.traverse();
    61.         System.out.println("删除节点:===>" + binaryTree.deleteNode(22));
    62.         binaryTree.traverse();
    63. //1    3    4    8    9    9    10    11    12    13    22    22    190    231    
    64. //删除节点:===>true
    65. //1    3    4    8    ?    9    10    11    12    13    22    22    190    231    
    66. //删除节点:===>true
    67. //1    3    4    8    ?    9    10    11    12    ?    22    22    190    231    
    68. //删除节点:===>true
    69. //1    3    4    8    ?    9    10    11    12    ?    ?    22    190    231    
    70. //删除节点:===>true
    71. //1    3    4    8    ?    9    10    11    12    ?    ?    ?    190    231    
    72.     }
    74.     private Node root;
    76.     public boolean isLeaf(Node node) {
    77.         return node.leftChild == null && node.rightChild == null;
    78.     }
    80.     public Node findNext(Node node) {
    81.         if (node.leftChild != null) {
    82.             return doFindMaxNode(node.leftChild);
    83.         }
    84.         return doFindMinNode(node.rightChild);
    85.     }
    87.     public void replace(Node node) {
    88.         //找到左子树中最大的节点 或者 是右子树中最小的节点
    89.         final Node next = findNext(node);
    90.         //找到这个节点的parent节点
    91.         NodeContext nodeContext = findParent(next);
    92.         if (nodeContext == null) {
    93.             return;
    94.         }
    95.         Node parent = nodeContext.node;
    96.         if (parent == null) {
    97.             parent = node;
    98.         }
    99.         if (parent.leftChild == next) {
    100.             parent.leftChild = null;
    101.         } else if (parent.rightChild == next) {
    102.             parent.rightChild = null;
    103.         }
    104.         node.data = next.data;
    105.     }
    107.     public boolean deleteNode(Integer data) {
    108.         if (root == null) {
    109.             return false;
    110.         }
    111.         //找到当前节点
    112.         final Node node = doFindNode(data);
    113.         //找不到节点的情况
    114.         if (node == null) {
    115.             return false;
    116.         }
    117.         //如果节点是根节点
    118.         if (node == root) {
    119.             //如果根节点是叶子节点
    120.             if (isLeaf(root)) {
    121.                 root = null;
    122.             } else {
    123.                 replace(root);
    124.             }
    125.             return true;
    126.         }
    127.         //被移除的是不是叶子节点
    128.         if (isLeaf(node)) {
    129.             //找到叶子节点的parent节点，并且说明当前节点是左(left)子树还是右子树(right)
    130.             final NodeContext nodeContext = findParent(node);
    131.             final Node parentNode = nodeContext.node;
    132.             if (nodeContext.left) {
    133.                 parentNode.leftChild = null;
    134.             } else {
    135.                 parentNode.rightChild = null;
    136.             }
    137.         } else {
    138.             replace(node);
    139.         }
    140.         return true;
    141.     }
    143.     public NodeContext findParent(Node node) {
    144.         if (node == null || node == root) {
    145.             return null;
    146.         }
    147.         return doFind(root, node);
    148.     }
    150.     private NodeContext doFind(Node root, Node node) {
    151.         if (root == null) {
    152.             return null;
    153.         }
    154.         return node.data >= root.data ? doFindParentRight(root, node) : doFindParentLeft(root, node);
    155.     }
    157.     private Node doFindMaxNode(Node node) {
    158.         if (node.rightChild == null) {
    159.             return node;
    160.         } else {
    161.             return doFindMaxNode(node.rightChild);
    162.         }
    163.     }
    166.     private Node doFindMinNode(Node node) {
    167.         if (node.leftChild == null) {
    168.             return node;
    169.         } else {
    170.             return doFindMinNode(node.leftChild);
    171.         }
    172.     }
    174.     /**
    175.      * 左
    176.      */
    177.     private NodeContext doFindParentLeft(Node root, Node node) {
    178.         if (root == null) {
    179.             return null;
    180.         }
    181.         if (root.leftChild != null) {
    182.             if (root.leftChild.data.equals(node.data)) {
    183.                 return new NodeContext(root, true);
    184.             }
    185.         }
    186.         if (root.rightChild != null) {
    187.             if (root.rightChild.data.equals(node.data)) {
    188.                 return new NodeContext(root, false);
    189.             }
    190.         }
    191.         return doFind(root.leftChild, node);
    192.     }
    194.     /**
    195.      * 右
    196.      */
    197.     private NodeContext doFindParentRight(Node root, Node node) {
    198.         if (root == null) {
    199.             return null;
    200.         }
    201.         if (root.leftChild != null) {
    202.             if (root.leftChild.data.equals(node.data)) {
    203.                 return new NodeContext(root, true);
    204.             }
    205.         }
    206.         if (root.rightChild != null) {
    207.             if (root.rightChild.data.equals(node.data)) {
    208.                 return new NodeContext(root, false);
    209.             }
    210.         }
    211.         return doFind(root.rightChild, node);
    212.     }
    214.     public void insertNode(Integer data) {
    215.         if (root == null) {
    216.             root = new Node();
    217.             root.data = data;
    218.         } else {
    219.             handleData(root, data);
    220.         }
    221.     }
    223.     public void traverse() {
    224.         doTraverse(root);
    225.         System.out.println();
    226.     }
    228.     public Integer findNode(Integer data) {
    229.         return root == null ? null : doFindNode(data).data;
    230.     }
    232.     public Integer findMax() {
    233.         return root == null ? null : doFindMax(root);
    234.     }
    236.     public Integer findMin() {
    237.         return root == null ? null : doFindMin(root);
    238.     }
    241.     private void handleData(Node root, Integer data) {
    242.         if (data >= root.data) {
    243.             handleRight(root, root.rightChild, data);
    244.         } else {
    245.             handleLeft(root, root.leftChild, data);
    246.         }
    247.     }
    249.     //处理右子树
    250.     private void handleRight(Node root, Node right, Integer data) {
    251.         if (right == null) {
    252.             right = new Node();
    253.             right.data = data;
    254.             root.rightChild = right;
    255.         } else {
    256.             handleData(right, data);
    257.         }
    258.     }
    260.     //处理左子树
    261.     private void handleLeft(Node root, Node left, Integer data) {
    262.         if (left == null) {
    263.             left = new Node();
    264.             left.data = data;
    265.             root.leftChild = left;
    266.         } else {
    267.             handleData(left, data);
    268.         }
    269.     }
    271.     private void doTraverse(Node node) {
    272.         if (node == null) {
    273.             System.out.println("么数据");
    274.             return;
    275.         }
    276.         if (node.leftChild != null) {
    277.             doTraverse(node.leftChild);
    278.         }
    279.         System.out.print(node.data + "\t");
    280.         if (node.rightChild != null) {
    281.             doTraverse(node.rightChild);
    282.         }
    283.     }
    285.     private Integer doFindMax(Node node) {
    286.         if (node.rightChild == null) {
    287.             return node.data;
    288.         } else {
    289.             return doFindMax(node.rightChild);
    290.         }
    291.     }
    294.     private Integer doFindMin(Node node) {
    295.         if (node.leftChild == null) {
    296.             return node.data;
    297.         } else {
    298.             return doFindMin(node.leftChild);
    299.         }
    300.     }
    302.     private Node doFindNode(Integer data) {
    303.         return data >= root.data ? findRight(root, data) : findLeft(root, data);
    304.     }
    306.     /**
    307.      * 找到右
    308.      *
    309.      * @param root 根
    310.      * @param data 数据
    311.      * @return {@link Node}
    312.      */
    313.     private Node findRight(Node root, Integer data) {
    314.         if (root == null) {
    315.             return null;
    316.         }
    317.         if (root.data.equals(data)) {
    318.             return root;
    319.         }
    320.         if (data >= root.data) {
    321.             //右子树
    322.             return findRight(root.rightChild, data);
    323.         } else {
    324.             //左子树
    325.             return findLeft(root.leftChild, data);
    326.         }
    327.     }
    329.     /**
    330.      * 发现左
    331.      *
    332.      * @param root 根
    333.      * @param data 数据
    334.      * @return {@link Node}
    335.      */
    336.     private Node findLeft(Node root, Integer data) {
    337.         if (root == null) {
    338.             return null;
    339.         }
    340.         if (root.data.equals(data)) {
    341.             return root;
    342.         }
    343.         if (data >= root.data) {
    344.             //右子树
    345.             return findRight(root.rightChild, data);
    346.         } else {
    347.             //左子树
    348.             return findLeft(root.leftChild, data);
    349.         }
    350.     }
    352.     private static class Node {
    353.         /**
    354.          * 左子
    355.          */
    356.         public Node leftChild;
    357.         /**
    358.          * 数据
    359.          */
    360.         private Integer data;
    361.         /**
    362.          * 右子
    363.          */
    364.         public Node rightChild;
    365.     }
    367.     private static class NodeContext {
    368.         public Node node;
    369.         public boolean left;
    371.         public NodeContext(Node node, boolean left) {
    372.             this.node = node;
    373.             this.left = left;
    374.         }
    375.     }
    376. }