Структурирование листьев в иерархическом дереве - PullRequest
Новая
       32

Структурирование листьев в иерархическом дереве

1 голос
/ 23 марта 2010

Этот код заполняет дерево значениями, основанными на их глубине. Но при обходе дерева мне не удается определить фактическое количество детей без итерации по родительскому узлу. Это необходимо, потому что подзаголовки хранятся в узле под текущим. Какие концептуальные изменения необходимы для хранения листьев непосредственно в текущем узле? 

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

Ответы [ 2 ]

1 голос
/ 24 марта 2010

Если ваша структура действительно является деревом, то следующий псевдокод для рекурсивного подсчета узлов может помочь: 

def total_number_of_leaf_nodes(node):
    if node does not have children:
        return 1
    else:
        sum = 0
        for each child of node:
            sum += total_number_of_leaf_nodes(child)
        return sum

Если вы вообще можете использовать C ++, я бы настоятельно рекомендовал это сделать. Возможность использовать std :: vector или std :: list для хранения ваших дочерних узлов и возможность придания элементу данных типа шаблона значительно упростит сложность вашего кода.

1 голос
/ 24 марта 2010

Я вижу две проблемы в вашей программе

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

Может быть, есть другие проблемы, но я настоятельно рекомендую сначала исправить их. Я надеюсь, что это может помочь вам Привет

...