二叉🌲【3节点实现】

比起2节点二叉树的删除操作，3节点的删除更加舒服一点，减少了很多扯蛋蛋的操作，加一个parent的只不过添加了一点点空间而已。

package io.github.chenshun00.web.tree;
/**
 * @author luobo.cs@raycloud.com
 * @since 2021/8/13 1:24 下午
 */
public class BinaryTree2 {
    public static void main(String[] args) {
        BinaryTree2 binaryTree = new BinaryTree2();
        binaryTree.insertNode(22);
        binaryTree.insertNode(1);
        binaryTree.insertNode(4);
        binaryTree.insertNode(3);
        binaryTree.insertNode(10);
        binaryTree.insertNode(9);
        binaryTree.insertNode(9);
        binaryTree.insertNode(8);
        binaryTree.insertNode(190);
        binaryTree.insertNode(11);
        binaryTree.insertNode(12);
        binaryTree.insertNode(13);
        binaryTree.insertNode(231);
        binaryTree.insertNode(22);
        binaryTree.traverse();
        System.out.println("删除节点:===>" + binaryTree.deleteNode(9));
        binaryTree.traverse();
        System.out.println("删除节点:===>" + binaryTree.deleteNode(13));
        binaryTree.traverse();
        System.out.println("删除节点:===>" + binaryTree.deleteNode(22));
        binaryTree.traverse();
        System.out.println("删除节点:===>" + binaryTree.deleteNode(22));
        binaryTree.traverse();
    }
    public Node root;
    public boolean deleteNode(Integer data) {
        if (root == null) {
            return false;
        }
        //找到当前节点
        final Node node = doFindNode(data);
        //找不到节点的情况
        if (node == null) {
            return false;
        }
        //如果节点是根节点
        if (node == root) {
            //如果根节点是叶子节点
            if (isLeaf(root)) {
                root = null;
            } else {
                replace(root);
            }
            return true;
        }
        //被移除的是叶子节点
        if (isLeaf(node)) {
            //找到叶子节点的parent节点，并且说明当前节点是左(left)子树还是右子树(right)
            final Node parent = node.parent;
            if (parent.leftChild == node) {
                parent.leftChild = null;
            } else {
                parent.rightChild = null;
            }
        } else {
            replace(node);
        }
        return true;
    }
    public Node findNode(Integer data) {
        return root == null ? null : doFindNode(data);
    }
    public void insertNode(Integer data) {
        if (root == null) {
            root = new Node(null, null, null, data);
        } else {
            handleData(root, data);
        }
    }
    public void traverse() {
        doTraverse(root);
        System.out.println();
    }
    //==============================删==================================
    private void replace(Node node) {
        //找到左子树中最大的节点 或者 是右子树中最小的节点
        final Node next = findNext(node);
        final Node parent = next.parent;
        if (parent.leftChild == next) {
            parent.leftChild = null;
        } else if (parent.rightChild == next) {
            parent.rightChild = null;
        }
        node.data = next.data;
    }
    private Node findNext(Node node) {
        if (node.leftChild != null) {
            return doFindMaxNode(node.leftChild);
        }
        return doFindMinNode(node.rightChild);
    }
    private Node doFindMaxNode(Node node) {
        if (node.rightChild == null) {
            return node;
        } else {
            return doFindMaxNode(node.rightChild);
        }
    }
    private Node doFindMinNode(Node node) {
        if (node.leftChild == null) {
            return node;
        } else {
            return doFindMinNode(node.leftChild);
        }
    }
    public boolean isLeaf(Node node) {
        return node.leftChild == null && node.rightChild == null;
    }
    //==============================查==================================
    private Node doFindNode(Integer data) {
        return data >= root.data ? findRight(root, data) : findLeft(root, data);
    }
    /**
     * 找到右
     *
     * @param root 根
     * @param data 数据
     * @return {@link Node}
     */
    private Node findRight(Node root, Integer data) {
        if (root == null) {
            return null;
        }
        if (root.data.equals(data)) {
            return root;
        }
        if (data >= root.data) {
            //右子树
            return findRight(root.rightChild, data);
        } else {
            //左子树
            return findLeft(root.leftChild, data);
        }
    }
    private Node findLeft(Node root, Integer data) {
        if (root == null) {
            return null;
        }
        if (root.data.equals(data)) {
            return root;
        }
        if (data >= root.data) {
            //右子树
            return findRight(root.rightChild, data);
        } else {
            //左子树
            return findLeft(root.leftChild, data);
        }
    }
    //==============================遍历==================================
    private void doTraverse(Node node) {
        if (node == null) {
            System.out.println("么数据");
            return;
        }
        if (node.leftChild != null) {
            doTraverse(node.leftChild);
        }
        System.out.print(node.data + "\t");
        if (node.rightChild != null) {
            doTraverse(node.rightChild);
        }
    }
    //=================插入数据=====================
    private void handleData(Node root, Integer data) {
        if (data >= root.data) {
            handleRight(root, root.rightChild, data);
        } else {
            handleLeft(root, root.leftChild, data);
        }
    }
    //处理右子树
    private void handleRight(Node root, Node right, Integer data) {
        if (right == null) {
            right = new Node(null, null, root, data);
            root.rightChild = right;
        } else {
            handleData(right, data);
        }
    }
    //处理左子树
    private void handleLeft(Node root, Node left, Integer data) {
        if (left == null) {
            left = new Node(null, null, root, data);
            root.leftChild = left;
        } else {
            handleData(left, data);
        }
    }
    public static class Node {
        public Node(Node leftChild, Node rightChild, Node parent, Integer data) {
            this.leftChild = leftChild;
            this.rightChild = rightChild;
            this.parent = parent;
            this.data = data;
        }
        public Node leftChild;
        public Node rightChild;
        public Node parent;
        public Integer data;
    }
}