Хранение дерева в эвм Опции

[John]

Привет, помогите пожалуйста!!
Придумайте(не реализовать, только придумать) способ хранения дерева с произвольным ветвлением, при котором в каждой вершине хранятся всего два (а не три, как в схеме "левый ребенок-правый сосед") указателя плюс одна булева переменная.
Заранее спасибо!

[Michael_Rybak]

один на вершину
второй на левого ребенка
третий на правого соседа

скорее, все-таки, не на вершину, а на родителя.

т.е. в каждом узле хранятся три указателя: отец, правый брат, левый сын.

чтобы обойтись двумя указателями и булевой переменной, сохранив при этом возможность последовательного обхода дерева с такой же временной сложностью, можно хранить указатель на отца не в каждом узле, а только в том, у которого нет правого брата.

получится, что для того, чтобы подняться от данного узла к отцу, нужно обойти всех братьев, начиная от этого узла, слева направо, и дойдя до конца, подняться к отцу. сложность этой операции увеличилась, но при последовательном обходе она не используется.

таким образом, первый указатель всегда будет указателем на левого сына, а булевая переменная будет задавать смысл второго указателя: true, если это указатель на правого брата, и false, если на отца.