私はサイズ<code>n</code>と（異なる値の）大きさ<code>n</code>の<code>int</code>のソートされた配列の<code>int</code>のBSTツリーを持っていると私は配列を使用してツリーを埋めるためにしたい場合はトラバーサル

Question

INORDER使用して、同じサイズのソートされた配列から既存のBSTを記入要素 - ツリー上のインオーダートラバーサルで行う必要があります。つまり、arr[0]が最も左側のノードにあり、arr[n-1]が最も右側のノードになるようにします。 （だからそれはO(n)時間かかる）

私はそれを行う素朴な再帰関数を書こうとしましたが、動作しません。現在のインデックスを配列に保存するには、何かをしなければならないようです。

void insert(Node* v, int* arr) { 
    if (!v) { 
     return; 
    } 

    insert(v->left, arr); 
    v->key = a[0]; 
    insert(v->right, arr + 1); 
} 

どのように変更する必要がありますか？

Answer 1

あなたの決定はほぼ真実です。ちょうどに関数宣言を変更：

void insert(Node* v, int* &arr) 

、あなたは右のサブツリーを訪問するとき、あなたは次の方法で、配列の次の要素を渡す必要があります。

insert(v->right, ++arr); 

arrを参照&として渡す必要があります。あなたのケースでは、配列へのポインタのコピーの渡しに関連しています。子ノードから親ノードに戻るとき、ポインタは初期配列arrの最初の要素にリセットされます。 コードに小さな変更を加えて配列へのポインタへのポインタを使用しても同様の動作を得ることができます。