BSTのn番目のアイテムを取得する

Question

BSTのn番目のアイテムに保持されているデータを返そうとしていますが、カウンタでインオーダートラバーサルを実行しようとしています。カウンタがnより大きい場合は、ノード。私の現在のコードは、常に最初の項目を返すようだ、私は私の論理が間違っているのか分からない。私はn番目と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)); 
    } 
} 

Answer 1

n = sizeOfLeftSubtree + 1のときは、そのノードを返してください。 nが小さければ左に行く。 nが大きければ、右に進み、sizeOfLeftSubtree + 1でnを減らします。最初の要素（一番左の要素）にn = 1をマッピングすることに注意してください。

サブツリーのサイズを再帰的に計算したり、すべてのルート（すべてのノードがサブツリーのルート）にサイズを格納することができます。挿入メソッドを変更する（スタック/キューにすべてのノードを保存し、if新しいノードが追加され、すべてのサイズが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); 
} 

Answer 2

inOrderメソッドではnodeを変更しません。

public BTNode inOrder(BTNode<Integer> node, int n) { 
    c++; 
    while (c <= n) { 
     if (node.left != null) { 
      // **** Add this - or something. 
      node = inOrder(node.left, n); 
     } 
     c++; 
     if (node.right != null) { 
      // **** Add this - or something. 
      node = inOrder(node.right, n); 
     } 
    } 
    return node; 
} 

修正するバグはありませんが、明らかにコードに問題があります。