Structuration des feuilles dans un arbre hiérarchique

Question

Ce code remplit un arbre avec des valeurs basées sur leurs profondeurs. Mais lors de la traversée de l'arbre, je n'arrive pas à déterminer le nombre réel d'enfants sans itération sur le nœud parent. Ceci est nécessaire car les sous-fichiers sont stockés dans le nœud sous le nœud actuel. Quels changements conceptuels sont nécessaires pour stocker les feuilles directement dans le nœud actuel?

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

Answer 1

Je vois deux problèmes que vous programmez

1) Lorsque vous « realloc » la liste des nœuds, vous vous déplacez réellement en mémoire les objets de noeud, de sorte que le pointeur parent dans leurs enfants doivent me mis à jour aussi bien . Je vous suggère de transformer le tableau de noeuds en un tableau de pointeurs vers des noeuds, de sorte que vous puissiez le réaffecter sans corriger les pointeurs.

2) Vous avez oublié de mettre fin à cordes:

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

devrait être:

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

ou aussi simplement

node->p = strdup(s); 

Peut-être il y a d'autres questions, mais je suggère fortement à Corrigez-les d'abord. J'espère que cela peut vous aider à Cordialement

Answer 2

Si votre structure est vraiment un arbre, le pseudo-code suivant pour le comptage récursive noeuds peuvent aider:

 
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 

S'il est tout possible pour vous d'utiliser C++, alors je le conseillerais fortement. Etre capable d'utiliser une liste std :: vector ou std :: list pour stocker vos nœuds enfants et pouvoir faire en sorte que l'élément de données ait un type de template simplifierait grandement la complexité de votre code.