c++ - ツリーソートを使用して配列を変更する

Question

ソートされた順序で数値を出力するのではなく、ソートされた数値を配列に格納するためにツリーソートを使用しようとしています。n はゼロに初期化されます。

void BinSearchTree::inOrder( TreeNodePtr subRoot, int A[], int n )
{
    if ( subRoot != NULL )             
    {
        inOrder( subRoot->left, A, n );    

        A[n] = subRoot->key;
        n++;

        inOrder( subRoot->right, A, n ); 
    }
}

問題は、inOrder のパラメーターとして A を呼び出し続けるところにあると思いますが、他にどのようにこれを行うかはわかりません。

Answer 1

n への参照が必要です。そうしないと、次に割り当てる要素が何かわかりません。つまり、次のようになります。

void BinSearchTree::inOrder( TreeNodePtr subRoot, int A[], int& last )
{
    if ( subRoot != NULL )             
    {
        inOrder( subRoot->left, A, n );    

        A[last++] = subRoot->key;

        inOrder( subRoot->right, A, n ); 
    }
}

他のオプションは、ベクトルのような push_back 関数を持つコンテナを使用することです:

 void BinSearchTree::inOrder( TreeNodePtr subRoot, std::vector<int>& vec )
    {
        if ( subRoot != NULL )             
        {
            inOrder( subRoot->left, vec );    

            vec.push_back( subRoot->key );

            inOrder( subRoot->right, vec); 
        }
    }