Алгоритм реализации недвоичных деревьев с использованием одномерного вектора?

Question

Каждый узел дерева может иметь произвольное количество дочерних элементов. Мне нужен способ построения и обхода таких деревьев, но для их реализации используется одномерный вектор или список

Answer 1

Если вы можете использовать только один вектор (не указан в вопросе), и узлы не должны содержать свой собственный список, только некоторые указатели (адреса в векторе), тогда вы можете попробовать это:

1. каждый узел содержит адрес своего брата
2. первый узел после данного (если это не его брат или сестра) является дочерним, с указателем на второго дочернего элемента и т. Д.
3. у каждого ребенка есть свои дети

Так для дерева вот так:

A
| \
B  E ___
|\  \ \ \
C D  F G H

Ваш вектор будет выглядеть так:

idx:    0 1 2 3 4 5 6 7
nodes:  A B C D E F G H
next:   _ 4 3 _ _ 6 7 _

, где _ - нулевой указатель

Edit:
Другой подход:

1. каждый узел содержит адрес области в векторе, занятом его дочерними элементами
2. дети рядом друг с другом
3. в векторе существует нулевой узел, отмечающий конец группы братьев и сестер

Для этого подхода данное дерево будет выглядеть так:

idx:    0 1 2 3 4 5 6 7 8 9 A B
nodex:  A _ B E _ C D _ F G H _
child:  2   5 8   _ _   _ _ _

Таким образом, вы можете легко найти дочерние элементы любого случайно заданного узла и реорганизовать массив, не перемещая все элементы (просто скопируйте дочерние элементы в конец таблицы, обновите указатель и добавьте следующий дочерний элемент в конец таблицы)

Answer 2

То, что вы в основном делаете, - это пишите начало диспетчера памяти для интерпретатора Lisp, объединяя элементы вектора в cons-ячейки. Вот что я сейчас бросил в Си:

#include <stdbool.h>
#include <iso646.h>
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

#define MEMORY_SIZE 1024
#define NIL 0
#define IVAL_MASK 0x8000000

struct pair
{
    bool allocated;
    size_t first;
    size_t second;
};

size_t allocate_pair(struct pair vector[])
{
    for (size_t i = 1; i < MEMORY_SIZE; i++)
        {
            if (not vector[i].allocated)
                {
                    vector[i].allocated = true;
                    return i;
                }
        }

    return NIL;
}

size_t make_pair(struct pair vector[], size_t a, size_t b)
{
    size_t the_pair = allocate_pair(vector);

    if (the_pair != NIL)
        {
            vector[the_pair].first = a;
            vector[the_pair].second = b;
            return the_pair;
        }
    else
        {
            fprintf(stderr,
                    "Out of pairs -- make_pair(%p, %zu, %zu)",
                    vector,
                    a,
                    b);
            exit(EXIT_FAILURE);
        }
}

size_t first(struct pair vector[], size_t index)
{
    assert(vector[index].allocated);

    return vector[index].first;
}


size_t second(struct pair vector[], size_t index)
{
    assert(vector[index].allocated);

    return vector[index].second;
}

void print_pair_aux(struct pair[], size_t, size_t);
void print_pair(struct pair vector[], size_t p)
{
    assert(vector[p].allocated);

    size_t a = first(vector, p);
    size_t b = second(vector, p);

    printf("(");

    print_pair_aux(vector, a, b);

    printf(")");
}

void print_pair_aux(struct pair vector[], size_t a, size_t b)
{
    if (a == NIL)
        printf("NIL");
    else if (a >= IVAL_MASK)
        printf("%zu", a &~ IVAL_MASK);
    else
        print_pair(vector, a);

    if (b == NIL)
        printf("");
    else if (b >= IVAL_MASK)
        printf(" . %zu", b &~ IVAL_MASK);
    else
        {
            printf(" ");
            print_pair_aux(vector,
                           first(vector, b),
                           second(vector, b));
        }

}

int main(void) 
{
    struct pair *vector = calloc(MEMORY_SIZE, sizeof *vector);

#define cons(A,B) make_pair(vector, (A), (B))
#define ival(x) ((x) | IVAL_MASK)

    size_t a = cons(ival(3), cons(ival(4), NIL));
    size_t b = cons(ival(2), cons(a, NIL));
    size_t c = cons(ival(6), cons(ival(7), cons(ival(8), NIL)));
    size_t d = cons(ival(5), cons(c, NIL));
    size_t e = cons(ival(1), cons(b, cons(d, NIL)));

    print_pair(vector, e);
    puts("");
}

$ cc -std=c99 try.c
$ ./a.out
(1 (2 (3 4)) (5 (6 7 8)))

Answer 3

Вы можете реализовать его, используя одномерный связанный список с небольшими накладными расходами.

Каждый родитель будет содержать указатели на своих потомков (но для этого необходимо решить, известно ли максимальное число узлов заранее).

Для дерева, имеющего A в качестве корневого узла и B, C, D в качестве дочерних, его представление будет таким, как показано ниже.

A -> B A -> C A -> D

Обратите внимание, что есть 3 ссылки от A.

Один из способов преодоления верхнего предела по количеству узлов заключается в наличии дополнительного указателя в узлах.

Итак, теперь A -> (дочерний) B -> (прил.) -> (прил.) C -> (прил.) -> D

В этом случае довольно сложно обновлять дерево при удалении.

Еще проще спроектировать более совершенные структуры данных, если бы вы могли определять временные рамки для различных операций.

Answer 4

Стандартный способ хранения полного двоичного дерева в массиве (как используется для реализаций двоичной кучи) хорош, поскольку вы можете представить дерево с массивом элементов в порядке обхода дерева порядка уровня. Используя эту схему, есть быстрые приемы для вычисления положения родительского и дочернего узла. Переход к дереву, в котором каждый узел может иметь произвольное количество элементов, приводит к появлению гаечного ключа в схеме такого типа.

Однако существует несколько схем для представления произвольных деревьев в виде двоичных деревьев. Они подробно обсуждаются в книге «Искусство компьютерного программирования» Дональда Кнута, том I, раздел 2.3.

.

Если самим узлам разрешено содержать указатель, вы можете сохранить список дочерних указателей для каждого узла. Это возможно в вашем случае?

Answer 5

Без ограничений на значения узлов и при условии, что вы можете использовать только один список, я бы построил его следующим образом:

Представляет каждый узел как ( val ; [ int ; ...] ), где val - значение узла, а каждое int - позиция в списке одного из его дочерних элементов. При необходимости используйте непечатаемый разделитель.

Обход очень медленный.