我想返回BST的第n個項目所持有的數據,我試圖用計數器執行inorder遍歷,並且當計數器大於n時,返回當前節點。我目前的代碼似乎總是返回第一項,我看不到我的邏輯錯在哪裏。我只寫了第n個和inOrder方法,其餘的都提供了。我認爲我經常增加櫃檯,是原因還是我做錯了什麼。我會在下面發佈我正在測試的主要方法。獲取BST的第n個項目
import java.util.NoSuchElementException;
public class BST {
private BTNode<Integer> root;
public BST() {
root = null;
}
public boolean insert(Integer i) {
BTNode<Integer> parent = root, child = root;
boolean goneLeft = false;
while (child != null && i.compareTo(child.data) != 0) {
parent = child;
if (i.compareTo(child.data) < 0) {
child = child.left;
goneLeft = true;
} else {
child = child.right;
goneLeft = false;
}
}
if (child != null)
return false; // number already present
else {
BTNode<Integer> leaf = new BTNode<Integer>(i);
if (parent == null) // tree was empty
root = leaf;
else if (goneLeft)
parent.left = leaf;
else
parent.right = leaf;
return true;
}
}
public int greater(int n) {
if (root == null) {
return 0;
}
else {
return n;
}
}
int c = 0;
public int nth(int n) throws NoSuchElementException {
BTNode<Integer> node = null;
if (root == null) {
throw new NoSuchElementException("Element " + n + " not found in tree");
}
else {
if (root != null){
node = inOrder(root, n);
}
}
return node.data;
}
public BTNode inOrder(BTNode<Integer> node, int n) {
c++;
while (c <= n) {
if (node.left != null) {
inOrder(node.left, n);
}
c++;
if (node.right != null) {
inOrder(node.right, n);
}
}
return node;
}
}
class BTNode<T> {
T data;
BTNode<T> left, right;
BTNode(T o) {
data = o;
left = right = null;
}
}
public class bstTest {
public static void main(String[] args) {
BST tree = new BST();
tree.insert(2);
tree.insert(5);
tree.insert(7);
tree.insert(4);
System.out.println(tree.nth(2));
}
}
每次調用方法時都會修改一個字段,所以是的。增加太頻繁 –
我不想增加,直到我在最左邊的項目權利?然後每次我調用該方法時我都會增加它?所以我可以添加如果node.left爲空然後遞增c。我在那裏走正確的路嗎? – Chaz