Я наконец понял что написал попробую теперь другим обяснить 8) Когда в некоторый узел мы приходим сверху: from == parent cur == (left,right) Эти указатели переставляются местами: from == left cur == (right,parent) и дальше обменивая from и cur мы начинаем обходить левое поддерево, при возврате из левого поддерева картина будет точно такая же. Еще раз переставляем указатели: from == right cur == (parent,left) обмениваем from и cur и обходим правое подерево. И еще раз переставляем указатели: from == parent cur == (left,right) и обменивая from и cur возвращаемся к родительскому узлу Маркер END нужен для того чтобы определить момент окончания обхода, поскольку у корня нет родителя. Чтобы исключить обработку каждого узла по нескольку раз производится проверка что from > cur->left и cur->right. При этом END и адрес любого узла дерева должны быть больше чем NULL.
Black_mirror насчёт окончания обхода дерева: лучше хранить общее колво ветвей, так как это поволяет избежать лишних проблем. и, далеко не в каждом дереве, все ветви не NULL.
UbIvItS А если нам попалось дерево про которое мы не знаем сколько в нём ветвей? Про NULL я ничего не сказал в описании, но алгоритм его успешно обрабатывает, посмотри внутренний цикл.
Black_mirror это не страшно - алгос должен пройти A ветвей в корне, тогда он заканчивает свою работу. я б релизил такой алгос через счётчик, а каждый узел должен содержать ссылку на ближайшего родителя, тогда можно организовать наиболее оптимальный обход.
Тем временем, знакомый предложил проверять, в каком поддереве мы находимся, сравнивая текущий указатель с указателем right родителя текущего узла. Признак в таком случае не нужен. В итоге получилось примерно так: Код (Text): NODE *ptr = &n1; while(1) { if (ptr ->left) { ptr = ptr ->left; } else { while (ptr ->parent && ptr == ptr ->parent ->right) ptr = ptr ->parent; if (ptr ->parent == NULL) break; ptr = ptr ->parent ->right; } }
Mika0x65 Этот алгоритм упадёт при возврате из левого поддерева если правое отсутствует, на строке: ptr = ptr ->parent ->right;
Mika0x65 Угу, именно это я и имел в виду в самом начале: постоянный порядок (здесь левый-правый) и определено сравнение (здесь по адресу). Black_mirror Почему упадет, parent ведь проверяется на существование: while (ptr ->parent ...
Stiver Действительно, на этой строке не упадёт, тут ptr просто станет равен NULL, а упадёт на проверке условия if(ptr ->left) при следующей итерации.
Black_mirror Можно добавить while (ptr ->parent && (ptr ->parent ->right == NULL || ptr == ptr ->parent ->right)). Но это уже мелочи..
) - какое может быть сравнение адресов - попытка реализации дерева через массив убивает все плюсы этой СД: узлы создаються динамично в нормальной реализации..... а насчёт: "алгос в студию" ====> я уже всё сказал, подумайте пока сами, а если не поймёте - тогда настрокаю....
UbIvItS Алгоритм который привёл Mika0x65 на этой странице после небольших исправлений сделанных Stiver'ом может обойти любое бинарное дерево в узлах которого есть ссылка на предка, тому алгоритму что привёл я ссылка на предка не нужна, но он в процессе работы перестраивает дерево. Оба этих алгоритма можно модифицировать так, что они смогут обходить не только бинарные деревья, причём без всякой рекурсии или самодельных стеков. А вот где ты увидел в них массивы, и почему ты предполагаешь что на нижнем уровне дерева A^k узлов я не понимаю.
Black_mirror мне непонятно как идёт в этом алгосе переход на ветки соседних узлов. считай, на примере бин. дерева: корень порождает две ветки; каждая ещё по две итд. =============> 2^k (k-высота дерева), таким образом счётчик позволяет задать обход дерева. цитата Stiver'а узлы разбросанны по неупорядоченным адресам!!
