binary-search-tree - 二分探索木で K 番目の要素を見つける

Question

二分探索木について学んでいます。二分探索木の順走査のk番目の要素を返したい。変数 'c​​ount' を更新し続けるにはどうすればよいですか、または k 番目の要素を見つけて出力したら、ループから抜け出す方法はありますか?

public void kthElement(int n, int count, BinaryNode<AnyType> root){

    if( root.left !=null)
        this.kthElement(n, count, root.left);

    count++;
    if(count==n){
        System.out.println(root.element); 
        }

    else if(count!=n){
        return;}

    if( root.right != null)
        this.kthElement(n, count, root.right);
    }

Answer 1

私は2つの解決策を考えることができます。

1. 各ノードの右側のサブツリーと左側のサブツリーに含まれる要素の数を示すフィールドを宣言します。ここからは簡単に進めることができます。
2. 追加のメモリを使用できる場合は、要素を動的に割り当てられた並べ替えられた配列にコピーし (インオーダー トラバーサルを使用)、k 番目の要素を返します。