在分層樹中構造葉子

Question

此代碼使用基於其深度的值填充樹。但是當遍歷樹時，我無法設法確定實際的孩子數量而沒有迭代父節點。這是必要的，因爲子樓層存儲在當前節點下方的節點中。爲了將葉子直接存儲在當前節點中，需要進行哪些概念更改？

#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

我看到兩個問題在你的程序

1）當你「realloc的」節點列表，實際上是在內存中移動節點的對象，所以在他們的子女的父或母，指針必須我更新以及。我建議你將節點數組轉換成指向節點的指針數組，這樣你就可以在不修正指針的情況下重新分配它。

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

可能還有其他的問題，但我強烈建議先糾正這些問題。 我希望它可以幫助你 問候

Answer 2

如果你的結構是一個真正的樹，然後遞歸計算節點可以幫助下面的僞代碼：

 
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來存儲您的子節點並且能夠使數據元素具有模板類型將大大簡化代碼的複雜性。