Java-Programm, um das k-kleinste Element in einem BST zu finden

Question

Ich schreibe ein Java-Programm, um das k-kleinste Element in einem BST zu finden.

Ich habe einige andere Beiträge zu dieser Frage auf Stack-Überlauf gegangen und habe ihre Lösungen durchlaufen, aber ich kann nicht verstehen, was das Problem mit meinem Code ist. Wenn jemand könnte mir bitte sagen, warum mein Programm nichts druckt.

//Program to find the kth smallest element in the BST 
public class KthSmallestElement { 
static Node root; 
//method to insert a key 
Node insertRec(Node root, int key) 
{ 
    //if the tree is empty 
    if(root == null) 
    { 
     root = new Node(key); 
     return root; 
    } 
    //otherwise recur down the tree 
    else 
    { 
     if(key > root.key) 
     { 
      root.right = insertRec(root.right, key); 
     } 
     else 
     { 
      root.left = insertRec(root.left, key); 
     } 
     return root; 
    } 
} 

//This method is for calling the insertRec() method 
Node insert(int key) 
    { 
     root = insertRec(root, key); 
     return root; 
    } 

//This method is for doing the inorder traversal of the tree 
void kthSmallest(Node root, int k) 
{ 
    int counter = 0; 
    if(root == null) 
     return; 
    else 
    { 
      kthSmallest(root.left, k); 
      counter++; 

    if(counter == k) 
     { 
      System.out.println(root.key); 
     } 
     kthSmallest(root.right, k); 
    } 
}  

//main method 
public static void main(String[] args) 
{ 
    KthSmallestElement tree = new KthSmallestElement(); 
    Node root = null; 
    root = tree.insert(20); 
    root =tree.insert(8); 
    root =tree.insert(22); 
    root =tree.insert(4); 
    root= tree.insert(12); 
    root =tree.insert(10); 
    root =tree.insert(14); 
    tree.kthSmallest(root, 3); 
} 

} 

Und meine Knotenklasse ist wie folgt:

//Class containing left and right child of current node and key value 
public class Node { 
int key; 
Node left, right, parent; 

//Constructor for the node 
public Node(int item){ 
    key = item; 
    left = right = parent= null; 
} 

} 

Es ist das Problem nicht Druck anything.That ist. Ok, ich bin nicht so gut im Programmieren, bitte verzeih mir, dass du mir eine solche Frage gestellt hast.

Answer 1

Ihr Zähler k wird nicht immer aktualisiert, und counter hat method-scope und wird bei jedem rekursiven Aufruf ignoriert, wodurch das Problem verursacht wird. Sie müssen einen Zähler machen, die konsistent über alle Methodenaufrufe ist:

int kthSmallest(Node root , int k){ 
    //empty root, don't change counter 
    if(root == null) 
     return k; 
    else { 
     //update counter - equivalent to k -= root.left.size() 
     k = kthSmallest(root.left, k); 

     if(k == 0) //kth element 
     { 
      System.out.println(root.key); 
      return -1; //return some invalid counter 
     } 

     //currently visited node 
     k--; 

     //search right subtree 
     return kthSmallest(root.right, k); 
    } 
} 

Dieser Code k als Zähler verwendet und zählt rückwärts k-0 und gibt den Knoten, für die k dreht 0.

Ihr Code funktioniert nicht, da counter einen methodenlokalen Gültigkeitsbereich hat. Dies bedeutet, dass der Wert counter nur für den aktuellen Anruf von kthSmallest gültig ist. Beim nächsten rekursiven Anruf wird counter auf 0 gesetzt - beachten Sie, dass dies ein weiterercounter im Speicher ist, als der aus dem vorherigen Anruf - und somit kann Ihr Code counter == k nicht erreichen, es sei denn k == 1.

Für diesen Baum:

        1 
           / \ 
           2  3 

Eine Darstellung des Programmablaufs wie folgt aussehen würde, für k > 1:

//i'll apply IDs to uniquely identify each function-call and 
// it's corresponding variables. the suffix #<Uppercase Letter> 
// is used to identify a variable by corresponding method-call 

kthElement(n , k): #A 
| counter#A = 0 //initialize counter 
| 
| kthElement(n.left , k): #B 
| | counter#B = 0 
| | 
| | kthElement(n.left.left , k): #C 
| | | counter#C = 0 
| | | n.left.left == null -> return from #D 
| | 
| | counter#B++ -> counter#B = 1 
| | 
| | counter#B != k -> don't print 
| | 
| | kthElement(n.left.right , k): #D 
| | | counter#D = 0 
| | | n.left.right == null -> return from #D 
| | 
| | end of method -> implicit return from #B 
| 
| counter#A++ -> counter#A = 1 
| ... 
... 

Beachten Sie, wie jeder Aufruf von kthElement schafft es eigene counter ist, die nur erhöht einmal für jeden Knoten.