Erste n-ten Element eines BST

Question

Ich versuche, die Daten durch die n-te Element eines BST gehalten zurückzukehren, Ich versuche, eine Inorder Traversal mit einem Zähler zu tun, und wenn der Zähler größer als n ist, geben Sie die aktuelle Knoten. Mein aktueller Code scheint immer den ersten Eintrag zurückzugeben, und ich kann nicht sehen, wo meine Logik falsch ist. Ich habe nur die nth- und inOrder-Methoden geschrieben, der Rest wurde bereitgestellt. Ich denke, dass ich meinen Zähler zu oft inkrementiere, ist das die Ursache oder mache ich etwas anderes falsch. Ich werde auch unten die Hauptmethode veröffentlichen, mit der ich gerade teste.

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

Eine unveränderliche man beachten sollte, ist, dass, wenn n = sizeOfLeftSubtree + 1, dann diesen Knoten zurück. Wenn n kleiner ist, dann gehe nach links. Wenn n größer ist, dann gehe nach rechts und reduziere n um sizeOfLeftSubtree + 1. Beachten Sie, dass ich n = 1 auf das erste Element (das Element ganz links) abbilde.

Sie könnten die Größe eines Unterbaums rekursiv berechnen, oder Sie können die Größe an jedem Stamm speichern (jeder Knoten ist ein Stamm eines Unterbaums), indem Sie die Einfügemethode ändern (Speichern in einem Stapel/Warteschlange aller besuchten Knoten und if) Wenn ein neuer Knoten hinzugefügt wird, erhöhen Sie einfach alle Größen um 1).

Wenn die Größe gespeichert ist, die Komplexität wird O (log n). Wenn nicht, könnte O (n^2) werden.

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

Sie nicht node im inOrder Methode ändern.

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; 
} 

Dies ist nicht der Fehler, den Sie versuchen zu beheben, aber es ist sicherlich ein Problem mit dem Code.