Funktion, die den k-ten Wert in binärer Suchbaum zurückgibt

Question

Ich brauche eine Funktion zu schreiben, die die k-i-te Wert in seiner Größe

in binärer Suchbaum zurückgibt zB wenn dies der binäre Suchbaum:

        50 
           /\ 
           46 58 
          /\ /\ 
          32 48 53 67 

dann, wenn k = 3, so sollte die Funktion 48

zurück, weil 48 in dem dritten Platz in seiner Größe ist.

32,46,48,50,53,58,67.

Meine Idee ist, irgendwie inorder zu verwenden, aber ich stecke viele Stunden fest, ich denke nicht, dass es schwer sein sollte, ich brauche einen Pseudocode oder einen besseren Code als meins bitte.

hier ist das, was ich in JAVA Eclipse tat

private static void k_val_inorder(TreeItem x,int k) 
{  
    if (x != null&&k!=0) 
    { 
     k_val_inorder(x.getLeft(),k--); 
     System.out.print(x.getKey()+" "); 
     k_val_inorder(x.getRight(),k--);   
    } 

} 

irgendwelche Ideen bitte?

Answer 1

Gegeben TreeNode Klasse einen binären Baum zu implementieren:

public class TreeNode { 
    int data; 
    TreeNode left; 
    TreeNode right; 

    TreeNode(int data) { 
     this.data = data; 
    } 
} 

Infix Traversal für einen bestimmten binären Baum:

public void inFix(TreeNode root, List<Integer> inFixRep) { 
    if (root != null) { 
     inFix(root.left, inFixRep); 
     inFixRep.add(root.data); 
     inFix(root.right, inFixRep); 
    } 
} 

Das obige Verfahren ein List<Integer> auffüllt. Diese Liste enthält die Infix-Darstellung des angegebenen Binärbaums. Um den k-ten Knoten zu erhalten, rufen Sie einfach das (k-1) -te Element der Liste wie inFixRep.get(k-1).

Answer 2

In Ordnung funktioniert, ist aber linear, dies kann in log (n) Zeit erreicht werden. Wenn Sie die Anzahl der im Teilbaum des Knotens enthaltenen Knoten überwachen, können Sie eine Funktion so einrichten, dass sie in logarithmischer Zeit ausgeführt wird. In Python, sieht es wie folgt aus:

def select(node, k): 
    if node == null: 
     return null 
    t = node.left == null ? 0 : node.count 
    if t > k: 
     return select(node.left, k) 
    if t < k: 
     return select(node.right, k-t-1) 
    return node.data 

EDIT:

Es in log arbeitet (n) Zeit für eine ausgewogene Baum, aber mit Standard BST das Worst-Case-Zeit ist immer noch linear. Trotzdem ist es im Durchschnitt schneller als in Ordnung.