I am trying to make a function that would print a node and all of its children but I am trying to make it efficient and also recursive. But it doesn't really work.
#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;
}
This code will provide you with a verifiable example and here's what I tried to do:
void printParentChildRec(Tree root) {
if (!root)
return;
printf("%d ", root->value);
printParentChildRec(root->sibling);
printParentChildRec(root->child);
}
The results I am getting is just 0 1 2 3 4 5
which is all the nodes, but I want to print something like this:
0 1 2 3
1 4 5
2
3
4
5
There are some problems in your code:
intptr_t
values with %ld
, which is undefined behavior on platforms where intptr_t
is not an alias for long
and has a different size, such as Windows 64-bit. There is no specific printf
format for this type, you should either recast the value as (long)(intptr_t)tree
or (long long)(intptr_t)tree
and use %lld
, or their unsigned versions or use the %p
format with (void *)tree
.Here are more problems in your code:
main()
, Tree root = uniteForest(root, forest, 6);
passes undefined variable root
to uniteForest
.argument root
in Tree uniteForest(Tree root, Tree *forest, int n)
is never used, it is used only to store temporary results. You should just remove the argument and simplify the code as:
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
only prints the root of the tree, hence the value of forest[0]
and those of its descendants recursively. You instead want to print the value of the node and that of its immediate children, then recurse for each child.
Here is a corrected version:
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);
}
}
}
Output:
0 1 2 3 1 4 5 4 5 2 3