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

для одного элемента, очевидно record с двумя указателями и одной булевой переменной.
Для дерева либо массив, либо список (в последнем случае в структуру добавляется указатель или два на предыдущий (последующий) элементы списка).

а что за схема? куда третий указатель?

так это понятно, что надо брать структуру и через список - это делать. Вопрос можно еще так переформулировать, как представить схему "левый ребенок-правый сосед" (я думаю это сильносвязывающие дерево, я только с бинарными работал) используя два указателя плюс одна булева переменная(структуру).???

Сформулируй, пожалуйста как-нибудь иначе.
Что значит "представить"? Если я скажу "указателями", такой ответ подойдет?
И еще: мне кажется лучше не прибегат к жаргону типа "левый ребенок", "правый сосед", "сильносвязывающее дерево", а объяснить с использованием базовых понятий.

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

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

Термин "левый ребенок- правый сосед" подразумевает 3 указателя:
один на вершину
второй на левого ребенка
третий на правого соседа(т.е элемент находящийся на том же уровне)

вот тут можно еще посмотреть как это примерно выглядит
http://www.sql.ru/forum/actualthread.aspx?tid=471299

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

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

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

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

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

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

Чего то я не понял!! (((



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


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



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

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



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



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

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



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

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



да.