Пишу от имени IceStudent'a, т.к. он не может залезть на форум...

На «АлгоЛисте» искал методы реализации обходов по бинарным
деревьям, но нашёл только общую классификацию.
Мне требуется сохранить/загрузить дерево, т.е. всё сводится к
полному проходу по дереву. Пробовал самостоятельно написать
функцию, но запутался в ней. Перечитал единственную книгу по
алгоритмам (подарочная «Жемчужины программирования»),
нашёл в ней «симметричный обход». Общий смысл его понятен, но
боязно вызывать рекурсию (а вдруг данных > 1Мб? как быть тогда
со стеком? вручную увеличивать?). В книге сказано, что можно
даже увеличить быстродействие, заменив рекурсию итерацией. А
как это можно сделать?
На «АлгоЛисте» сказано, что:
"Рекурсивные обходы можно, очевидно, организовать и с помощью
стека, 'развернув' рекурсию".
Это как понимать? "Развернуть" рекурсию - это заменить её
итерацией? А как это "организовать с помощью стека"?
Просвятите…

Вот то, что я думаю/понял о проходе по бинарному дереву:
1. а) Проход по дереву можно сделать как по лабиринту: всё время
по 1 стороне (напр., левой), одновременно запоминая непустые
правые узлы. Как только упрёшься в "NULL", то возвращаешься к
предыдущему непустому правому узлу и спускаешься теперь от
него также по левой стороне. И так далее. Это, случайно, не
«обход в ширину»? Или мой вариант - это "обход в высоту"?
б) Но как быть с "запоминанием" непустых узлов? Тут треба по
идее динамический массив, но это несерьёзно. Рекурсивный
вызов функции использует стек, вроде этого массива, только он
(стек) является ограниченным (1Мб по умолчанию, а если дать,
скажем, 16Мб? Как это отразится на системе/программе?
быстродействие, эффективность?).
2. Обычные обходы (что приведены в «АлгоЛисте»):
Я попытался представить (по рекурсии) «симметричный обход» -
получается, что он обрабатывает дерево как шомпол, т.е. сначала
спускается по 1 стороне до самого низу, обрабатывает нижний
узел, "возвращается" чуть наверх, обрабатывает узел, смотрит 2
сторону: если не пустая, то заходит в неё и снова идёт по 1
стороне до самого низу.
Ага, получается, что мой вариант - это «обход в прямом порядке»,
т.к. под проходом я понимал обработку узла при первом
попадании на него.

P.S. А вообще это я переписываю свою старую прогу, работающую на
двоичном дереве (только сейчас об этом узнал), где данные
сохранялись у меня в 2-х массивах (для вариантов А и Б), но
требовалось ещё 2 (или 1, но массив структур, сост. из А и Б) для
хранения индексов. В общем, тогда я сделал это как попало, но оно
работало. А теперь хочу переписать её на что-то более красивое.

Написал я вот давеча автоматический трейсер PE, так там проблема примерно такая-же - имеем дерево команд, надо сделать их обход для анализа.
Не хочу сказать, что это лучшее решение, но я делал так:

Имеем список TTaskList, элементы которого (TTaskItem) хранят информацию об узлах, которые необходимо обработать.

При обработке узла, следующий узел добавляется в список для последующей обработки, типа TaskList.Push(Item). В случае ветвления добавляются все последующие узлы. И все.

Основной цикл выглядит примерно так:
while TaskList.Pop(Item) do begin
... // process Item
end;

Т.к. в TaskList элементы добавляются/удаляются достаточно интенсивно, процедуру выделения памяти в нем надо делать с некоторым capacity, чтобы небыло частых релокейтов памяти.

Также имеется еще один массив уже обработанных элементов - чтобы небыло бесконечных заходов в циклы и повторных обработок узлов. Новый элемент добавляется в TaskList только если он отсутствует в данном списке. Элементы списка отсортированы по QuickSort. Проверка на наличие элемента в списке осуществляется аналогичным алгоритмом (типа QuickSearch).

P.S. Со стеком и рекурсией советую не заморачиваться - по закону подлости, тебе его когда-нибудь все равно не хватит, сколько бы ты не поставил 1Мб, 16Мб и т.п.

Немножко сумбурно... Если честно. Конкретный пример ухода от рекурсии - ее раскрутки - лежит в qsort.c из MS-CRT. Глянь в инклудах к MS-компилятору. Они вывернулись за счет использования goto.
Что до обхода дерева. Опять ты меня смутил. Ты хоть скажи, какое дерево? AVL, RB, еще что-нибудь? Если дерево сбалансировано и высота невелика, то чего ты боишься рекурсии? Если же дерево несбалансировано и узлов ДЕЙСТВИТЕЛЬНО много, ну, тогда раскрути рекурсию...
Это так, мое дилетантское мнение.

