Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Алгоритмы _ Хранение дерева в эвм

Автор: John 5.05.2008 18:10

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

Автор: andriano 5.05.2008 21:25

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

Автор: мисс_граффити 6.05.2008 3:50

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

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

Автор: John 6.05.2008 15:38

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

Автор: andriano 6.05.2008 22:36

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

Автор: John 6.05.2008 23:39

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

Автор: andriano 6.05.2008 23:51

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

Автор: John 14.05.2008 23:30

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

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

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

Автор: Michael_Rybak 14.05.2008 23:48

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

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

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

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

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

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

Автор: John 15.05.2008 0:15

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

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


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

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


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

Цитата

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


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


Автор: Michael_Rybak 15.05.2008 0:58

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


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

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


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

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


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

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

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


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

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

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


да.