在层次树中构造叶子

此代码使用基于深度的值填充树。但是在遍历树时,如果不遍历父节点,就无法确定子节点的实际数量。这是必要的,因为子AFs存储在当前节点下的节点中。哪些概念上的改变是直接在当前节点中存储叶子所必需的?

#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]
        = malloc(sizeof(Tree_Node));

    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;
    }

    int cnt = 0;
    for (int i = 0; i < node->parent->cnt - 1; i++) {
        if (node->parent->nodes[i] == node) {
            cnt = node->parent->nodes[i + 1]->cnt;
        }
    }

    printf("value=%s cnt=%i", node->p, 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) + 1);
        memcpy(node->p, s, strlen(s) + 1);

        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) + 1);
        memcpy(node->p, s, strlen(s) + 1);
    }
}

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(4, "1.1.1.1.2");
    add(4, "1.1.1.1.3");
    add(4, "1.1.1.1.4");
    add(2, "1.1.2");
    add(0, "2");

    handleNode(&tree.root, 0);
}