"Обратное дерево"

← →
AdMeen © (2008-10-08 07:55) [0]

Каким образом можно реализовать "перевёрнутое дерево",т.е. дерево наоборот.где ветви сходятся к корню
*--- |-----* *--- | |---* *--- | |-----* *---
Примерно вот так.

← →
Palladin © (2008-10-08 08:03) [1]

кроме картинки, построение "перевернутого дерева" ничем не отличается от построения нормального

← →
AdMeen © (2008-10-08 08:17) [2]

Но,вроде если в "обыкновенном" дереве мы имеем корень,от которого потом начинаем строить левую-правую ветвь,то здесь мы имеем 2-их родителей и 1 потомка.Если можно код.

← →
{RASkov} © (2008-10-08 08:20) [3]

Лучше скажи зачем это надо....

← →
Palladin © (2008-10-08 08:22) [4]

Type TNodePosEnum=(npLeft,npRight) PNode=^TNode; TNode=Record Parent1,Parent2:PNode; Caption:String; Pos:TNodePosEnum; End;

← →
Сергей М. © (2008-10-08 08:27) [5]

> AdMeen © (08.10.08 07:55)

"перевёрнутое дерево" - это обычное дерево, на которое ты смотришь расположившись вверх тормашками)

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

А "левый"/"правый" - опять же как посмотришь)

Я серьезно.

← →
oxffff © (2008-10-08 09:06) [6]

> AdMeen © (08.10.08 07:55)

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

← →
MsGuns © (2008-10-08 09:22) [7]

>oxffff © (08.10.08 09:06) [6]
>Нужно использовать "обычное" дерево, но с обратным способом обхода.

И тогда получится то, что нарисовано в сабже ? Т.е. два или более узлов будут иметь одного "ребенка" ?

← →
oxffff © (2008-10-08 10:21) [8]

> MsGuns © (08.10.08 09:22) [7]

У меня получится как надо.

← →
MBo © (2008-10-08 10:24) [9]

Для какой задачи это нужно?

← →
ANB (2008-10-08 10:48) [10]

В базу надо запихать ?

← →
Ega23 © (2008-10-08 10:52) [11]

специальные ini-файлы надо использовать

← →
MsGuns © (2008-10-08 11:01) [12]

>oxffff © (08.10.08 10:21) [8]
>У меня получится как надо.

При условии использования "обычного" TTreeView ?
Если это не военная тайна, приведите, пожалуйста, код

← →
oxffff © (2008-10-08 11:10) [13]

> MsGuns © (08.10.08 11:01) [12]

Вы что не знаете способ обхода от листьев к корню?

← →
{RASkov} © (2008-10-08 11:21) [14]

> [13] oxffff © (08.10.08 11:10)

Самое главное найти самые дальние листы :)
Я что-то пока не могу представить себе четкий алгоритм прохода по всему дереву начиная с листьев и до корня...)
Такое ощущение, что можно "триста" раз бегать по этому дереву по одному и тому же пути пока все ветки не будут пройдены....
Нет, что-то здесь не так :)

← →
oldman © (2008-10-08 11:27) [15]

> oxffff © (08.10.08 11:10) [13]
> Вы что не знаете способ обхода от листьев к корню?

Имхо, путь к корню единственен.

← →
{RASkov} © (2008-10-08 11:40) [16]

> [15] oldman © (08.10.08 11:27)
> Имхо, путь к корню единственен.

Вот смотри..... Есть пять конечных листьев с одним общим узлом..... сколько будет путей к корню? :) пять. только вся разница в последнем листе....
1n*--|
2n*--|
3n*--|---1n-1*
4n*--|
5n*--|

← →
{RASkov} © (2008-10-08 11:44) [17]

Что-то я "загнался".... Оно и в другую сторону(от корня к листьям) тоже самое...
Но я хотел сказать, что от корня к листьям мы будем по одному разу в каждом узле, а наоборот(к корню) - кучу раз придется бегать по дереву.... имхо.

← →
{RASkov} © (2008-10-08 11:48) [18]

В общем бред как обычно :)
Дерево строится(растет) от корня к кроне, но не наоборот и точка. иначе это уже не дерево...)

