Counting leaf nodes in hierarchical tree
- by timn
This code fills a tree with values based their depths. But when traversing the tree, I cannot manage to determine the actual number of children. node-cnt is always 0. I've already tried node-parent-cnt but that gives me lots of warnings in Valgrind.
Anyway, is the tree type I've chosen even appropriate for my purpose?
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#ifndef NULL
#define NULL ((void *) 0)
#endif
// ----
typedef struct _Tree_Node {
// data ptr
void *p;
// number of nodes
int cnt;
struct _Tree_Node *nodes;
// parent nodes
struct _Tree_Node *parent;
} Tree_Node;
typedef struct {
Tree_Node root;
} Tree;
void Tree_Init(Tree *this) {
this->root.p = NULL;
this->root.cnt = 0;
this->root.nodes = NULL;
this->root.parent = NULL;
}
Tree_Node* Tree_AddNode(Tree_Node *node) {
if (node->cnt == 0) {
node->nodes = malloc(sizeof(Tree_Node));
} else {
node->nodes = realloc(
node->nodes,
(node->cnt + 1) * sizeof(Tree_Node)
);
}
Tree_Node *res = &node->nodes[node->cnt];
res->p = NULL;
res->cnt = 0;
res->nodes = NULL;
res->parent = node;
node->cnt++;
return res;
}
// ----
void handleNode(Tree_Node *node, int depth) {
int j = depth;
printf("\n");
while (j--) {
printf(" ");
}
printf("depth=%d ", depth);
if (node->p == NULL) {
goto out;
}
printf("value=%s cnt=%d", node->p, node->cnt);
out:
for (int i = 0; i < node->cnt; i++) {
handleNode(&node->nodes[i], depth + 1);
}
}
Tree tree;
int curdepth;
Tree_Node *curnode;
void add(int depth, char *s) {
printf("%s: depth (%d) > curdepth (%d): %d\n", s, depth, curdepth, depth > curdepth);
if (depth > curdepth) {
curnode = Tree_AddNode(curnode);
Tree_Node *node = Tree_AddNode(curnode);
node->p = malloc(strlen(s));
memcpy(node->p, s, strlen(s));
curdepth++;
} else {
while (curdepth - depth > 0) {
if (curnode->parent == NULL) {
printf("Illegal nesting\n");
return;
}
curnode = curnode->parent;
curdepth--;
}
Tree_Node *node = Tree_AddNode(curnode);
node->p = malloc(strlen(s));
memcpy(node->p, s, strlen(s));
}
}
void main(void) {
Tree_Init(&tree);
curnode = &tree.root;
curdepth = 0;
add(0, "1");
add(1, "1.1");
add(2, "1.1.1");
add(3, "1.1.1.1");
add(4, "1.1.1.1.1");
add(2, "1.1.2");
add(0, "2");
handleNode(&tree.root, 0);
}
