使用指针增强技术时 BST rRemove(BSTNode<T> current, T data, BSTNode<T> dummy) 的递归方法问题

Question

这是节点 class:

public class BSTNode<T extends Comparable<? super T>> {

private T data;
private BSTNode<T> left;
private BSTNode<T> right;

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

T getData() {
    return data;
}

BSTNode<T> getLeft() {
    return left;
}

BSTNode<T> getRight() {
    return right;
}

void setData(T data) {
    this.data = data;
}

void setLeft(BSTNode<T> left) {
    this.left = left;
}

void setRight(BSTNode<T> right) {
    this.right = right;
}

}

这是我的 BST class 主要驱动方法：

import java.util.NoSuchElementException;

public class BST<T extends Comparable<? super T>> {

private BSTNode<T> root;
private int size;

BST() {
    root = null;
}

public void add(T data) {
    if (data == null) {
        throw new IllegalArgumentException("Error: Data can't be null");
    }
    root = rAdd(root, data);
}

private BSTNode<T> rAdd(BSTNode<T> current, T data) {
    if (current == null) {
        size++;
        return new BSTNode<T>(data);
    } else if (data.compareTo(current.getData()) < 0) {
        current.setLeft(rAdd(current.getLeft(), data));
    } else if (data.compareTo(current.getData()) > 0) {
        current.setRight(rAdd(current.getRight(), data));
    }
    return current;
}

public T remove(T data) {
    if (data == null) {
        throw new IllegalArgumentException("Error: data can't be null");
    }
    BSTNode<T> dummy = new BSTNode<>(null);
    root = rRemove(root, data, dummy);
    return dummy.getData();
}

private BSTNode<T> rRemove(BSTNode<T> current, T data, BSTNode<T> dummy) {
    if (current == null) {
        throw new NoSuchElementException("Error: Data not present");
    } else if (data.compareTo(current.getData()) < 0) {
        current.setLeft(rRemove(current.getLeft(), data, dummy));
    } else if (data.compareTo(current.getData()) > 0) {
        current.setRight(rRemove(current.getRight(), data, dummy));
    } else {
        System.out.println("Data found ... ");
        dummy.setData(current.getData());
        size--;
        if (current.getRight() == null  && current.getLeft() == null) {
            if (current.equals(root)) {
                this.root = null;
            }
            return null;
        } else if (current.getLeft() != null) {
            return current.getLeft();
        } else if (current.getRight() != null) {
            return current.getRight();
        } else {
            BSTNode<T> dummy2 = new BSTNode<>(null);
            current.setRight(removeSuccessor(current.getRight(), dummy2));
            current.setData(dummy2.getData());
        }
    }
    return current;
}

private BSTNode<T> removeSuccessor(BSTNode<T> current, BSTNode<T> dummy) {
    if (current.getLeft() == null) {
        dummy.setData(current.getData());
        return current.getRight();
    } else {
        current.setLeft(removeSuccessor(current.getLeft(), dummy));
    }
}

public List<T> inorder(BSTNode<T> root) {
    ArrayList<T> inorderContents = new ArrayList<T>();
    if (root == null) {
        return inorderContents;
    }
    inorderR(inorderContents, root);
    return inorderContents;
}

private void inorderR(ArrayList<T> inorderContents, BSTNode<T> current) {
    if (current ==  null) {
        return;
    }
    inorderR(inorderContents, current.getLeft());
    inorderContents.add(current.getData());
    inorderR(inorderContents, current.getRight());
}
  
public BSTNode<T> getRoot() {
    // DO NOT MODIFY THIS METHOD!
    return root;
}


public int size() {
    // DO NOT MODIFY THIS METHOD!
    return size;
}

public static void main(String[] args) {       
    
    BST bst3 = new BST<>();

    bst3.add(1);
    bst3.add(0);
    bst3.add(5);
    bst3.add(4);
    bst3.add(2);
    bst3.add(3);

    System.out.println(bst3.inorder(bst3.getRoot() ));

    bst3.remove(1);
    System.out.println(bst3.inorder(bst3.getRoot() ));
    
}

}

我的 IDE (IntelliJ) 说我的 removeSuccessor(BSTNode current, BSTNode dummy) 方法缺少 return 语句，但我希望它递归到基本情况以加强未更改的节点.

因此，当我尝试从两个子节点中删除它时，它 return 为零，尽管一个子节点和零个子节点工作。

有人能告诉我我的两个子节点删除案例有什么问题吗？谢谢，斯珀林。

Answer 1

首先需要通过改变条件来修改if-else：

if (current.getLeft() != null && current.getRight() == null) {
            return current.getLeft();
        } else if (current.getRight() != null && current.getLeft() == null) {
            return current.getRight();
        }

而不是在 rRemove() 方法中没有 && 的第二个参数。

然后，使用这个：

private BSTNode<T> removeSuccessor(BSTNode<T> current, BSTNode<T> dummy) {
    if (current.getLeft() == null) {
        dummy.setData(current.getData());
        return current.getRight();
    } else {
        current.setLeft(removeSuccessor(current.getLeft(), dummy));
        return current;
    }
}

该方法的含义如下：删除树中的最低值和return新根，并使用dummy记住该值。

如果我们在左边什么也没有得到，那是微不足道的 - 我们删除当前节点，return getRight() 并将值设置为 dummy。

另一方面，如果我们得到左边的东西，那么我们知道当前节点将是根，但在我们 return 它之前，我们需要删除左边最低的条目，并且所以我们递归地使用该函数，同时将 current.left 设置为它的 return 值以正确转换树。我们传递 dummy 以便它可以在第一个 case 发生时获得一个值，然后将它传递给最高调用（在第一个函数内）。

不用递归也可以做到：

private BSTNode<T> removeSuccessor2(BSTNode<T> current, BSTNode<T> dummy) {
    BSTNode<T> root = current;
    BSTNode<T> prev = null;
    while(current.getLeft() != null) {
        prev = current;
        current = current.getLeft();
    }
    /* current.getLeft == null */
    //we will delete current
    
    if (prev == null) { //no loop iterations -- current is the root
        dummy.setData(current.getData());
        return(current.getRight()); 
    }
    else {//some iterations passed, prev.getLeft() == curret
        dummy.setData(current.getData());
        prev.setLeft(current.getRight());
        return root;
    }
}

有了 dummy 我们 return 值，剩下的就是转换树。

注意：它在我的版本中不适用于 current == null。不过，您应该能够轻松修改它。另外，为了清楚起见，我没有在 if...else 等之前拉 dummy.setData...。根据需要修改它！

使用指针增强技术时 BST rRemove(BSTNode<T> current, T data, BSTNode<T> dummy) 的递归方法问题

Problem with recursive method for BST rRemove(BSTNode<T> current, T data, BSTNode<T> dummy) when using pointer reinforcement technique

java

data-structures

binary-search-tree