← →
Anatoly Podgoretsky © (2008-10-08 11:48) [19]

> MsGuns (08.10.2008 9:22:07) [7]

На рисунке, что-то похожее на коноплю.

← →
{RASkov} © (2008-10-08 11:54) [20]

> [19] Anatoly Podgoretsky © (08.10.08 11:48)

На рисунке ответ на вопрос в ветке. Там нарисованы - Вилы :)

← →
oxffff © (2008-10-08 11:56) [21]

> oldman © (08.10.08 11:27) [15]
>
> > oxffff © (08.10.08 11:10) [13]
> > Вы что не знаете способ обхода от листьев к корню?
>
>
> Имхо, путь к корню единственен.

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

← →
Vlad Oshin © (2008-10-08 11:57) [22]

> Имхо, путь к корню единственен.

+1

← →
Vlad Oshin © (2008-10-08 11:58) [23]

> oxffff © (08.10.08 11:56) [21]

а нафиг?
автор чего хотел?

← →
Anatoly Podgoretsky © (2008-10-08 12:00) [24]

> {RASkov} (08.10.2008 11:54:20) [20]

А ниже грабли.

← →
{RASkov} © (2008-10-08 12:02) [25]

> [24] Anatoly Podgoretsky © (08.10.08 12:00)
> А ниже грабли.

В [16]-то ? :)

← →
oxffff © (2008-10-08 12:02) [26]

> Vlad Oshin © (08.10.08 11:58) [23]

Это для того, чтобы автор использовав алгоритмы "выращивания" обычного дерева, использовав обратный итератор имел представление о нем, как о перевернутом.

← →
{RASkov} © (2008-10-08 12:06) [27]

Путь-то к корню единственный... это от корня много путей расходятся...
Но автору нужно как-то умудрится свести все пути(пусть даже разной длины наверное) к единому истоку....
Не реально, имхо...
Т.е. он строит дерево изначально зная конечные ветки, но не знает где и как есть корень.... Это страшно :)

← →
oxffff © (2008-10-08 12:09) [28]

> {RASkov} © (08.10.08 12:06) [27]

Да какая разница как он, его строит, от А к B или B к A. Зная А можно получить единственный B. Зная B можно получить все A.

← →
{RASkov} © (2008-10-08 12:15) [29]

> Зная А можно получить единственный B

Это ему(автору) нужно знать изначально все A.... например их 300 получилось ну или пятьсот....
Собсно с бухты барахты можно построить дерево с такими входными данными..... но возможно могут получится "упавшие ветки" но это не страшно или как?(скорее вопрос автору)...

← →
MsGuns © (2008-10-08 15:19) [30]

>oxffff © (08.10.08 11:56) [21]
>Я говорю не про путь к корню. А про обход узлов от кроны к корню.

Юноша, у Вас, очевидно какие-то марсианские деревья. У обычных, земных, по ветке нельзя ОБОЙТИ все дерево. Вы просто упретесь в ствол и все. При этом все листья перед Вашим взором будут в кучу и определить какие из них к каким веткам относятся просто физически невозможно, сидя на стволе.

← →
AdMeen © (2008-10-08 16:21) [31]

На самом деле надо решить задачу,собственно сабж:
Написать программу для проведения соревнований по борьбе,вводить имена участников в поле Edit.Затем выводить имена участников пары,и поля для ввода очков.По окончании пар,вывести ход соревнований в виде дерева
Так что вот так вот:(

← →
Сергей М. © (2008-10-08 16:32) [32]

> Так что вот так вот

И ты, конечно же, сразу ломанулся в лес из "деревьев вверх ногами" ?)
А кто сказал, что соревнования должны проходить именно по олимпийской системе ?

← →
Vlad Oshin © (2008-10-08 16:33) [33]

> Написать программу для проведения соревнований по борьбе,

ключевое слово - по борьбе

← →
Palladin © (2008-10-08 16:39) [34]

тьфу... я то думал.... а оно то оказалось...

← →
Palladin © (2008-10-08 16:39) [35]

тут вообще деревьями и не пахнет...

← →
Сергей М. © (2008-10-08 16:40) [36]

