Tree

package structure;

public class Tree {
    private Node root;


    /**
     * 节点
     */
    class Node{
        public long value;

        public Node leftChild;

        public Node rightChild;

        public Node(long value){
            this.value = value;
        }

    }

    /**
     * 插入节点
     * @param value
     */
    public void insert(long value){
        Node node = new Node(value);
        if(root == null){
            root = node;
            return;
        }

        // 当前节点引用。插入思路：即和当前节点比较，大于当前节点的值走右边；小于当前节点的值走走边；改变current指向
        Node current = root;
        do{
            if(current.value > value){
                if(current.leftChild == null){
                    current.leftChild = node;
                    return;
                }
                current = current.leftChild;
            }else{
                if(current.rightChild == null){
                    current.rightChild = node;
                    return;
                }
                current = current.rightChild;
            }
        }while (true);

    }

    /**
     * 删除节点
     * @param value
     */
    public Node remove(long value){
        Node current = root;

        // 要删除节点的父节点
        Node parent = current;
        boolean isLeft = true;

        // 查到到需要删除的节点
        while(current.value != value){
            parent = current;

            // 找不到返回 false
            if(current == null){
                return null;
            }

            if(current.value > value){
                current = current.leftChild;
                isLeft = true;
            }else{
                current = current.rightChild;
                isLeft = false;
            }
        }

        // 1、如果删除的节点是叶子节点
        if(current.leftChild == null && current.rightChild == null){
            if(current == root){
                root = null;
            }

            if(isLeft){
                parent.leftChild = null;
            }else{
                parent.rightChild = null;
            }

            // 引用类型，直接将它置为 null 就可以了
            current = null;
        }

        // 2、左子树不为null，右子树为null
        else if(current.rightChild == null){
            if(current == root){
                root = current.leftChild;
            }

            if(isLeft){
                parent.leftChild = current.leftChild;
            }else{
                parent.rightChild = current.leftChild;
            }
        }

        // 3、左子树为null，右子树不为null
        else if(current.leftChild == null){
            if(current == root){
                root = current.rightChild;
            }

            if(isLeft){
                parent.leftChild = current.rightChild;
            }else{
                parent.rightChild = current.rightChild;
            }
        }

        // 4、左子树和右子树都不为空，需要查找中继后续,即右子树中最小的那个节点
        else {
            Node successor = getSuccessor(current);
            if(current == root){
                root = successor;
            }

            if(isLeft){
                parent.leftChild = successor;
            }else{
                parent.rightChild = successor;
            }
            successor.leftChild = current.leftChild;

        }

        return current;
    }

    /**
     * 获取中继后序节点
     * @param deleteNode
     * @return
     */
    private Node getSuccessor(Node deleteNode){
        Node successor = deleteNode;
        // 中继后序节点的父节点
        Node successorParent = successor;
        Node current = deleteNode.rightChild;

        while(current != null){
            successorParent = successor;
            successor = current;
            current = current.leftChild;
        }

        // 当右子树只有一个节点的时候，此时 successor == deleteNode.rightChild，不需要执行下面的逻辑
        if(successor != deleteNode.rightChild){
            // 中继后续节点有可能有rightChild， 但不可能有leftChild
            successorParent.leftChild = successor.rightChild;
            successor.rightChild = deleteNode.rightChild;
        }

        return successor;
    }

    /**
     * 查找节点
     * @param value
     * @return
     */
    public Node find(long value){
        Node current = root;

        while (current.value != value){
            if(current == null){
                return null;
            }

            if(current.value > value ){
                current = current.leftChild;
            }else{
                current = current.rightChild;
            }
        }

        return current;
    }

    /**
     * 前序遍历：根 --》 左 --》 右
     * @param localNode
     */
    public void frontOrder(Node localNode){
        if(localNode != null){
            // 访问根节点
            System.out.println(localNode.value);

            // 遍历左子树
            frontOrder(localNode.leftChild);

            // 遍历右子树
            frontOrder(localNode.rightChild);
        }
    }


    /**
     * 中序遍历：左 --》 根 --》 右
     * @param localNode
     */
    public void inOrder(Node localNode){
        if(localNode != null){
            // 遍历左子树
            inOrder(localNode.leftChild);

            // 访问根节点
            System.out.println(localNode.value);

            // 遍历右子树
            inOrder(localNode.rightChild);
        }
    }

    /**
     * 中序遍历：左 --》 右 --》 根
     * @param localNode
     */
    public void afterOrder(Node localNode){
        if(localNode != null){
            // 遍历左子树
            afterOrder(localNode.leftChild);

            // 遍历右子树
            afterOrder(localNode.rightChild);

            // 访问根节点
            System.out.println(localNode.value);
        }
    }


    public static void main(String[] args) {
        Tree tree = new Tree();
        tree.insert(2);
        tree.insert(1);
        tree.insert(7);
        tree.insert(5);
        tree.insert(4);
        tree.insert(6);
        tree.insert(10);
        tree.insert(8);
        tree.insert(11);
        tree.insert(9);


        // 查找
        Node node = tree.find(6);
        System.out.println("----------------------------------查找节点------------------------------------");
        System.out.println(node.value);

        // 前序遍历
        System.out.println("----------------------------------前序遍历------------------------------------");
        tree.frontOrder(tree.root);

        // 中序遍历
        System.out.println("----------------------------------中序遍历------------------------------------");
        tree.inOrder(tree.root);

        // 后序遍历
        System.out.println("----------------------------------后序遍历------------------------------------");
        tree.afterOrder(tree.root);

        // 删除节点
        System.out.println("----------------------------------删除节点------------------------------------");
        tree.remove(7);
        tree.inOrder(tree.root);

    }
}