PDA

Просмотр полной версии : 2-3-4 деревья



michael
02.12.2004, 00:35
если допустить что даные содержащиеся в узлах это целые числа, каков будет НЕ РЕКУРСИВНЫЙ алгоритм распечатывения оных чисел по порядку возвростания?

Спасибо..


class Node
{
private static final int ORDER = 4;
private int numItems;
private Node parent;
private Node childArray[] = new Node[ORDER];
private DataItem itemArray[] = new DataItem[ORDER-1];
}

Absurd
06.12.2004, 16:06
Почитай Кнута (том 1)...
Там был изящный алгоритм прошитых деревьев, который сводится к тому, что через все узлы по возрастанию тянется нить. Соответственно, чтобы пройти дерево, надо сделать один цикл вдоль всей нити.
Но нить надо поддерживать, и поэтому процедуры вставки и удаления узлов там несколько сложнее.

michael
06.12.2004, 21:46
а как книга то называется полностью?

Absurd
07.12.2004, 13:04
http://www.ozon.ru/context/detail/id/1335648/

Absurd
07.12.2004, 13:32
Сорри, не заметил, что ты из Израиля и ссылки на озон тебе не нужны. Но как назвывается книжка, там в принципе ясно.

michael
07.12.2004, 16:00
Cпасибо. Но вот теоретический вопрос - возможно ли ВООБЩЕ пройтись по дереву не рекурсивно, не используя вспомагательную структуру?

Absurd
07.12.2004, 19:59
Можно эмулировать стек =)

michael
08.12.2004, 19:22
НЕ подкинет ли кто код как выбрать корень из 2-3-4 дерево и при этом сохранить структуру 2-3-4