漫画算法——二叉查找树的删除

public class FindTree {    private Node root;
    public Node search(int data) {        Node targetNode = root;        while (targetNode != null && targetNode.data != data) {            if (targetNode.data > data) {                targetNode = targetNode.left;            } else {                targetNode = targetNode.right;            }        }
        if (targetNode == null) {            System.out.println("未找到节点:" + data);        } else {            System.out.println("以找到节点:" + data);        }        return targetNode;    }
    public boolean insert(int data) {        Node node = new Node(data);        if (root == null) {            root = node;            return true;        }
        Node targetNode = root;        while (true) {            if (data == targetNode.data) {                System.out.println("二叉查找树中已有重复的节点：" + data);                return false;            } else if (data > targetNode.data) {                if (targetNode.right == null) {                    targetNode.right = node;                    return true;                }                targetNode = targetNode.right;            } else {                if (targetNode.left == null) {                    targetNode.left = node;                    return true;                }                targetNode = targetNode.left;            }        }    }
    public boolean delete(int data) {        if (root.data == data) {            root = removeNode(root);            return true;        } else if (root.data < data) {            return deleteRight(root, data);        } else {            return deleteLeft(root, data);        }
    }
    private boolean deleteRight(Node parent, int data) {        Node current = parent.right;        if (current == null) {            return false;        } else if (current.data == data) {            parent.right = removeNode(current);            return true;        } else if (current.data < data) {            return deleteRight(current, data);        } else {            return deleteLeft(current, data);        }    }
    private boolean deleteLeft(Node parent, int data) {        Node current = parent.left;        if (current == null) {            return false;        } else if (current.data == data) {            parent.left = removeNode(current);            return true;        } else if (current.data < data) {            return deleteRight(current, data);        } else {            return deleteLeft(current, data);        }    }
    //从移除节点的子节点选择一个作为新的根节点  // 根据该节点的情况分为三种  //1.没有子节点,直接返回null  //2.只有一个子节点,该子节点是新的根节点  //3.有两个子节点,由于构建的是二叉查找树,所以参考书上寻找下一个比该节点(NextNode)大的数值作为新的根节点   //(1)寻找该节点的逻辑:nextNode就等于node右子树的最左节点[直至该节点没有左节点]   //(2)nextNode.left=node.left   //(3)nextNode的现有右子树全部小于node的右子树,   //(4) 所以遍历该nextNode的右子树的最右节点[直至节点没有右子树]   //(5)将node的右子数挂载在最右节点的右节点   //(6)最右注意一点,nextNode是新的根节点,所以需要将该nextNode的父节点的左子树置空,否则会导致死循环      private Node removeNode(Node node) {        Node root = null;        ChildStatus childStatus = queryChildStatus(node);        switch (childStatus) {            case LEFT:                root = node.left;                break;            case RIGHT:                root = node.right;                break;            case ALL:                //查找一个稍大一点的值                Node nextRoot = node.right;                //把和上级的联系断掉                Node before = node;                while (nextRoot.left != null) {                    before = nextRoot;                    nextRoot = nextRoot.left;                }                before.left = null;                nextRoot.left = node.left;
                Node temp = node.right;                root = nextRoot;                Node findLarge = nextRoot;                while (findLarge.right != null) {                    findLarge = findLarge.right;                }                findLarge.right = temp;                break;            default:                break;        }        return root;    }
    private ChildStatus queryChildStatus(Node parent) {        if (parent.left == null) {            if (parent.right == null) {                return ChildStatus.NO;            } else {                return ChildStatus.RIGHT;            }        } else if (parent.right == null) {            return ChildStatus.LEFT;        } else {            return ChildStatus.ALL;        }    }
    @Override    public String toString() {        return toString(root);    }
    public String toString(Node root) {        StringBuilder builder = new StringBuilder();        append(root, builder);        return builder.toString();    }

    public void append(Node node, StringBuilder builder) {        if (node == null) {            return;        }        append(node.left, builder);        builder.append(node.data).append(",");        append(node.right, builder);    }
    public enum ChildStatus {        NO,        LEFT,        RIGHT,        ALL,        ;    }}

class FindTreeTest {
    @Test    public void testCase1() {        FindTree findTree = new FindTree();        int[] arr = {6, 3, 8, 2, 4, 7, 9, 1, 5};        for (int v : arr) {            findTree.insert(v);        }        System.out.println(findTree);    }
    @Test    public void testCase2() {        FindTree findTree = new FindTree();        int[] arr = {9, 5, 13, 2, 7, 11, 1, 3, 6, 8, 10, 12};        for (int v : arr) {            findTree.insert(v);        }        System.out.println(findTree);    }
    @Test    public void testCase3() {        FindTree findTree = new FindTree();        int[] arr = {9, 5, 13, 2, 7, 11, 1, 3, 6, 8, 10, 12};        for (int v : arr) {            findTree.insert(v);        }        System.out.println(findTree);        findTree.delete(12);        System.out.println(findTree);    }
    @Test    public void testCase4() {        FindTree findTree = new FindTree();        int[] arr = {9, 5, 13, 2, 7, 11, 1, 3, 6, 8, 10, 12};        for (int v : arr) {            findTree.insert(v);        }        System.out.println(findTree);        findTree.delete(13);        System.out.println(findTree);    }
    @Test    public void testCase5() {        FindTree findTree = new FindTree();        int[] arr = {9, 5, 13, 2, 7, 11, 1, 3, 6, 8, 10, 12};        for (int v : arr) {            findTree.insert(v);        }        System.out.println(findTree);        findTree.delete(5);        System.out.println(findTree);    }
    @Test    public void testCase6() {        FindTree findTree = new FindTree();        int[] arr = {9, 5, 13, 2, 7, 11, 1, 3, 6, 8, 10, 12};        for (int v : arr) {            findTree.insert(v);        }        System.out.println(findTree);        findTree.delete(9);        System.out.println(findTree);    }
}