метод удаления для бинарного дерева поиска универсального типа приводит к проблеме переполнения стека - PullRequest
Новая
       23

метод удаления для бинарного дерева поиска универсального типа приводит к проблеме переполнения стека

2 голосов
/ 28 марта 2019

Я столкнулся с этой лабораторной проблемой, связанной с реализацией метода удаления для дерева двоичного поиска универсального типа.

Я реализовал двоичное дерево поиска универсального типа.

Я изучил алгоритм удаления дерева двоичного поиска, и я пытаюсь разобраться с 3 случаями, когда родительский узел имеет «0 дочерних элементов», «1 дочерний элемент» или «2 дочерних элемента».

Я реализую код для удаления узла, но он продолжает вызывать проблему переполнения стека, и я не могу найти, где что-то не так в моем коде.

Любая помощь будет оценена. 

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;
    }
}

1 Ответ

2 голосов
/ 28 марта 2019

У вас проблема с вашими условиями. Они должны быть: 

        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 методом.

...