JavaプログラムでBSTのk番目に小さい要素を見つける

Question

Javaプログラムを作成して、BSTのk番目に小さい要素を見つけようとしています。

私はスタックオーバーフローに関するこの質問の他の記事を読んで、解決策を見つけましたが、私のコードで何が問題であるのか理解できません。 誰でも私のプログラムが何も印刷していない理由を教えてください。次のように

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

} 

そして、私のノードクラスがある：それは印刷されません

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

} 

anything.Thatが問題です。 私はプログラミングがうまくいきませんので、ここでそのような質問をしてくださったことをご容赦ください。

Answer 1

カウンタkは更新されず、counterにはメソッドスコープがあり、再帰呼び出しごとに破棄されるため、問題が発生します。あなたは、すべてのメソッド呼び出しを通して一貫性のあるカウンターを行う必要があります。

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

このコードは、カウンタとしてkを使用し、kから0までカウントダウンし、ノードを返し、kは0

を回すいますcounterにメソッドローカルスコープがあるため、コードが機能しません。つまり、counterの値は、現在の電話kthSmallestに対してのみ有効です。前の呼び出しからのものよりも、これはメモリ内の別のcounterであることに注意してください - - 次の再帰呼び出しでは、counterは0に設定されますので、あなたのコードはk == 1ない限り、counter == kに到達することはできません。プログラムの流れの描写がk > 1ために、次のようになります

        1 
           / \ 
           2  3 

：このツリーの

//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 
| ... 
... 

注kthElementの各呼び出しは、それだけインクリメントされる自身のcounterだ作成する方法各ノードに対して1回。