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

[John]

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

[andriano]

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

[мисс_граффити]

(а не три, как в схеме "левый ребенок-правый сосед")

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

[John]

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

Сообщение отредактировано: John - 6.05.2008 15:43

[andriano]

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

[John]

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

[andriano]

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

[John]

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

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

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

[Michael_Rybak]

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

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

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

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

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

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

[John]

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

можно хранить указатель на отца не в каждом узле, а только в том, у которого нет правого брата.

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

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

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

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

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

[Michael_Rybak]

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

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

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

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

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

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

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

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

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

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

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

да.