> Palladin © (08.10.08 16:39) [34]

Вот так оно и всегда - думали про что-то страшное, а получилось как у Черномырдина)

← →
Сергей М. © (2008-10-08 16:43) [37]

> Palladin © (08.10.08 16:39) [35]

Ну почему ?
При олимп.системе запах вполне привычный)
Только вот автор никак не сообразит, что единый корень образуется лишь после окончания соревнований, т.е. после определения победителя в финале)

← →
AdMeen © (2008-10-08 16:44) [38]

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

То Сергей М.
Ломанулся :),других вариантов к сожалению не усматриваю:(

← →
Palladin © (2008-10-08 16:48) [39]

> При олимп.системе запах вполне привычный)

да, но от нормального дерева тут лишь - способ представления :) остальное все можно хранить в простом массиве массивов, по уровням соревнований, пока не останется только один! Маклауд какой нибудь.
типа
1. петя маша вася ИШ коля света рома АП
2. маша ИШ света АП
3. ИШ АП
4. ХЗ :))
5. ЮЗ на победителя :))

← →
Сергей М. © (2008-10-08 16:48) [40]

> AdMeen © (08.10.08 16:44) [38]

> Кто знаком с борьбой

Так ты программист или знаток борьбы ?)
Или по совместительству пытаешься освоить вполне родственное занятие ?)

> других вариантов к сожалению не усматриваю

А почему перевернутое-то ?
Ты объясни нам, бестолковым, мы ж не борцы в большинстве своем, а программисты ..

← →
Сергей М. © (2008-10-08 16:52) [41]

> от нормального дерева тут лишь - способ представления

Почему ? И способ организации хранения тоже ..

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

← →
AdMeen © (2008-10-08 16:55) [42]

Сергей М.
Довольно долгое время занимался. А так пытаюсь быть программистом :).
Palladin
Спасибо за совет буду пробывать таким способом.

Ну а всё таки,каким образом потом это всё можно вывести в виде дерева,как особо бестолковому объясните пожалуйста.

← →
Palladin © (2008-10-08 16:57) [43]

> Почему ? И способ организации хранения тоже ..

ну потому что, из двух выбран на уровень выше может быть только один, от этого и отталкиваемся, по проще опишу, скажем есть у нас ID участников от 1 до 8
массив 1 уровня: 1,2,3,4,5,6,7,8
массив 2 уровня: 2,3,6,7
массив 3 уровня: 3,7
и победитель: 7

дальше уже просто нужно только нарисовать по этим данным дерево...

← →
Palladin © (2008-10-08 16:58) [44]

> массив 1 уровня: 1,2,3,4,5,6,7,8

то есть, этот массив означает что 1 соревнуется с 2, 3 с 4 и тд...

← →
Сергей М. © (2008-10-08 16:58) [45]

> AdMeen © (08.10.08 16:55) [42]

> каким образом потом это всё можно вывести в виде дерева

С помощью компонента TTreeView.
Для большого количества участников - TDBTreeView.

← →
Сергей М. © (2008-10-08 17:03) [46]

> дальше уже просто нужно только нарисовать по этим данным
> дерево

Его можно и сразу "нарисовать", заполнив TTreeView заранее известными данными. А по ходу соревнований изменять св-ва узлов соотв.образом.

← →
han_malign © (2008-10-08 18:16) [47]

> в простом массиве массивов
.....
> массив 3 уровня

(участник,количество побед)
[0,0] [1,2] [1,2] [1,2] [2,1] [2,1] [3,0]
------------------
function Y_norm(fighter,victory: integer): integer; begin victory:= $FFFFFFFF shl victory; Result:= (fighter and victory)*2 + not victory; end; for i:= 0 to n-1 do with fv do for j:= 0 to v do DrawFighter(j*X_step+X_offs, Y_norm(i,j)*Y_step+Y_offs, Fighter[i]);

>Palladin © (08.10.08 16:48) [39]
>2. маша ИШ света АП
>3. ИШ АП

Щаз придет data с булыжником и щетками. И покажет и тебе, и ИШу, и АПу.
Еще и Юре рикошетом достанется ;)))

А где марсианин охфффф ? С секретом выращивания "обратных" деревьев ?