volodya
Если дерево сбалансировано и высота невелика, то чего ты боишься рекурсии?

Абсолютно согласен. А если дерево не сбалансировано, то ето уже не дерево и тебе точно не нужно. :)

Может, имело смысл задавать этот вопрос на форуме Алголиста?

Или почитать учебники? Кнут? Вирт? Ахо-Ульман? Кормен-Лейзерсон-Ривест? ... :)

captain cobalt

Мне, ей богу, вы перестаете нравится, сэр.
Единственная радость для меня в этом форуме, помимо отдела книжек, куда постянно пытаются нагадить зеленые чукчи, является раздел A&O.
Я строго за то, чтобы форум пополнялся ХОРОШИМИ вопросами. Если все мы здесь начнем отвечать неучам как вешать иконочку в трее или компилировать файл - то это путь к вырождению и я уйду отсюда.
Хороших вопросов в форуме мало. Мало кто поднимает СЛОЖНЫЕ темы системного программирования, сложные вопросы алгоритмизации. Тех людей, что задают такие вопросы - терять грех. Их надо пытаться удержать. Мне казалось, что ты из таких. Так неужели не понимаешь настолько очевидных вещей?

Если кратко сформулировать первоначальный вопрос, то получится вроде:
"какие бывают способы обхода дерева и как их реализовать".
Это что, хороший вопрос? Сложная проблема алгоритмизации?
Мне вообще непонятно, как можно знать, что такое деревья,
но не знать как их обходить. За такие вопросы на форуме алголиста
тут же как следует напинали бы. Вот и ты, volodya, начинаешь громко топать
ногами, когда сюда приходят задавать вопросы даже не погуглив перед этим.
По-моему первоначальный вопрос как раз из этой же серии...

Хорошие вопросы - это конечно хорошо :)
Хотите, могу набросать сюда кучу интересных задач?
Только мне будет не очень интересно, потому что знаю ответ...
Вот, например, упражнение на заданную тему:

Предложить модификацию алгоритма обхода Дойча-Шора-Вейта,
при котором на вершинах не делается никаких пометок, и
в дерево не добавляются новые узлы.

Указание: означенный алгоритм позволяет обойти дерево без
использования рекурсии (!) И без заведения дополнительного
стека (!). Основная идея заключается в том, чтобы, спускаясь
по дереву временно изменять поля ссылок так, чтобы они
указывали на родителей и по ним можно было подняться обратно,
восстановив их. Фактически, нужно найти такое преобразование
вершины, которое при двойном применении уничтожает само себя,
и чтобы при помощи одного и того же кода можно
было спуститься по дереву, а потом подняться обратно наверх...

dz 3BePIOra, попробуй это сделать. Это будет красиво.
И никакой опасности переполнения.

captain cobalt
1. dz 3BePIOra не причём, он же написал, что постит от моего имени.

2. Я тебя прекрасно понял, сажусь за теорию…

IceStudent
И тем не менее, заинтересовала меня эта тема, а особенно ответ captain cobalt... Надо пообщаться со знающими людьми, может чего интересного по данному вопросу накопаю... :)

„Предложить модификацию алгоритма обхода Дойча-Шора-Вейта,
при котором на вершинах не делается никаких пометок, и
в дерево не добавляются новые узлы. “

C=tree

P=0
if(C) do{
  if(C->L){
    t=C->L
    C->L=C->R
    C->R=P
    P=C
    C=t
  }else if(C->R){
    t=C->R
    C->L=P
    C->R=0
    P=C
    C=t
  }else{
    t=P
    P=C
    C=t
  }
}while(P)

Как оно работает:
p - предок
c - текущий узел
l - левое поддерево
r - правое поддерево

Значения P, C->L и C->R при С=с
1) в начале обхода поддерева:
p l r
2) при возврате из левого поддерева:
l r p
3) при возврате из правого поддерева:
r p l

Щас проверю ;)

Кажется, не совсем работает. ;)

Дерево из двух вершин.
Одна является левым потомком другой.
Срабатывает первая ветка if.
Указатель на потомка обнуляется.
Далее зацикливание по третьей ветке...

У меня и картинка есть 8)

_870537676__treewalk.png

Действительно не работает, придется использовать еще один маркер, отличный от маркера пустого поддерева(назовем его #):

T=tree
C=#
if(T!=NULL) do{
  if(T!=NULL)
  {
    temp=C
    C=T
    T=temp
  }
  temp=C->L
  C->L=C->R
  C->R=T
  T=temp
}while(T!=#)