Помощь - Поиск - Пользователи - Календарь
Полная версия: Хранение дерева в эвм
Форум «Всё о Паскале» > Разработка ПО, алгоритмы, общие вопросы > Алгоритмы
John
Привет, помогите пожалуйста!!
Придумайте(не реализовать, только придумать) способ хранения дерева с произвольным ветвлением, при котором в каждой вершине хранятся всего два (а не три, как в схеме "левый ребенок-правый сосед") указателя плюс одна булева переменная.
Заранее спасибо!
andriano
для одного элемента, очевидно record с двумя указателями и одной булевой переменной.
Для дерева либо массив, либо список (в последнем случае в структуру добавляется указатель или два на предыдущий (последующий) элементы списка).
мисс_граффити
Цитата
(а не три, как в схеме "левый ребенок-правый сосед")

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


да.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.