3

Box オブジェクトと呼ぶこのような構造があります。

Box--+---Box----Box
     |
     +---Box-+--Box
             |
             +--Box
             |
             +--Box

トップ ボックス オブジェクトにリーフ ノード ボックスのリストを要求しようとしています。この場合、これは 3 つのボックス オブジェクトです。

box オブジェクトには、children と呼ばれる Vector 型のインスタンス変数に、その子のリストがあります。

お子様の人数は無制限です。

これを行うための単一の再帰メソッドを作成しようとしましたが、成功しませんでした。

4

3 に答える 3

1

このような関数を作成するには、いくつかの方法があります。これが解決するための1つのアプローチです。

  • ノードとノードを保持する可変キューを受け取るヘルパー関数を定義します。
  • そのヘルパー関数で、指定されたノードの子が空であるかどうかを確認します。その場合は、そのノードをキューに追加して、戻ります。
  • 代わりに、提供されたノードに子がある場合は、子ごとにヘルパー関数を1回呼び出し、子と同じキュー参照を渡します。
  • トップレベルで、空のキューを作成し、ヘルパー関数を呼び出して、ルートノードとキューを渡します。
  • ヘルパー関数が戻ると、キューには、検出された順序ですべてのリーフが含まれます。

別のアプローチでは、同じ深さ優先走査を使用しますが、関数は検出した葉のリストを返します。これらのリストは、探索された兄弟のセットごとに組み合わせる必要があり、関数呼び出しが戻るたびにツリーをバックアップします。

于 2011-02-05T00:35:28.707 に答える
1

私が Java をやったのは久しぶりなので、このコードには構文エラーがたくさんあると確信しています。いくつかのアルゴリズムのアイデアを提供しようとしているだけです。うまくいけば、それは役に立ちます:

vector<Box> getLeaves(Box root)
{
    vector<Box> tempList;    //vector to hold nodes to check
    vector<Box> tempList2;   //vector to hold nodes' children
    vector<Box> leafList;
    bool goflag = true;

    tempList.add(root);

    while(goflag){
        for(int i = 0; i < tempList.size; i++){
            if(tempList[i].children.isEmpty()){
                leafList.add(tempList[i]);
            }
            else{
                //add all children to tempList2
                for(int c = 0; c < tempList[i].children.size; c++){
                    tempList2.add(tempList[i].children[c])
            }
        }
        if(tempList2.isEmpty()) //no more childs
            goflag = false;
        else
            tempList = tempList2;
        tempList2.clear();
    }
    return leafList;
}

すべてのノードを通過し、チェックする次のリストに子を追加し、返されるリストに葉を追加します。

于 2011-02-05T00:05:44.880 に答える
1

これを行う 1 つの方法は、構造を再帰的に走査することです。考え方は次のとおりです。

  1. 空のツリーにはリーフ ノードがありません。
  2. 子を持たないルート r を持つツリーでは、r が唯一のリーフです。
  3. ルート r を持つツリーで、r に子がある場合、ツリーの葉はそれらの子の葉になります。

この種の疑似コードを使用して、再帰的なトラバーサルを作成できます。

void findChildren (Box current, List<Box> found) {
    /* Case 1. */
    if (current == null) return;

    /* Case 2. */
    if (current.children.isEmpty()) {
        found.add(current);
        return;
    }

    /* Case 3. */
    for (Box child: current.children)
        findChildren(child, found);
}

お役に立てれば！

于 2011-02-04T23:31:45.653 に答える