c - 有效打印树节点及其所有子节点
问题描述
我正在尝试制作一个可以打印节点及其所有子节点的函数,但我正在尝试使其高效且递归。但它并没有真正起作用。
#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
解决方案
您的代码中存在一些问题:
- 您将指针隐藏在 typedef 后面,这会使您的代码读者感到困惑,并且经常导致编程错误。
- 您使用 打印
intptr_t
值,这是在不是别名且大小不同的%ld
平台上未定义的行为,例如 Windows 64 位。此类型没有特定格式,您应该将值重新转换为or并使用,或者它们的无符号版本或使用格式 with 。intptr_t
long
printf
(long)(intptr_t)tree
(long long)(intptr_t)tree
%lld
%p
(void *)tree
- 您期望的结果不是文本,而是某种形式的图形渲染,很难从代码中分析。首先生成文本输出会更容易调试。
以下是您的代码中的更多问题:
- 在 中
main()
,Tree root = uniteForest(root, forest, 6);
将未定义的变量传递root
给uniteForest
。 从不使用参数
root
inTree 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
推荐阅读
- python - 错误- IndentationError: unindent 不匹配任何外部缩进级别
- kotlin - 如何在 Kotlin Jupyter 中添加包名
- python - 无法找到包 python-pip Ubuntu 20.04
- python - 如何过滤pydatatable中列组的NA值?
- c++ - “缺少类型说明符 - 假定为 int。注意:C++ 不支持默认 int”错误发生在同一 .h 文件中定义的结构的字段中
- typescript - 在打字稿中使用 as 关键字
- python-3.x - Python Vending Machine类方法理解
- c++ - C++ 如何根据作为输入传递的参数调用一个或另一个构造函数?
- magento - 如何访问 cpanel?
- javascript - 在 Blazor Web Assembly 应用程序中显示本地计算机摄像头源