2

ベクター ベースのバイナリ ツリーがあり、さまざまな走査方法を使用して、ツリー内の各値に関数を適用する必要があります。preorder トラバーサルは、再帰関数を使用して実装するのが非常に簡単でしたが、inorder および postorder トラバーサルで同じことを行うのに問題がありました。誰かがそれを助けることができれば、それは素晴らしいことです!

含める必要のある追加情報: ノードのベクトルを使用しています。各ノードには、そのノードが満たされているかどうかを示すブール変数と、テンプレート化されたデータ変数が含まれています。各ノードはインデックス「i」に格納され、その左の子はインデックス「2i+1」に、右の子は「2i+2」に格納されます。

リストに事前注文トラバーサルを適用するために、最初にインデックス 0 に格納されたデータを処理し、次にこの再帰関数を呼び出しました。

template <typename Item, typename Key>
template <typename Function>
void BST<Item,Key>::preTraverse(int n, Function f) {
    if(tree[n].occupied == false) return;
    else {
        f(tree[n].data);
        preTraverse(2*i+1,f);
        preTraverse(2*i+2,f);
    }
}

私の「n」パラメータとしてインデックス1と2で始まる2回。

4

2 に答える 2

3

予約注文：

do something with the value
f(go to the left)
f(go to the right)

順番に：

f(go to the left)
do something with the value
f(go to the right)

ポストオーダー:

f(go to the left)
f(go to the right)
do something with the value
于 2012-11-26T01:32:12.960 に答える
2

ツリーが最大人口の左優位の表現であると仮定すると、位置の配列内の任意のポイントには、位置とi位置に子があります。些細な散歩：2*i+12*i+2

Node   Children
=====  ===========
ar[0]: ar[1], ar[2]
ar[1]: ar[3], ar[4]
ar[2]: ar[5], ar[6]
ar[3]: ar[7], ar[8]
ar[4]: ar[9], ar[10] etc...

この定義を考えると、単純なインデックス転送と「占有」フラグのいくつかのチェックで、事前注文、事後注文、および順序どおりのすべてを実行できます。次のテンプレートは、 typeTが「占有」メンバーを持つ構造体型であることを前提としています。

template<typename T>
void preorder(const T ar[], size_t i, size_t count, void (&visit)(const T&))
{
    if (i>=count || !ar[i].occupied)
        return;

    visit(ar[i]);
    preorder(ar, 2*i+1, count, visit);
    preorder(ar, 2*(i+1), count, visit);
}

template<typename T>
void inorder(const T ar[], size_t i, size_t count, void (&visit)(const T&))
{
    if (i>=count || !ar[i].occupied)
        return;

    inorder(ar, 2*i+1, count, visit);
    visit(ar[i]);
    inorder(ar, 2*(i+1), count, visit);
}

template<typename T>
void postorder(const T ar[], size_t i, size_t count, void (&visit)(const T&))
{
    if (i>=count || !ar[i].occupied)
        return;

    postorder(ar, 2*i+1, count, visit);
    postorder(ar, 2*(i+1), count, visit);
    visit(ar[i]);
}
于 2012-11-26T01:49:26.940 に答える