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 最有用的补充之一，IMNSHO）。我选择使用比myStruct结构“更好”的名称；它代表一棵树，所以这就是它的名称。我也没有在 typedef 中隐藏指针，并使打印代码 const 正确（打印代码通常不应该修改它正在操作的数据结构）。它还使用 C99 选项在for循环的第一个子句中声明一个变量。我引入了一个额外的函数，printTree()它从根节点打印数据，调用 yourprintBFS()来打印树的主体，并打印一个换行符来标记输出的结束；调用该printTree()函数来打印一棵树。注意系统的使用printData()打印节点的数据。如果数据比单个整数更复杂，这将允许您编写一次打印代码。

仔细研究代码会发现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 回答