Мое почтение всем. Работал давеча с деревом -- обходил слева-направо, стали интересны нерекурсивные методы обхода. Подумав головой, пришел к выводу, что это можно сделать только имея в каждом узле поле, которое содержит признак -- были ли мы в правом поддереве, или нет. Т.е. получилось нечто в роде: Код (Text): ptr = root; while(1) { //тут делаем что хотим. //если можно идти влево -- всегда идем влево. if (ptr ->left) { ptr = ptr ->left; } else { //раз нельзя -- будем подниматься по всем узлам, // пропуская все, где мы уже были справа. ptr = ptr ->parent; while (ptr ->parent && ptr ->traversed) { ptr = ptr ->parent; } //если дошли до корня, и побывали у него справа -- // дерево обойдено. if (ptr ->parent == NULL && ptr ->traversed) break; //а раз нет -- ставим признак и идем вправо. ptr ->traversed = 1; ptr = ptr ->right; } } Так вот, мне интересно, можно ли обойти дерево без введения признака? Варианты с самодельным стеком я откидываю, т.к. это шило на мыло (ну, не так, конечно, но все же). Думаю, что без признака нельзя, но вдруг все же можно?
Mika0x65 из каждого узла выходит k ветвей: достаточно знать сколько ветвей мы прошли в узле и общую сумму пройденных узлов- отсюда и считается на сколько узлов в верх нужно прыгнуть.
Mika0x65 Зависит от дерева. Если соседние узлы (? siblings) упорядочены и определена функция сравнения узлов(равно - не равно), то можно и без признака. Иначе потребуется хранить дополнительную информацию о пройденном пути, которую тогда можно будет обозвать "самодельным стеком" (хотя это и не обязан, естественно, быть стек).
Stiver не важно упорядочено дерево или нет: нужно лишь перебирать ветви каждого узла (не важно в каком порядке, если требуеться полный обход дерева), а затем переходить к соседнему узлу, вот, например: a1->b1->c1 a1->b1->c2 a1->b2->c3 a1->b2->c4
UbIvItS А можно подробнее? Я не совсем понял, что даст кол-во узлов. Лучше всего псевдокод, типа того, что я привел на asm/C.
Mika0x65 код строкать как-то влом - объясню на пальцах: кол-во ветвей на нижнем этаже равно A^k, A - колво веток в узле; k- высота дерева. спускаемся в нижнюю левую ветвь дерева и начинем обход всех ветвей в узле; как пройдено A ветвей мы смотрим с какого верхнего узла нужно проводить спуск в низ (мда........ несколько витеевато я настрокал)) давай по другому: представь себе число с основанием A и колвом разрядов k ====> перебор всех его значений и есть обход дерева.
Писал прям в форум, не факт что работает но вроде должно Предположение - дерево, у которого по две ветви из каждого узла, дерево полное. Код (Text): p = root -> right -> right -> right -> right -> right; // самая правая вершина unsigned i = 1 << 5; // для дерева высоты 5 while (--i) { signed c; donothing(p); __asm bsf ecx, i; __asm mov c, ecx; __asm push ecx; while (c--) p = p -> parent; donothing(p -> parent); // если обходить не только листья p = p -> parent -> left; __asm pop c; while (c--) p = p -> right; } donothing(p);
Mika0x65 лано, давай для удобства бинарное дерево рассмотрим в 3 этажа: первая крайняя ветвь с лева имеет код 100b, а с права 111b, тоесть обход всех ветвей - это перебор всех значений счётчика. теперь давай вспомним особеность древовидной СД: мы не можем к произвольному узлу обратиться произвольно - нужно пройти всех его прародителей. тоесть, для обращение к соседу мы должны дойти до их общего родителя в верх и только затем спустится к соседнему узлу на том же уровне, например: узлы a->b1->a1 & a->b2->a3 имеют общего родителя a[\b], тогда как a->b1->a1 & a->b1->a2 имеют общего родителя b1.
Где-то на форуме эта задача была, но найти не смог. Решение там было примерно такое: cur - текущий узел from - узел из которого пришли Код (Text): cur = root; from = END;// маркер для определения конца обхода, не равный NULL do{ do{ temp = cur->left; cur->left = cur->right; cur->right = from; from = temp; }while(from==NULL); [добавлено] if(from>cur->left && from>cur->right) //сравниваются адреса, END должен быть больше чем NULL { //здесь обрабатываем узел //узлы будут обрабатываться по одному разу //но произойти это может как при спуске, так и при подъёме или переходе в другое поддерево } [/добавлено] temp = cur; cur = from; from =temp; }while(cur!=END); [удалено]Правда каждый узел здесь посещается несколько раз, как это обойти пока не знаю, возможно есть и другие баги.[/удалено]
Помойму без разметки во время прохода, или повторного посещения сделать это никак нельзя. Единственная надежда это опираясь на мысли UbIvItS следить за путевой меткой узлов. Спускаемся влево - дописываем ноль, спускаемся вправо еденицу, поднимаемся, убираем один разряд. Таким образом образуемое число всегда должно возрастать, и мы защищены от повторов. Но узнать в каком направлении мы идём по узлу - это значительная проблема. Спуск и подъём отличить алгоритм отличать позволяет. А вот лево от право нет. Единственная зацепка, это принудительно поддерживать узлы в неком специфичном состоянии, когда адрес родительского и дочерних узов расположены в памяти с определённом порядке. Скажем родитель по адресу меньше нашего узла. А у сынков, второй узел по адресу меньше первого. Тогда сравнивая адрес можно догадываться о направлении. Для этого придётся как минимум для кажлого узла держать адрес родителя, чтобы при обмене телами между родителем и текущим узлом, можно было коректировать ссылку на родителя (тут точнее даже нужна ссылка на родителя, а ссылка на ссылку на текущий узел внутри родителя нашего узла). Ну а если можно сравнивать сами значения, то ещё проще... Так что стоит ли оно такого гемора, если можно просто выполнять разметку узлов при обходе?
Proteus что такое узел дерева - это просто сишная struct c ссылками на другие узлы ==========> перебор этих ссылок в узле вполне определён, например, если адрес у нас 4 байта, то смещаясь в структуре(узле) на 4*i байт мы получаем новую ветвь. счётчик позволяет исключить повторы.
Это типа вариант с "самодельным стеком" чем тебе такое решение не нравится я х.з. По-крайне мере оно точно эффективнее чем выделение признака или того хуже создания массива пройденных вершин. Обход в глубину Код (Text): proc Tree Tree push esi ;Начинаем обход с корня дерева mov esi, [Tree.Root] test esi, esi ;А есть ли корень? je .lbEnd ;Сохраняем значение стека mov edx, esp .lbNextNode mov eax, DWORD[esi] ;TreeNode.Node Указатель на массив детей элемента дерева mov ecx, DWORD[esi+4] ;TreeNode.NodesCount Количество детей в эелементе дерева ;В esi хранится текущий элемент дерева тут его можно вывести на экран или куда там еще test eax, eax ;Проверяем, а есть ли в элементе дерева что-нибудь? je .lbGetParent ;Если нет, то на уровень выше test ecx, ecx je .lbGetParent push eax ;Сохраняем в стеке нашу текущую позицию push ecx .lbNextNodeItem: mov esi, DWORD [eax+ecx*4-4] ;переходим к самому последнему ребенку дерева test esi, esi ;проверяем его на 0 jne .lbNextNode ;если он не нулевой, то работаем с ним как с новым элементом дерева sub ecx, 1 ;иначе уменьшаем счетчик элементов на 1 jnz .lbNextNodeItem ;если у нас еще остались непросмотренные элементы, то берем следующий элемент .lbGetParent: ;Пытаемся вернуться на уровень вверх cmp edx, esp ;Проверяем можно ли поднятся на уровень вверх je .lbEnd ;Если нельзя, то мы все уже обработали надо выходить pop ecx ;Восстанавливаем верхний уровень pop eax sub ecx,1 ;Так как в этом уровне 1 элемент мы только что обработали уменьшаем счетчик jnz .lbNextNodeItem ;Если на этом уровне остались еще необработанные элементы, то обрабатываем их jmp .lbGetParent ;Иначе переходим еще на уровень выше .lbEnd: ;Это конец pop esi ret endp
фишка в том что решение не намногим лучше самой рекурсии. Вызываешь ты функцию обхода и ставишь стек самодельный или родной , смысл уже теряется.
в узле порядок ссылок определён. Но мы обходим дерево производя при этом престройку ссылок (перезацепку узлов). Поэтому идём вы по узлу вверх, влево, вправо, Процедура в какдом направлении используется одна и та же. Сама трудность в том чтобы понять в каком направлении идёт обход.
Proteus 1. Ну оно лучше рекурсии хотя бы тем, что жрет памяти минимум на треть меньше ну и предположительно быстрее. 2. Использование идентификаторов внутри элементов дерева так же требует ровно столько же памяти (4 байта на индекс и 4 байта на адрес возврата). Плюс неэффективно в многопоточных системах. 3. Тем что ты располагаешь элементы дерева в памяти особым образом (чем выше элемент в дереве тем меньше его адрес), ты превращаешь дерево в обычный массив. И эффективность работы с таким деревом будет такая же как с обычным массивом. 4. Использование отдельного массива для хранения счетчиков это вообще полный абзац. Глубина дерева заведомо ограничена размером массива. Уж лучше рекурсия. 5. А если алгоритм будет понескольку раз проходить один и тот же элемент, то тут вообще хрен знает какое получится быстродействие Достаточно аргументов?
