我正在查看此处提出的问题,但只找到了有关二叉树的答案。 我想按级别顺序打印一棵有 0 - n 个 child 的树。 我知道 child 的数量,但我的代码不起作用
我想到的算法是:
- 打印根
- 打印所有子数据
- 每个 child
- 打印数据
但问题是我不知道在哪里停下来,当我递归尝试时,我失败了。
这是我写的函数:
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
最佳答案
此代码非常基于您的代码(但扩展为 SSCCE ),产生输出:
1 2 7 8 3 6 4 5 9 12 10 11
该代码使用了 C99 的指定初始化程序功能(C99 最有用的新增功能之一,恕我直言)。我选择使用比 myStruct
结构“更好”的名称;它代表一棵树,所以这就是它的名字。我也没有在 typedef 中隐藏指针,并使打印代码 const 正确(打印代码通常不应修改它正在运行的数据结构)。它还使用 C99 选项在 for
循环的第一个子句中声明变量。我引入了一个额外的函数,printTree()
,它从根节点打印数据,调用你的printBFS()
打印树的主体,并打印一个换行符标记输出结束; 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);
}
关于c - 如何在 C 中打印级别顺序树(不是二进制)?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12027669/