>AdMeen © (08.10.08 16:44) [38]
>Кто знаком с борьбой знают,что соревнования при приведённых участниках >проводятся именно по олимпийской системе.

Занимались бы вы, товарищ, тем, с чем знакомы, а именно борьбой ;)

> MsGuns © (08.10.08 15:19) [30]
> >oxffff © (08.10.08 11:56) [21]
> >Я говорю не про путь к корню. А про обход узлов от кроны
> к корню.
>
> Юноша, у Вас, очевидно какие-то марсианские деревья. У обычных,
> земных, по ветке нельзя ОБОЙТИ все дерево. Вы просто упретесь
> в ствол и все. При этом все листья перед Вашим взором будут
> в кучу и определить какие из них к каким веткам относятся
> просто физически невозможно, сидя на стволе.

Ну раз мы перешли на возраст, то тогда

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

> MsGuns © (08.10.08 20:34) [49]
> А где марсианин охфффф ? С секретом выращивания "обратных"
> деревьев ?

Что старый пердун подуматься не может?

> Сергей М. © (08.10.08 16:52) [41]
>
> > от нормального дерева тут лишь - способ представления
>
>
> Почему ? И способ организации хранения тоже ..
>
> Только однокоренное дерево образуется лишь в конце соревнований,
> а в ходе оных это еще не дерево, а заросли чепыжника -
> куча корней, из каждого из которых торчат ветки) ..

Чисто технически можно построить дерево изначально, зная количество участников, и атрибутировать узлы после проведения схватки. Можно динамически стыковать заросли чепыжника после проведения схватки в более крупные заросли чепыжника и так далее. :)

> Можно динамически стыковать заросли чепыжника после проведения
> схватки в более крупные заросли чепыжника и так далее. :
> )

Для MsGuns

Чисто технически это позволит доопределять количество листьев по необходимости в run time, сохранив при этом структуру дерева
и доатрибутировать узлы после проведения схватки и тут же добавлять родителя к этому дереву еще неатрибутированного его корня(то есть победитель не установлен). Таким образом в целом структура будет дерево, только сборка в обратном порядке.

> Каким образом можно реализовать "перевёрнутое дерево",т.
> е. дерево наоборот.где ветви сходятся к корню

Только нарисовать самому. А ещё, сетка может с двух сторон, к центру быть нарисована :)
1/8|- -|2/7 | | >-|?/?|->|?/?|<-|?/?|< | | 4/5|- -|3/6
Вот это уже не дерево, а куст :)) "Совокупность веток, растущих из одного места" (с)

>oxffff ©

Употребив к Вам слово "юноша", я имел в виду не возраст, а исключительно опыт и навыки в программировании. И, судя по [53] [54], явно переоценил - на юношу не тянете. Хоть и нахватались где-то "умных" слов (что такое "атрибутировать" - ни разу не слышал, это что-то типа "крышевать" или "фундаментить" по отношению к зданию, ага ?)

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

Все-таки боролись бы Вы лучше, мальчик ;)))

Посмотрел в анкету - хм.. 27 лет уже..
Вроде взрослый, а грубит и ругается как пацан с рогаткой. Анкета врет - Вам ведь не больше 20, точно ?

;)))

Сорри за офтоп, но хамство возмутило ;)

А если серьезно по теме, то турнирную сетку можно, конечно изобразить и в виде TTreeView (какая разница, слева напрво рисовать этапы или справа налево), но есть много минусов:

- стандартная отрисовка узлов в TTreeView некрасивая, поэтому придется отрисовывать все "ручками" в соответствующем событии
- компонент не "умеет" ветвление рисовать в несколько сторон (как, например, показано в [55]
- нельзя вместо "пары" нарисовать таблицу, если вместо одного поединка предполагается круговой турнир (как, например, в футбольных турнирах, где круговые турниры чередуются с олимпийкой)
...

Можно, конечно, задачу предельно упростить, но тогда вопрос - зачем именно тривью, если много проще использовать для этих целей например TListView или даже TDrawGrid (и даже, страшно подумать !,- TStringGrid)
В общем вариантов море и, ИМХО, TTreeView в данном случае далек от оптимального

И последнее
Я, конечно, могу запамятовать, но на соревнованиях борцов (не помню какого стиля) раньше применялись именно круговые турниры. Не знаю повсеместно ли, но на Олимпиадах вроде да.

To MsGuns ©
>>Занимались бы вы, товарищ, тем, с чем знакомы, а именно борьбой ;)

