java - Java二叉树节点删除问题

Question

我想尝试实现我自己的 BST 作为练习，但我陷入了节点删除的困境。我不明白为什么它在某些情况下不起作用。我从一本书上获取了该算法，但是当我用随机元素测试它时，在某些情况下它不会删除元素，甚至会打乱它们的顺序，因此它们不再排序。我做错了什么以及实现此目标的更好方法是什么？

注意:方法中的所有 println() 语句仅用于调试目的

class TreeNode<T extends Comparable<T>> {
    T data;
    TreeNode<T> left;
    TreeNode<T> right;
    TreeNode<T> parent;

    TreeNode(T data) {
        this.data = data;
    }

    boolean hasBothChildren() {
        return hasLeftChild() && hasRightChild();
    }

    boolean hasChildren() {
        return hasLeftChild() || hasRightChild();
    }

    boolean hasLeftChild() {
        return left != null;
    }

    boolean hasRightChild() {
        return right != null;
    }

    boolean isLeftChild() {
        return this.parent.left == this;
    }

    boolean isRightChild() {
        return this.parent.right == this;
    }
}

public class BinaryTreeSet<T extends Comparable<T>> {
    private TreeNode<T> root;

    private void makeRoot(T element) {
        TreeNode<T> node = new TreeNode<T>(element);
        root = node;
    }

    private TreeNode<T> find(T element) {
        TreeNode<T> marker = root;
        TreeNode<T> found = null;

        while (found == null && marker != null) {
            int comparator = (marker.data.compareTo(element));

            if (comparator > 0)
                marker = marker.left;
            else if (comparator < 0)
                marker = marker.right;
            else
                found = marker;
        }

        return found;
    }

    private TreeNode<T> max(TreeNode<T> root) {
        TreeNode<T> currentMax = root;

        while (currentMax.hasRightChild()) {
            currentMax = currentMax.right;
        }

        return currentMax;
    }

    // returns the inorder predecessor of node
    private TreeNode<T> predecessor(TreeNode<T> node) {
        return max(node.left);
    }

    // removes a given node with 0 or 1 children
    private void removeNode(TreeNode<T> node) {
        if (!node.hasChildren()) {
            System.out.println("node with no children");
            if (node.isLeftChild())
                node.parent.left = null;
            else
                node.parent.right = null;
        }
        else {
            System.out.println("node with 1 child");
            if (node.isRightChild()) {
                if (node.hasLeftChild())
                    node.parent.right = node.left;
                else if (node.hasRightChild())
                    node.parent.right = node.right;
            }
            else if (node.isLeftChild()) {
                if (node.hasLeftChild())
                    node.parent.left = node.left;
                else if (node.hasRightChild())
                    node.parent.left = node.right;
            }
        }

        node = null;
    }

    public BinaryTreeSet() {
        root = null;
    }

    public void addElement(T element) {
        if (root == null)
            makeRoot(element);
        else {
            TreeNode<T> marker = root;
            TreeNode<T> node = new TreeNode<T>(element);
            boolean done = false;

            while(!done) {
                int comparator = marker.data.compareTo(element);
                if (comparator > 0) {
                    if (marker.hasLeftChild())
                        marker = marker.left;
                    else {
                        marker.left = node;
                        done = true;
                    }
                }
                else if (comparator < 0) {
                    if (marker.hasRightChild())
                        marker = marker.right;
                    else {
                        marker.right = node;
                        done = true;
                    }
                }
                else
                    return;

                node.parent = marker;
            }
        }
    }

    public boolean contains(T element) {
        boolean found = (find(element) == null)? false : true;
        return found;
    }

    public boolean removeElement(T element) {
        TreeNode<T> node = find(element);
        if (node == null)
            return false;

        // removal of a node with no children
        if (!node.hasChildren()) {
            if (node.isLeftChild()) {
                node.parent.left = null;
            }
            else if (node.isRightChild()) {
                node.parent.right = null;
            }
        }

        // removal of a node with both children
        else if (node.hasBothChildren()) {
            TreeNode<T> pred = predecessor(node);
            T temp = pred.data;
            pred.data = node.data;
            node.data = temp;
            removeNode(pred);
        }

        // removal of a node with only 1 child
        else {
            if (node.isRightChild()) {
                if (node.hasLeftChild())
                    node.parent.right = node.left;
                else if (node.hasRightChild())
                    node.parent.right = node.right;
            }
            else if (node.isLeftChild()) {
                if (node.hasLeftChild())
                    node.parent.left = node.left;
                else if (node.hasRightChild())
                    node.parent.left = node.right;
            }

        }

        node = null;
        System.out.println("item removed: " + !contains(element));
        return true;
    }
}

Answer 1

请将以下方法添加到 BinaryTreeSet 类中并调用它， 这将显示带有左/右前缀的当前元素列表。

 boolean rootOncePrint = true;
    public void printAllTree(TreeNode<T> startNode){
        if(startNode == null) return;
        //System.out.println(startNode.data);
        if(rootOncePrint){
            System.out.println("Root : " + startNode.data);
            rootOncePrint = false;
        }

        if(startNode.hasChildren()){
            if(startNode.hasLeftChild()){
                printAllTree(startNode.left);
            } 
            if(startNode.hasRightChild()){
                printAllTree(startNode.right);
            }

        }
        if(startNode != root){
            T parentValue = startNode.parent.data;
            T dataValue = startNode.data; 
            System.out.println(startNode.data + ((parentValue.compareTo(dataValue) > 0)?"L":"R"));
        }

    }

After Add this code, try to add/remove element into BinaryTreeSet so you will get to know what's going on.