我试图返回BST的第n个项所保存的数据,并试图使用一个计数器进行有序遍历,当计数器大于n时,返回当前节点。我当前的代码似乎总是返回第一项,而我看不出我的逻辑错在哪里。我只写了nth和inOrder方法,其余的都提供了。我想我经常增加计数器,是原因还是我做错了其他事情。我还将在下面发布要测试的主要方法。
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));
}
}
最佳答案
您应该考虑的不变因素是,当n = sizeOfLeftSubtree + 1时,则返回该节点。如果n小于,则向左走。如果n更大,则向右移动并通过sizeOfLeftSubtree + 1减小n。请注意,我将n = 1映射到第一个元素(最左边的元素)。
您可以递归地计算子树的大小,或者可以将大小存储在每个根目录下(每个节点都是子树的根目录),从而修改插入方法(保存在堆栈中/排队访问的所有节点以及是否有新的节点只需将所有大小增加1)。
如果存储了大小,则复杂度将为O(log n)。如果不是,则可能变为O(n ^ 2)。
public int nth(int n) throws NoSuchElementException {
if( sizeOfTree(this.root) < n || n < 1)
throw new NoSuchElementException("Element " + n + " not found in tree");
BTNode<Integer> root = this.root;
boolean found = false;
do{
int sizeOfLeftSubtree = sizeOfTree(root.left);
if( sizeOfLeftSubtree + 1 == n ){
found = true;
}else if( n < sizeOfLeftSubtree+1 ){
root = root.left;
}else if( sizeOfLeftSubtree+1 < n ){
root = root.right;
n -= sizeOfLeftSubtree+1;
}
}while( !found );
return root.data;
}
public int sizeOfTree(BTNode<Integer> root){
if( root == null )
return 0;
else
return sizeOfTree(root.left) + 1 + sizeOfTree(root.right);
}