1

二分木を表す C 構造体があります。

struct btree {
    char *word; 
    int frequency; 
    struct btree *left; 
    struct btree *right; 
};

渡されたバイナリツリー内btree_list(struct btree*)のすべてのオブジェクトの配列を返す関数を作成したいと思います。btree注文は関係ありません。

この関数がどのように機能するかの例を次に示します。

struct btree *T = populate_with_random_values(); 
struct btree *entries = (struct btree*) malloc(sizeof(struct btree) * btree_size(T));

entries = btree_list(T);

while (*entries != NULL) {
    printf("There are %d occurences of the word %s", entries->frequency, entries->word); 
    entries++; 
}

また、 の各要素に対してE、entries技術的に使用されていないため、 に設定する必要がありますE->left。これを実装するにはどうすればよいですか？E->rightNULL

4

3 に答える 3

1

さて、プレオーダー、インオーダー、またはポストオーダーのトラバーサルが必要ですか?

疑似コードでの予約注文の例を次に示します: ( Wikipedia のクレジット)

iterativePreorder(node)
  parentStack = empty stack
  while not parentStack.isEmpty() or node ≠ null
    if node ≠ null then
      visit(node)
      if node.right ≠ null then
        parentStack.push(node.right)
      node = node.left
    else
      node = parentStack.pop()

ノードのリストを返すようにするには、これを少し調整する必要がありますが、ツリー ウォークの背後にあるアイデアはすべてそこにあります。

于 2013-10-17T05:19:14.523 に答える
1

これは配列である可能性があります：

typedef struct {
    struct btree **data;
    size_t count;
} t_tbl;

t_tbl *tbl_create(size_t count)
{
    t_tbl *new = NULL;

    if (count > 0) {
        new = malloc(sizeof(t_tbl));
        new->data = malloc(count * sizeof(struct btree *));
        new->count = 0;
    }
    return new;
}

void tbl_destroy(t_tbl *table)
{
    if (table) {
        free(table->data);
        free(table);
    }
}

そして、これはプロセスである可能性があります：

void btree_populate_array(const t_node *root, t_tbl *table)
{
    if (root->left) btree_populate_array(root->left, table);
    table->data[table->count++] = root;
    if (root->right) btree_populate_array(root->right, table);
}

if (root) {
    t_tbl *table = tbl_create(btree_size);
    btree_populate_array(root, table);
    /* Do stuff with array */
    tbl_destroy(table);
}

mallocbtree のサイズがわからない場合は、を確認する必要があります。

void btree_count(const t_node *root, size_t *count)
{
    if (root->left) btree_count(root->left, count);
    (*count)++;
    if (root->right) btree_count(root->right, count);
}

size_t btree_size = 0;

if (root) {
    btree_count(root, &btree_size);
}
于 2013-10-17T05:33:25.493 に答える