Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Представление свободного дерева в виде бинарного, возможно ли это вообще? 
V
    Опции темы
zim22
Дата 5.6.2009, 12:39 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


depict1
****


Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: нет
Всего: 69
Необходимо из свободного дерева получить бинарное. 
Рисунок свободного дерева:
user posted image

Я пытался конвертировать(рис.ниже), но когда до точки № 9 дохожу - не понимаю, что делать дальше, т.к. в этой точке у нас три разветвления. А бинарные деревья ограничены двумя поддеревьями... Надеюсь на вашу помощь.
user posted image


--------------------
C++ FAQ Lite
PM MAIL   Вверх
Soah
Дата 5.6.2009, 12:53 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 512
Регистрация: 18.2.2009

Репутация: 5
Всего: 54
ИМХО, никак.

Цитата(zim22 @  5.6.2009,  12:39 Найти цитируемый пост)
Необходимо из свободного дерева получить бинарное.

zim22, зачем?
может есть другое решение
PM MAIL   Вверх
zim22
Дата 5.6.2009, 13:08 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


depict1
****


Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: нет
Всего: 69
Цитата(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.


Это сообщение отредактировал(а) zim22 - 5.6.2009, 13:19


--------------------
C++ FAQ Lite
PM MAIL   Вверх
Soah
Дата 5.6.2009, 13:14 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 512
Регистрация: 18.2.2009

Репутация: 5
Всего: 54
zim22, новые точки добавлять можно?

              4
            /    \
           p       5  
          /   \
         6     9
PM MAIL   Вверх
zim22
Дата 5.6.2009, 13:21 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


depict1
****


Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: нет
Всего: 69
Цитата(Soah @  5.6.2009,  13:14 Найти цитируемый пост)
новые точки добавлять можно?

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

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

Цитата

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


Это сообщение отредактировал(а) zim22 - 5.6.2009, 13:25


--------------------
C++ FAQ Lite
PM MAIL   Вверх
Soah
Дата 5.6.2009, 13:37 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 512
Регистрация: 18.2.2009

Репутация: 5
Всего: 54
Цитата(zim22 @  5.6.2009,  13:21 Найти цитируемый пост)
скорее всего есть какая хитрость

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

Это сообщение отредактировал(а) Soah - 5.6.2009, 13:43
PM MAIL   Вверх
zim22
Дата 5.6.2009, 13:45 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


depict1
****


Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: нет
Всего: 69
Цитата(Soah @  5.6.2009,  13:37 Найти цитируемый пост)
всё-таки надо добавлять узлы, посмотри рисунок 5.22 и представление дерева.

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


--------------------
C++ FAQ Lite
PM MAIL   Вверх
DocBox
Дата 25.6.2009, 18:32 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 6
Регистрация: 22.4.2008

Репутация: нет
Всего: нет
Необходимо строить так...

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

в вашем примере..   / - сын  \ - сосед... 
    
   9
  /  
10
  \
   11
     \
      12
      /
     13
     /
   15
   / \
 17  14
.. и тд.

Надеюсь понятно обьяснил.
PM MAIL   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "Алгоритмы"

maxim1000

Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000.
 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Алгоритмы | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0874 ]   [ Использовано запросов: 20 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.