java - 递归二叉搜索树删除

Question

注意:我已经包含了用于插入的代码，以防这是我的错误所在。

我在删除二叉搜索树中的节点时遇到问题。我通过 eclipse 运行它，节点的“指针”似乎被重新分配，但是一旦我退出我的递归方法，它就会回到节点的状态。

我可能误解了 java 如何在方法之间传递树节点。

public abstract class BinaryTree<E> implements Iterable<E> {

    protected class Node<T> {

        protected Node(T data) {
            this.data = data;
        }

        protected T data;
        protected Node<T> left;
        protected Node<T> right;
    }

    public abstract void insert(E data);
    public abstract void remove(E data);
    public abstract boolean search(E data);

    protected Node<E> root;
}

import java.util.Iterator;

public class BinarySearchTree<E extends Comparable<? super E>> extends BinaryTree<E> {

    private Node<E> findIOP(Node<E> curr) {

        curr = curr.left;

        while (curr.right != null) {
            curr = curr.right;
        }

        return curr;
    }

public Iterator<E> iterator() {

    return null;
}

public static void remove(E data) {

    if (root != null){

         if (data.compareTo(root.data) == 0) {

            if (root.left == null || root.right == null) {

                root = root.left != null ? root.left : root.right;


            } else {

                Node<E> iop = findIOP(root);
                E temp = root.data;
                root.data = iop.data;
                iop.data = temp;

                if (root.left == iop) {

                    root.left = root.left.left;

                } else {

                    Node<E> curr = root.left;

                    while (curr.right != iop) {
                        curr = curr.right;
                    }
                    curr.right = curr.right.left;
                }
            }

        } else {

             if (data.compareTo(root.data) < 0) {

                remove(root.left ,data);

             } else {

                remove(root.right ,data);

             }
        }

    }
}

private void remove (Node<E> node, E data){

     if (data.compareTo(node.data) == 0) {

        if (node.left == null || node.right == null) {


            if (node.left != null) {
                                    // Problem is either here
                node = node.left;

            } else {
                                    // or here
                node = node.right;
            }


        } else {

            Node<E> iop = findIOP(node);
            E temp = node.data;
            node.data = iop.data;
            iop.data = temp;

            if (node.left == iop) {

                node.left = node.left.left;

            } else {

                Node<E> curr = node.left;

                while (curr.right != iop) {
                    curr = curr.right;
                }
                curr.right = curr.right.left;
            }
        }
    } else {

         if (data.compareTo(node.data) < 0) {

            remove(node.left ,data);

         } else {

            remove(node.right ,data);

         }
    }

}

}

当我插入时:

tree.insert(10);
tree.insert(15);
tree.insert(6);
tree.insert(8);
tree.insert(9);

然后

tree.remove(8);

System.out.println(tree.root.left.right.data);

仍然是 8 而不是 9。

删除工作在根目录，如果从中删除，指针会被正确地重新分配root.left 和 root.right。

如有任何建议，我们将不胜感激。

编辑:我似乎缩小了问题范围。我实现了一个迭代版本，其中我使 root = curr 并更改 curr.left.right = curr.left.right.right。我注意到此更改反射(reflect)了我的根节点，而当我将 node = root.left.right 传递给我的递归函数时，将节点更改为 node.right 并不反射(reflect)根中的更改。这是为什么？

进一步缩小范围。为什么 node.left = node.left.left 对我的树进行更改而 node = node.left 什么都不做。

我通过递归地重新分配父节点而不是递归地重新分配子节点来修复它。这是由此产生的私有(private)和公共(public)函数。

public void remove(E data) {

    Node<E> curr;

    if (root != null) {
        if (data.compareTo(root.data) == 0) {
            if (root.left == null || root.right == null) {
                root = root.left != null ? root.left : root.right;
            }
            else {
                Node<E> iop = findIOP(root);
                E temp = root.data;
                root.data = iop.data;
                iop.data = temp;
                if (root.left == iop) {
                    root.left = root.left.left;
                }
                else {
                    curr = root.left;
                    while (curr.right != iop) {
                        curr = curr.right;
                    }
                    curr.right = curr.right.left;
                }
            }
        } else if (data.compareTo(root.data) < 0) {
            root.left = remove(data, root.left);
        } else {
            root.right = remove(data, root.right);
        }
    }
}

private Node<E> remove(E data, Node<E> node){

    Node<E> curr;

    if (node != null){
        if (data.compareTo(node.data) == 0) {
            if (node.left == null || node.right == null) {
                node = node.left != null ? node.left : node.right;
                return node;
            } else {

                Node<E> iop = findIOP(node);
                E temp = node.data;
                node.data = iop.data;
                iop.data = temp;
                if (node.left == iop) {
                    node.left = node.left.left;
                    return node;
                } else {
                    curr = node.left;
                    while (curr.right != iop) {
                        curr = curr.right;
                    }
                    curr.right = curr.right.left;
                    return node;
                }
            }
        } else {
            if (data.compareTo(node.data) < 0) {
                node.left = remove(data, node.left);
                if (node.left != null){
                    return node.left;
                }
            } else {
                node.right = remove(data, node.right);
                if (node.right != null){
                    return node.right;
                }
            }
            // if node.left/right not null
            return node;
        }
    }
    // if node = null;
    return node;
}

Answer 1

当您说“我可能误解了 java 如何在方法之间传递树节点”时，您确实是对的。考虑:

public class Ref {
    public static void main(String args[]) {
        Integer i = new Integer(4);
        passByRef(i);
        System.out.println(i);    // Prints 4.
    }

    static void passByRef(Integer j) {
        j = new Integer(5);
    }
}

虽然 i 是“通过引用传递”，但引用 i 本身 并没有被该方法改变，只有 j 指的是。换句话说，j 是用引用 i 的副本初始化的，也就是说，j 最初指的是与 相同的对象i(但关键不是 i)。分配 j 来引用其他内容不会影响 i 所引用的内容。

为了在搜索中实现您想要的结果，我建议您改为将新引用返回给调用者。例如，类似于以下更改的内容:

public class Ref {
    public static void main(String args[]) {
        Integer i = new Integer(4);
        i = passByRef(i);
        System.out.println(i);    // Prints 5.
    }

    static Integer passByRef(Integer j) {
        j = new Integer(5);
        return j;
    }
}