구조적 트리 구조 리프팅

Question

이 코드는 깊이를 기준으로 트리를 채 웁니다. 그러나 트리를 탐색 할 때 부모 노드를 반복하지 않고 실제 자식 수를 결정할 수는 없습니다. 서브 리프가 현재 노드 아래의 노드에 저장되기 때문에 이것은 필요합니다. 어떤 개념적인 변경이 현재 노드 내에 직접 leafs를 저장하는데 필요합니까? 당신이 "realloc을"노드 목록, 실제로 메모리에 노드 객체를 이동하면

#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

나는) 당신이

한 프로그램에서이 문제를보고, 그래서 자녀의 부모 포인터 나도 업데이트해야한다 . 노드 배열을 노드에 대한 포인터 배열로 변형하여 포인터를 수정하지 않고 다시 할당 할 수 있습니다.

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

가 있어야한다 :

2) 당신은 문자열을 종료하는 것을 잊었다 또한

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를 사용하여 자식 노드를 저장하고 데이터 요소에 템플릿 유형이 있도록함으로써 코드의 복잡성을 크게 줄일 수 있습니다.