我正在嘗試在 BST 中實作插入方法，但遇到了一些問題。鑒于周圍的代碼：
public class BinarySearchTree<E> {
private BinaryNode<E> root;
private int size;
private Comparator<E> comparator;
/**
* Constructs an empty binary search tree, sorted according to the specified comparator.
*/
public BinarySearchTree(Comparator<E> comparator) {
root = null;
size = 0;
this.comparator = comparator;
}
private static class BinaryNode<E> {
private E element;
private BinaryNode<E> left;
private BinaryNode<E> right;
private BinaryNode(E element) {
this.element = element;
left = right = null;
}
}
//Other methods
}
我的實作有什么問題：
/**
* Inserts the specified element in the tree if no duplicate exists.
* @param x element to be inserted
* @return true if the the element was inserted
*/
public boolean add(E x) {
return add(root, x);
}
private boolean add(BinaryNode<E> n, E x) {
if(n == null) {
n = new BinaryNode<E> (x);
size ;
return true;
}
int compResult = comparator.compare(x, n.element);
if(compResult<0){
return add(n.left, x);
} else if(compResult>0) {
return add(n.right, x);
}else {
return false;
}
}
當測驗只插入一個元素時，我得到 null 作為根的回傳值，但我真的看不出哪里出了問題。謝謝您的幫助！
uj5u.com熱心網友回復：
當你分配
n = new BinaryNode<E> (x)
在add()你分配給一個區域變數。這不會將新節點添加到樹中；這樣就沒有從現有樹到新節點的參考。
有很多方法可以修復它，但這可能是您永遠不會看到root變化的原因null；你永遠不會在任何地方分配給它。
指標在這里會很好，它們可以更輕松地通過參考傳遞變數，但是在 Java 中，我認為您需要傳遞需要以其他方式放置新節點的位置。我已經有 20 年沒有使用過這種語言了，所以我不太確定。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/362057.html