1

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

#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);
}
4

2 回答 2

1

我在您的程序中发现了两个问题

1）当您“重新分配”节点列表时，您实际上是在内存中移动节点对象，因此它们的子对象中的父指针也必须更新。我建议您将节点数组转换为指向节点的指针数组，这样您就可以重新分配它而无需更正指针。

2）您忘记终止字符串：

  node->p = malloc(strlen(s));
  memcpy(node->p, s, strlen(s));

应该：

  node->p = malloc(strlen(s)+1);
  memcpy(node->p, s, strlen(s)+1);

或者也简单地说

  node->p = strdup(s);

也许还有其他问题，但我强烈建议先纠正这些问题。我希望它可以帮助你问候

于 2010-03-23T21:09:10.980 回答
1

如果您的结构确实是一棵树，那么以下用于递归计算节点的伪代码可能会有所帮助：

def total_number_of_leaf_nodes（节点）：
    如果节点没有孩子：
        返回 1
    别的：
        总和 = 0
        对于节点的每个子节点：
            sum += total_number_of_leaf_nodes(child)
        返回总和

如果您完全可以使用 C++，那么我强烈建议您这样做。能够使用 std::vector 或 std::list 来存储您的子节点并能够使数据元素具有模板类型将大大简化代码的复杂性。

于 2010-03-24T09:27:28.640 回答