我试图返回 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 更大,则向右将 n 减少 sizeOfLeftSubtree+1。请注意,我将 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);
}
关于java - 获取 BST 的第 n 项,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42229184/