ArtiSКто подскажет, как организовать в таком дереве поиск (получить указатель узел, имея ID узла)? Нужно еще определить отношения между узлами. Но вообще в таком дереве (из-за наличия PParent) все традиционные алгоритмы на дереве (поиск, обходы, вставка, удаление, если нужно - балансировка) итеративны.

Предполагая порядок такой, что ребенок содержит меньшие значения, правый сосед - большие, поиск выглядит примерно так:

Melanito teras
данное предложение будет работать верно если id создаётся в нужном порядке, тогда можно и сравнить id < p^.id . а если нет?
id - это номер. не думаю, что при вставке нового узла всё дерево будет перенумеровано в правильном порядке. Не совсем так - просто при модификации дерева (это общее свойство всех деревьев поиска) нужно обеспечивать выполнение того-же самого инварианта. Например, делая вставку нового элемента в дерево - находить место для вставки в зависимости от такого-же сравнения. Это и будет соблюдением инварианта - а без него дерево поиска вообще построить не удастся.
Здесь я предположил один инвариант и написал для него процедуру поиска. Конечно, это самый простой, но, возможно, не самый любопытный инвариант - потому, что реально, в результате получается обычное бинарное дерево. Но, чтобы написать что-то более осмысленное, нужно иметь представление о предметной области. А именно - что нужно хранить, какие требуются алгоритмы, и ограничения.

Чтобы показать, что рекурсия здесь не нужна - можно набросать обход дерева в глубину (написано быстро и на глаз - так, что может содержать ошибки и неоптимальности, но суть все равно - верна) Цикл печатает дерево в инфиксном порядке (a+b). Другие порядки (префиксный +ab, постфиксный ab+) легко делаются из этого путем перестановки print()

Процедуры модификации работают используя указатель parent подобным образом.

ИндейЕврейский teras
p = p->parent;


Гы гы, насмешил! Так не честно - дерево само себе стек, вот тебе стек и не нужен.

В реале так редко бывает, что тебе позволительно строить такие деревья. Например, если дерево иммутабельно, и одна и та же ветка может принадлежать нескольким разным родительским узлам - разным версиям дерева. Вот это уже очень частый случай. Хрен тут что сделаешь без рекурсии или явного стека. Ну, если подходить с такой позиции, то и список, и массив, и переменная - это стек. А насчет реала не буду спорить - посмотри заглавный пост, что просили, то и написал. В таких условиях можно сделать итеративную реализацию для всех (по меньшей мере - большинства) типичных алгоритмов.
Кстати, запросы к структурам - они разные бывают. Всегда можно отслеживать владельца, вопрос только - что накладнее. И все. Например, у меня есть ощущение, что и в твоей структуре можно это делать. Причем разными способами (с точки зрения потребления памяти, монопольного доступа и т.д). А что узлы будут потреблять больше памяти - это не важно. Лишь бы исполнялось основное свойство итеративных алгоритмов - константное потребление памяти при исполнении.