Вы уж пожалуйста извините,но давайте я сам буду решать чем мне заниматься.Не удержался,сорри за оффтоп.

Каждый программист должен вырастить дерево и родить наследника.

> AdMeen © (09.10.08 00:54) [59]
>
> To MsGuns ©
> >>Занимались бы вы, товарищ, тем, с чем знакомы, а именно
> борьбой ;)
>
> Вы уж пожалуйста извините,но давайте я сам буду решать чем
> мне заниматься.Не удержался,сорри за оффтоп.
>

Так никто и не против. Но зачем переворачивать деревья? Они же погибнут сразу!
:)
Сорри за оффтоп.

> MsGuns © (09.10.08 00:24) [56]
> >oxffff ©
>
> Употребив к Вам слово "юноша", я имел в виду не возраст,
> а исключительно опыт и навыки в программировании. И, судя
> по [53] [54], явно переоценил - на юношу не тянете. Хоть
> и нахватались где-то "умных" слов (что такое "атрибутировать"
> - ни разу не слышал, это что-то типа "крышевать" или "фундаментить"
> по отношению к зданию, ага ?)
>
> То, что у Вас нет понятия о деревьях в информатике, ясно
> тут уже всем и давно и никакия грубость не поможет Вам выйти
> сухим из воды.
>
> Все-таки боролись бы Вы лучше, мальчик ;)))

Грубость на грубость.

>То, что у Вас нет понятия о деревьях в информатике

Честно улубнуло. Но к вашему сожалению здесь вы опять ошиблись.

> korneley © (08.10.08 23:07) [55]
>
> > Каким образом можно реализовать "перевёрнутое дерево",
> т.
> > е. дерево наоборот.где ветви сходятся к корню
>
> Только нарисовать самому. А ещё, сетка может с двух сторон,
> к центру быть нарисована :)
>
> 1/8|- -|2/7
> | |
> >-|?/?|->|?/?|<-|?/?|<
> | |
> 4/5|- -|3/6
>
> Вот это уже не дерево, а куст :)) "Совокупность веток, растущих
> из одного места" (с)

Ну это не куст. А лес.

>Ну это не куст. А лес.

Марсианский ?
:)

> MsGuns © (09.10.08 00:45) [58]
> А если серьезно по теме, то турнирную сетку можно, конечно
> изобразить и в виде TTreeView (какая разница, слева напрво
> рисовать этапы или справа налево), но есть много минусов:
>

У вас странное восприятие. А [55] лишь относится к способу отрисовки дерева. А не к самому дереву. Имеется ввиду, что Ttreeview это выравнивание по левому краю, а [55] это выравнивание по центру.

Теперь по делу. Если вы не поняли [53] и [54], то для вас специально на пальцах.

Иванов
----[Победитель не извествен]
Петров
----[Победитель не извествен]
Сидоров
----[Победитель не извествен]
Чупров

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

Иванов
----[Победитель не извествен]
Петров
----[Победитель не извествен]
Сидоров
----[Победитель не извествен]
Чупров
----
Ляо
----[Победитель не извествен]
Цзы
----[Победитель не извествен]
Дзе
----[Победитель не извествен]
Цхи

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

P.S. Честно я даже боюсь с вами поговорить об LR анализе. Если LL вы еще понимаете, то LR для вас будет тяжелее.

> MsGuns © (09.10.08 09:12) [64]
> >Ну это не куст. А лес.
>
> Марсианский ?
> :)

Если смотреть слева направо, то лес. Если сверху вниз, то дерево.

>Честно я даже боюсь с вами поговорить об LR анализе. Если LL вы еще понимаете, то LR для вас >будет тяжелее.

:)))

Сажайте деревья на здоровье, пусть даже марсианские
И пребудет с Вами удача !

"Обратное дерево" Найти похожие ветки