泛型二叉搜索树的remove方法导致栈溢出问题

Question

我遇到了关于为泛型二叉搜索树实现删除方法的实验问题。

我实现了泛型二叉搜索树。

我学习了二叉搜索树移除算法，我尝试处理3种情况parent节点有“0child”，“1child”或“2 child仁”.

我实现了删除节点的代码，但一直导致堆栈溢出问题，我找不到我的代码哪里出错了。

任何帮助将不胜感激。

public class BinarySearchTree<T extends Comparable<T>> {

    private Node<T> _root; //Root node

    public class Node<T extends Comparable<T>> {
        public T get_value() {return _value;}

        public void set_value(T _value) {this._value = _value;}

        public Node<T> get_left() {return _left;}

        public void set_left(Node<T> _left) {this._left = _left;}

        public Node<T> get_right() {return _right;}

        public void set_right(Node<T> _right) {this._right = _right;}

        public Node<T> get_parent() {return _parent;}

        public void set_parent(Node<T> _parent) {this._parent = _parent;}

        T _value;           // Node value
        Node<T> _left;      // Left child

        Node<T> _right;     // Right child
        Node<T> _parent;    // Parent node

        public Node(T key, Node<T> parent, Node<T> left, Node<T> right) {
            _value = key;
            _left = left;
            _right = right;
            _parent = parent;
        }
    }
    // Remove a node from the BST
    private Node<T> remove(BinarySearchTree<T> bst, Node<T> z) {
        Node<T> delNode = null;
        if(bst._root == null){
            delNode = null;
        }
        else{
            Node<T> current = bst._root;
            // find the position to delete
            while(current!=null){
                int compare = z.get_value().compareTo(current.get_value());
                if(compare < 0){
                    current = current.get_left();
                }
                if(compare > 0){
                    current = current.get_right();
                }
                else{
                  // if node has two child,replace it with right minimum value
                    if (current._left!=null && current._right!=null){
                        delNode = current;
                        Node<T> successor = minimumKey(current.get_right());
                        current.set_value(successor.get_value());
                        remove(successor._value);
                    }
                    if (current._left!=null){
                        delNode = current;
                        remove(current._value);
                        current._left.set_parent(current._parent);
                    }
                    if (current._right!=null){
                        delNode = current;
                        remove(current._value);
                        current._right.set_parent(current._parent);
                    }
                    else{
                        delNode = current;
                        remove(current._value);
                    }
                }
            }

        }


        return delNode;

    }
    // remove a node value
    public void remove(T key) {
        Node<T> z, node;
        if ((z = find(_root, key)) != null)
            if ( (node = remove(this, z)) != null)
                node = null;
    }
    public Node<T> minimumKey(Node<T> current) {
        while (current._left != null) {
            current = current._left;
        }
        return current;
    }
}

Answer 1

您的条件有问题。他们应该是：

        if(compare < 0) {
            current = current.get_left();
        } else if(compare > 0) {
            current = current.get_right();
        } else {
            ...

就像现在一样，如果 compare < 0 是 true，您将同时执行 current = current.get_left(); 和 else 子句。

不过，我不确定这是您 remove 方法的唯一问题。

泛型二叉搜索树的remove方法导致栈溢出问题

remove method for generic type binary search tree result in stack overflow problem

java

stack-overflow

generic-type-argument

binary-search-tree