我正在尝试创建一个可以打印节点及其所有子节点的函数,但我正在尝试使其高效且递归。但它并没有真正起作用。
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#define SIZE 100
typedef struct tree {
int value;
struct tree *child, *sibling, *parent;
} *Tree;
Tree initTree(int value) {
Tree root = malloc(sizeof(struct tree));
root->value = value;
root->parent = NULL;
root->child = NULL;
root->sibling = NULL;
return root;
}
void drawTreeHelper(Tree tree, FILE* stream) {
Tree tmp;
if (tree == NULL) {
return;
}
fprintf(stream, " %ld[label=\"%d\", fillcolor=red]\n", (intptr_t) tree, tree->value);
tmp = tree->child;
while (tmp != NULL) {
fprintf(stream, " %ld -> %ld \n", (intptr_t) tree, (intptr_t) tmp);
drawTreeHelper(tmp, stream);
tmp = tmp->sibling;
}
}
void drawTree(Tree tree, char *fileName) {
FILE* stream = fopen("test.dot", "w");
char buffer[SIZE];
fprintf(stream, "digraph tree {\n");
fprintf(stream, " node [fontname=\"Arial\", shape=circle, style=filled, fillcolor=yellow];\n");
if (tree == NULL)
fprintf(stream, "\n");
else if (!tree->child)
fprintf(stream, " %ld [label=\"%d\"];\n", (intptr_t) tree, tree->value);
else
drawTreeHelper(tree, stream);
fprintf(stream, "}\n");
fclose(stream);
sprintf(buffer, "dot test.dot | neato -n -Tpng -o %s", fileName);
system(buffer);
}
Tree uniteTries(Tree child, Tree parent)
{
if (parent)
{
if (!parent->child) parent->child = child;
else
{
Tree iter = parent->child;
while (iter->sibling) iter = iter->sibling;
iter->sibling = child;
}
}
return parent;
}
Tree uniteForest(Tree root, Tree *forest, int n)
{
int i;
for (i = 0; i < n; ++i)
{
if (forest[i]) root = uniteTries(forest[i], forest[i]->parent);
}
root = forest[0];
return root;
}
void printParentChildRec(Tree root)
{
if(!root) return;
printf("%d ", root->value);
printParentChildRec(root->sibling);
printParentChildRec(root->child);
}
int main() {
int i;
char buffer[SIZE];
Tree *forest = malloc(6 * sizeof(Tree));
for (i = 0; i < 6; i++) {
forest[i] = initTree(i);
}
forest[1]->parent = forest[0];
forest[2]->parent = forest[0];
forest[3]->parent = forest[0];
forest[4]->parent = forest[1];
forest[5]->parent = forest[1];
Tree root = uniteForest(root, forest, 6);
printParentChildRec(root);
drawTree(root, "tree.png");
return 0;
}
这段代码将为您提供一个可验证的示例,这是我尝试做的事情:
void printParentChildRec(Tree root) {
if (!root)
return;
printf("%d ", root->value);
printParentChildRec(root->sibling);
printParentChildRec(root->child);
}
我得到的结果只是0 1 2 3 4 5
,这是所有的节点,但我想打印这样的东西:
0 1 2 3
1 4 5
2
3
4
5
0
投票
投票
您的代码中存在一些问题:
你隐藏了typedef背后的指针,这对你的代码的读者来说很困惑,并且经常导致编程错误。 您使用intptr_t
打印
%ld
值,这是在
intptr_t
不是
long
的别名且具有不同大小的平台上的未定义行为,例如Windows 64位。此类型没有特定的
printf
格式,您应该将值重新设置为
(long)(intptr_t)tree
或
(long long)(intptr_t)tree
并使用
%lld
或其无符号版本或使用
%p
格式与
(void *)tree
。 您期望的结果不是作为文本生成的,而是某种形式的图形渲染,难以从代码中分析。首先生成文本输出将更容易调试。
以下是您的代码中的更多问题:
在main()
,
Tree root = uniteForest(root, forest, 6);
将未定义的变量
root
传递给
uniteForest
。
root
中的参数
Tree uniteForest(Tree root, Tree *forest, int n)
从未使用过,它仅用于存储临时结果。您应该删除参数并简化代码:
Tree uniteForest(Tree *forest, int n) { for (int i = 0; i < n; i++) { if (forest[i]) uniteTries(forest[i], forest[i]->parent); } return forest[0]; }
main
只打印树的根,因此递归地显示
forest[0]
及其后代的值。您想要打印节点的值以及其直接子节点的值,然后递归每个子节点。
这是一个更正版本:
void printParentChildRec(Tree node) {
if (node) {
printf("%d ", node->value);
for (Tree child = node->child; child; child = child->sibling) {
printf("%d ", child->value);
}
printf("\n");
for (Tree child = node->child; child; child = child->sibling) {
printParentChildRec(child);
}
}
}
输出:
0 1 2 3 1 4 5 4 5 2 3
0
投票
投票
我认为你的联合树功能是这里的问题。我用我的调试器运行这段代码,这就是它从根目录看起来的样子
这是在unite trees方法之后输入到print函数的根:
你能告诉我你在这里想要达到的目标吗?也许我可以帮助你!