Страница 1 из 1
2-3-4 деревья
Добавлено: 02 дек 2004, 00:35
michael
если допустить что даные содержащиеся в узлах это целые числа, каков будет НЕ РЕКУРСИВНЫЙ алгоритм распечатывения оных чисел по порядку возвростания?
Спасибо..
Код: Выделить всё
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];
}
Добавлено: 06 дек 2004, 16:06
Absurd
Почитай Кнута (том 1)...
Там был изящный алгоритм прошитых деревьев, который сводится к тому, что через все узлы по возрастанию тянется нить. Соответственно, чтобы пройти дерево, надо сделать один цикл вдоль всей нити.
Но нить надо поддерживать, и поэтому процедуры вставки и удаления узлов там несколько сложнее.
Добавлено: 06 дек 2004, 21:46
michael
а как книга то называется полностью?
Добавлено: 07 дек 2004, 13:04
Absurd
Добавлено: 07 дек 2004, 13:32
Absurd
Сорри, не заметил, что ты из Израиля и ссылки на озон тебе не нужны. Но как назвывается книжка, там в принципе ясно.
Добавлено: 07 дек 2004, 16:00
michael
Cпасибо. Но вот теоретический вопрос - возможно ли ВООБЩЕ пройтись по дереву не рекурсивно, не используя вспомагательную структуру?
Добавлено: 07 дек 2004, 19:59
Absurd
Можно эмулировать стек =)
Добавлено: 08 дек 2004, 19:22
michael
НЕ подкинет ли кто код как выбрать корень из 2-3-4 дерево и при этом сохранить структуру 2-3-4