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

[John]

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

[Michael_Rybak]

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

да, именно так.

а где эту вершину тогда хранить?? вспомогательной переменной?

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

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

что значит "как узнать его вершину"? т.е. что значит "как узнать вершину элемента"?

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

или элемент который содержит указатель на отца(вершину выше уровнем) - это и будет являтся вершиной для всех узлов этого уровня??

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

только не "этого уровня", а "этой группы братьев" (группы узлов с общим отцом).

тут получается, что если вершина имеет правого брата, то у нее булевая переменная равна true, иначе если на отца(вершину выше уровнем), то false???

да.