1

私はここで尋ねられている質問を見ていましたが、二分木に関する答えしか見つかりませんでした。0〜n個の子を持つツリーをレベル順に印刷したいと思います。子供の数はわかっていますが、コードが機能していません

私が考えたアルゴリズムは次のとおりです。

  • ルートを印刷
  • すべての子データを印刷します
  • 子供ごとに
    • データを印刷する

しかし、問題は、どこで停止するかわからないことです。再帰的に試行すると、失敗します。

これは私が書いた関数です：

void printBFS(myStruct s)
   {
      int i = 0;
      printAllChildrenData(s);
      for (i = 0; i < s->number_of_children; i++)
        {
            myStruct childCurr = getChildAtIndex(s, i);
            printBFS(chilCurr);
        }
   }

私はここで何かをいじっています。関数が明確であることを願っていますprintAllChildrenData。Sのすべての子のすべてのデータを出力します。子リストを調べて印刷します。

たとえば、このツリーがある場合の編集：

           1
     2        7        8
  3    6            9     12
 4 5              10 11

印刷する必要があります：

1 2 7 8 3 6 4 5 9 12 10 11

それ以外の：

1 2 7 8 3 6 9 12 4 5 10 11
4

3 に答える 3

1

このコードは、コードに厳密に基づいていますが（ただし、SSCCEに拡張されています）、次の出力を生成します。

 1 2 7 8 3 6 4 5 9 12 10 11

このコードは、C99の指定された初期化機能（C99への最も便利な追加機能の1つであるIMNSHO）を使用しています。myStruct構造よりも「より良い」名前を使用することを選択しました。それは木を表すので、それはそれが呼ばれるものです。また、typedefでポインターを非表示にせず、印刷コードをconst-correctにしました（印刷コードは通常、操作しているデータ構造を変更しないはずです）。また、C99オプションを使用して、forループの最初の句で変数を宣言します。printTree()ルートノードからデータを出力し、yourを呼び出してprintBFS()ツリーの本体を印刷し、出力の終わりを示す改行を出力する追加の関数を導入しました。このprintTree()関数は、ツリーを印刷するために呼び出されます。の体系的な使用に注意してくださいprintData()ノードのデータを出力します。データが単一の整数よりも複雑な場合、これにより、印刷コードを1回記述することができます。

コードを注意深く調べると、printBFS()以下が表示内容と同型であることがわかります。これは、表示するコードに問題がないことを示しています。つまり、ツリーの印刷に使用されるコードではなく、ツリーの構築に使用するコードに含まれている可能性があります。ツリー構築コードを表示していないため、問題が何であるかを予測するのが難しくなります。

#include <stdio.h>
#include <assert.h>

enum { MAX_CHILDREN = 3 };
typedef struct Tree Tree;

struct Tree
{
    int data;
    int number_of_children;
    Tree *children[MAX_CHILDREN];
};

static void printData(const Tree *s)
{
    printf(" %d", s->data);
}

static void printAllChildrenData(const Tree *s)
{
    for (int i = 0; i < s->number_of_children; i++)
        printData(s->children[i]);
}

static const Tree *getChildAtIndex(const Tree *s, int i)
{
    assert(s != 0 && i >= 0 && i < s->number_of_children);
    return(s->children[i]);
}

static void printBFS(const Tree *s)
{
    printAllChildrenData(s);
    for (int i = 0; i < s->number_of_children; i++)
    {
        const Tree *childCurr = getChildAtIndex(s, i);
        printBFS(childCurr);
    }
}

static void printTree(const Tree *s)
{
    printData(s);
    printBFS(s);
    putchar('\n');
}

/*
**             1
**       2        7        8
**    3    6            9     12
**   4 5              10 11
*/

static Tree nodes[] =
{
    [ 1] = {  1, 3, { &nodes[ 2], &nodes[ 7], &nodes[ 8] } },
    [ 2] = {  2, 2, { &nodes[ 3], &nodes[ 6], 0          } },
    [ 3] = {  3, 2, { &nodes[ 4], &nodes[ 5], 0          } },
    [ 4] = {  4, 0, { 0,          0,          0          } },
    [ 5] = {  5, 0, { 0,          0,          0          } },
    [ 6] = {  6, 0, { 0,          0,          0          } },
    [ 7] = {  7, 0, { 0,          0,          0          } },
    [ 8] = {  8, 2, { &nodes[ 9], &nodes[12], 0          } },
    [ 9] = {  9, 2, { &nodes[10], &nodes[11], 0          } },
    [10] = { 10, 0, { 0,          0,          0          } },
    [11] = { 11, 0, { 0,          0,          0          } },
    [12] = { 12, 0, { 0,          0,          0          } },
};

int main(void)
{
    printTree(&nodes[1]);
    return(0);
}

テストを簡単に修正して、各ノードを順番に印刷できます。

enum { NUM_NODES = sizeof(nodes) / sizeof(nodes[0]) } ;

int main(void)
{
    for (int i = 1; i < NUM_NODES; i++)
        printTree(&nodes[i]);
    return(0);
}
于 2012-08-19T18:57:38.930 に答える
1

printElementsAtLevelN（int n）のような関数を使用して、ツリーをトラバースし、ツリーの深さを追跡し、適切なレベルの要素のみを出力することができます。印刷された要素の数を返すようにすると、次のようなループが発生する可能性があります。

while (printElementsAtLevelN( n ))
{
    n++;
}

これの欠点は、ツリーの一部を何度もトラバースすることですが、ツリーが大きくない場合は、問題にならない可能性があります。

于 2012-08-19T16:52:06.973 に答える
0

リスト構造（または他のコンテナ）が必要です。擬似コードは次の行に沿っています。

ListOfNodes list
ListOfNodes children
add_node(list, root)
repeat {
    while (list not empty) {
        print top_node(list)
        add_children(children, top_node)
        pop_top(list)
    }
    list = children
    clear_all(children)
} until (list is empty)
于 2012-08-19T15:47:12.910 に答える