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

あなたのプログラムには2つの問題があります

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(子)
        返還額

C++ を使用できる場合は、強くお勧めします。std::vector または std::list を使用して子ノードを格納でき、データ要素にテンプレート型を持たせることができれば、コードの複雑さが大幅に簡素化されます。

于 2010-03-24T09:27:28.640 に答える