public class SearchBinaryTree {

    private static class TreeNode {

        private int data;
        private TreeNode leftNode;
        private TreeNode rightNode;
        private TreeNode parentNode;

        public TreeNode(int data, TreeNode parentNode) {
            this.data = data;
            this.parentNode = parentNode;
        }

        @Override
        public String toString() {
            return "TreeNode [data=" + data + ", leftNode=" + (leftNode != null ? leftNode.data : null) + ", rightNode="
                    + (rightNode != null ? rightNode.data : null) + ", parentNode="
                    + (parentNode != null ? parentNode.data : null) + "]";
        }
    }

    private TreeNode rootNode;

    public TreeNode put(int data) {
        if (rootNode == null) {
            rootNode = new TreeNode(data, null);
            return rootNode;
        }
        TreeNode node = rootNode;
        if (data == node.data) {
            return node;
        }
        TreeNode parentNode = null;
        while (node != null) {
            parentNode = node;
            if (data > node.data) {
                node = node.rightNode;
            } else {
                node = node.leftNode;
            }
        }
        node = new TreeNode(data, parentNode);
        if (node.data < parentNode.data) {
            parentNode.leftNode = node;
        } else {
            parentNode.rightNode = node;
        }
        return node;
    }

    public void removeNode(int data) {
        TreeNode node = findNode(data);
        if (node == null) {
            return;
        }
        TreeNode parentNode = node.parentNode;
        // 删除的是root节点
        if (parentNode == null) {
            if (node.rightNode != null) {
                rootNode = node.rightNode;
                rootNode.parentNode = null;
            } else if (node.leftNode != null) {
                rootNode = node.leftNode;
                rootNode.parentNode = null;
            } else {
                rootNode = null;
            }
        }
        // 找出删除节点右树中最小的节点
        TreeNode minimumNode = findMinimumNode(node.rightNode);
        // 如果含有该最小节点，则该最小节点的左树节点为null
        if (minimumNode != null) {
            // 如果有左节点，将其挂载到这个最小节点上
            if (node.leftNode != null) {
                minimumNode.leftNode = node.leftNode;
                node.leftNode.parentNode = minimumNode;
            }
            if (parentNode != null) {
                if (node.data < parentNode.data) {
                    // 删除的是左树节点
                    parentNode.leftNode = node.rightNode;
                    node.rightNode.parentNode = parentNode;
                } else {
                    // 删除的是右树节点
                    parentNode.rightNode = node.rightNode;
                    node.rightNode.parentNode = parentNode;
                }
            }
        } else if (node.leftNode != null) {
            // 只有左树节点
            if (parentNode != null) {
                parentNode.leftNode = node.leftNode;
                node.leftNode.parentNode = parentNode;
            }
        } else {
            // 没有子节点
            if (parentNode != null) {
                if (node.data < parentNode.data) {
                    // 删除的是左树节点
                    parentNode.leftNode = null;
                } else {
                    // 删除的是右树节点
                    parentNode.rightNode = null;
                }
            }
        }
        node.parentNode = null;
        node.leftNode = null;
        node.rightNode = null;
    }

    private TreeNode findMinimumNode(TreeNode node) {
        TreeNode parentNode = node;
        while (node != null) {
            parentNode = node;
            node = node.leftNode;
        }
        return parentNode;
    }

    public TreeNode findNode(int data) {
        TreeNode node = rootNode;
        while (node != null) {
            if (data < node.data) {
                node = node.leftNode;
            } else if (data > node.data) {
                node = node.rightNode;
            }
            if (node == null || node.data == data) {
                break;
            }
        }
        return node;
    }

    // 中序遍历所有数据，会从小到大排序
    public static void midPrint(TreeNode node) {
        if (node == null) {
            return;
        }
        midPrint(node.leftNode);
        System.out.print(node.data + " ");
        midPrint(node.rightNode);
    }

    public static void main(String[] args) {
        SearchBinaryTree binaryTree = new SearchBinaryTree();
        int[] dataArray = new int[] { 10, 23, 42, 5, 1, 20, 22, 34, 25, 90, 14, 60 };
        for (int data : dataArray) {
            binaryTree.put(data);
        }
        SearchBinaryTree.midPrint(binaryTree.rootNode);
        System.out.println();
        TreeNode node = binaryTree.findNode(1);
        System.out.println(node.toString());
        for (int data : dataArray) {
            binaryTree.removeNode(data);
            SearchBinaryTree.midPrint(binaryTree.rootNode);
            System.out.println();
        }
    }
}