删除泛型类型二叉搜索树的方法导致堆栈溢出问题

Question

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

我已经实现了泛型类型的二叉搜索树。

我已经学习了二叉搜索树删除算法，并且我尝试处理父节点具有“0子节点”，“1子项”或“2个子项”的3种情况。

我实现代码以删除节点，但不断导致堆栈溢出问题，并且我无法在代码中找到错误的地方。

任何帮助将不胜感激。

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();

                }

Answer 1

您的条件有问题。它们应该是：&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(compare&nbsp;<&nbsp;0)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;current&nbsp;=&nbsp;current.get_left(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;else&nbsp;if(compare&nbsp;>&nbsp;0)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;current&nbsp;=&nbsp;current.get_right(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;else&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;...就像现在一样，如果 是 ，则同时执行子句和子句。compare < 0truecurrent = current.get_left();else不过，我不确定这是你的方法的唯一问题。remove