Доброго времени суток.
Нужно реализовать дерево с нодами, которые могут быть и списками нодов. Т.е. Один нод может содержать адрес правого и левого нода, или правых и левых нодов может быть несколько.
Бьюсь уже неделю над сей проблемой. Помоему это тупиковая проблема.
У кого есть мысли - Высказывайте.

а смысл?
такое дерево можно заменить бинрным...

Lazin, Разве? Мне кажется, что не так все просто.
В моей реализации проблема с рекурсией.

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

Почему? Правых становится несколько, левых так же.

andrew_121, 
а как определяется количество правых и левых узлов для данного узла?

А если нод описывает трехмерный куб, заданный координатами, который в свою очередь разбит на восемь равных частей, описываемых "дочерними" нодами. Неужели это нельзя назвать деревом? Неужто это не древовидная структура? Она, разумеется, не бинарная, а (хм.. октарная?) .  И понятия правых и левых нет. Зато есть понятия верхний правый ближний, верхний правый дальний и т.д.   

это N-арное дерево, автору-же нужно бинарное, так как есть правые и левые чаилды, я так понял что он хочет такого:



но это уже не дерево, так как узлы C D F то-же как-то друг с другом соотносятся 
вот это дерево:
         

SaDFromSpb нестоит придираться к словам. слово дерево там было употреблено в терминологии автора первого поста дабы исключить путаницу.

Lazin лично я думаю что автор имел  в виду нечто вроде

Мне нужно представить это:

В виде дерева. Но есть одно "НО". Слово "being" указывает на 4-ри поддерева. А это очень простое предложение.
Из кода сего парсера, я получаю это:

Список связей, каждая содержит тип, и слова.


Это сообщение отредактировал(а) andrew_121 - 26.7.2008, 16:09

andrew_121, объясни, что ты вообще делаешь по-лучше. А то это какой-то страшный набор букв.

SaDFromSpb - Что именно не понятно?

andrew_121, 

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

SaDFromSpb - Гм... Вопрос правильный. Похоже что я просто не знаю как мне представить эту древовидную структуру.
Т.е. Парсер после разбора предложения отображает диаграмму связей, это для наглядности, программе которая работает с результатом парса этого не понять. При помощи API парсера, я получаю список пар:

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

А что такое API парсер?

chipset - Ну что такое API, Вам известно. А perser это программа-библиотека смыслового-синтаксического разбора предложений.

Нифига не понял. Обьясни ещё раз что ты хочешь, четко и понятно и что такое этот perser (с ссылками, если можно).

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

chipset - Что такое parser я обьяснил. Ссылок нет, программа коммерческая, код закрыт. Да и причем тут parser?
Я изложил все что знаю. Если есть вопросы - задавайте конкретно.


Это сообщение отредактировал(а) andrew_121 - 27.7.2008, 23:42

andrew_121 вот chipset и интересутся при чем тут parser, почему ты его называешь "парсер", и че за кучка пар у тебя получилась, что она значит и нахрена это вообще.

есть такая вещь как понимание. вы понимаете что хотите? изложите мат модель, которую вы не можете разрешить и не парьте мозг людям про какие-то закрытые сверсекретные исходники... мы и сами можем таких отсыпать 8)

jonie - Я немогу в этой теме объяснять что такое, так называемый parser. Я эту библиотеку называю parser(ом). Это лингвистическая программа, объяснять суть программы я не стану, это не объяснишь в нескольких строках. Все что мне известно об API этой программы я объяснил. Что еще я могу объяснить??? Задавайте вопросы!

вы математику изучали ? ну там типа "... где s={V,E} : для любого V из V' выполнимо...." ? представляете как описывать строгим языком задачи?

Слово "being" ни на одно поддерево там не указывает, оно лист (или “висячая вершина”, то есть не имеет поддеревьев) — как известно, в информатике деревья растут вниз (корень в самом верху). Вы, наверное, имели ввиду, что оно является дочерним узлом для четырех других узлов, что тоже не совсем верно, потому что я таковых на диаграммке насчитал 5: Xd, Os, MX*p, MVp, Xc. Надеюсь, вы действительно оговорились, а не смотрели на это дерево снизу вверх, потому что в таком ракурсе оно смотрится действительно жутковато. Давайте смотреть как обычно, сверху вниз!   

То, что вы нарисовали, похоже на обыкновенное бинарное дерево с тремя особенностями. 1) Нет корня. Поэтому, строго говоря это не дерево. 2) Глубина 1 — очень плоское дерево.

Уже учтя эти две особенности можно сказать, что никакое дерево вам не нужно. Запомним это и двинемся дальше.

3 и самая интересная особенность: листы (“терминалы”, если говорить в терминах синтаксического анализа) должны принадлежать классу, реализующему паттерн Приспособленец (Flyweight), то есть есть объект представляющий слово “being”, а есть куча объектов в разных узлах дерева ссылающихся на него. Я не знаю, насколько обязательно то, что вы нарисовали, может быть вполне достаточно хранить копии слова “being”, тогда эта особенность отпадает.

Теперь про деревья. Как я сказал выше, это похоже на дерево, но таковым не является. В общем. это не так плохо, потому что деревья в чистом виде в стандартной библиотеке C++ не реализованы, как и стандартных библиотеках некоторых других популярных языков. Я не буду тут вдаваться в подробности, почему дело обстоит таким образом, но это, разумеется, не спроста. 

Наконец вывод. В вашем случае нужно определиться с тем, какое API вы хотите иметь на выходе. То есть на входе результат работы вашего парсера, а на выходе должен быть экземпляр класса с каким-то фиксированным интерфейсом. Забудьте про всякие там деревья и определите этот интерфейс (можете даже тут нам его рассказать). А в качестве реализации (то есть закрытого поля в этом классе, которое (поле) будет содержать имеющуюся информацию) используйте что-нибудь вроде std::list<std::vector<std::string> >, где длина внутреннего вектора всегда равна трем (строковое содержимое узла и двух дочек). Если может быть больше двух дочек — пожалуйста, vector не будет вас в этом стеснять. Если захотите все-таки Приспособленца, то с vector будет трудность, потому что узел и дочки должны принадлежать к разным типам. В этом случае вместо vector можно использовать boost::tuple, ну или, если boost очень страшно, то std::pair< T, std::pair<U, U> >, (чем по сути tuple и является, только со много более удобным интерфейсом) где, скажем, T это тип для узла, а U тип для его дочек, реализующих Приспособленца. Можно обойтись vector, если завязать T и U в одну иерархию наследования. Кроме того, возможно, наследование упростит жизнь, если ваше “дерево” все-таки может иметь глубину больше 1.

Как-то так. А вообще тема бодрая, да, я тут сижу и просто-таки веселюсь...  

Это сообщение отредактировал(а) Ulysses4j - 28.7.2008, 17:04

Ulysses4j - Спасибо за пояснения. Я действительно не мог представить способ реализации сей проблемы, потому и использовал "средние" термины. Запутался, затупил конкретно. Сейчас ситуация проясняется.
Переосмыслю...

Ulysses4j - А вот мне совсем не смешно )))

Это сообщение отредактировал(а) andrew_121 - 28.7.2008, 02:17