Форум программистов [Powered by Invision Power Board]

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

Форум программистов > Алгоритмы > Представление свободного дерева в виде бинарного

Автор: zim22 5.6.2009, 12:39

Необходимо из свободного дерева получить бинарное.
Рисунок свободного дерева:
http://xmages.net/show.php/258647_tree.gif.html

Я пытался конвертировать(рис.ниже), но когда до точки № 9 дохожу - не понимаю, что делать дальше, т.к. в этой точке у нас три разветвления. А бинарные деревья ограничены двумя поддеревьями... Надеюсь на вашу помощь.
http://xmages.net/show.php/258648_tree2.gif.html

Автор: Soah 5.6.2009, 12:53

ИМХО, никак.

Цитата(zim22 @ 5.6.2009, 12:39

)

Необходимо из свободного дерева получить бинарное.

zim22, зачем?
может есть другое решение

Автор: zim22 5.6.2009, 13:08

Цитата(Soah @ 5.6.2009, 12:53

)

зачем?

это задание из книжки "Фундаментальные алгоритмы на С++"(стр.225, задание 5.56) (Роберт Седжвик).

Цитата

Приведите представление свободного дерева, показанного на рис. 5.20(мой верхний рисунок) в форме дерева с корнем и бинарного дерева.

Я думаю решение есть 100%, т.к. в противном случае в задаче было бы дополнительно указано следующее

Цитата

если построить дерево невозможно, то объясните почему

***
в англ.версии книги задание звучит так:

Цитата

Give representations of the free tree in Figure 5.20 as a rooted tree and as a binary tree.

Автор: Soah 5.6.2009, 13:14

zim22, новые точки добавлять можно?

              4
            /    \
           p       5
          /   \
         6     9

Автор: zim22 5.6.2009, 13:21

Цитата(Soah @ 5.6.2009, 13:14

)

новые точки добавлять можно?

я над этим уже тоже думал. если точки добавлять - то можно будет представить дерево в бинарном виде smile

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

Цитата

Лемма 5.4. Существует однозначное соответствие между бинарными деревьями и упорядоченными борами.

Цитата

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

Автор: Soah 5.6.2009, 13:37

Цитата(zim22 @ 5.6.2009, 13:21

)

скорее всего есть какая хитрость

посмотри рисунок 5.22 и представление дерева.

Автор: zim22 5.6.2009, 13:45

Цитата(Soah @ 5.6.2009, 13:37

)

всё-таки надо добавлять узлы, посмотри рисунок 5.22 и представление дерева.

http://xmages.net/show.php/258911_tree3.gif.html
я думал, что это два разных дерева, никак с друг с другом не связанных. оказалось - это различное представление одного и того же.
спасибо.

Автор: DocBox 25.6.2009, 18:32

Необходимо строить так...

для кажой вершины указывать. сына. и соседа.

в вашем примере..   / - сын  \ - сосед...

   9
  /
10
  \
   11
     \
      12
      /
     13
     /
   15
   / \
17  14
.. и тд.

Надеюсь понятно обьяснил.