[Алгоритмы] Как построить дерево?

[OlmerDale]

Wolsh спасибо за ссылку и сорри за первые комменты.
Расписано вполне доступно, а главное русским языком написано что - за один проход не получится и хватит пытаться Конечно есть небольшие разности, но если что, то можно и третий проход сделать..

[Wolsh]

И тут же на рисунках показывают небинарное дерево.

Но, если прочитать не только первое предложение, а и то, которое собственно предшествует рисунку, то получится

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

Бинарное же дерево рассматривается в соответствующей главе.

[dimarik]

Wolsh, нет, не надо папу путать. Указания на рисунки в контексте бинарных деревьев

Изоморфизм: каждая пара изоморфных поддеревьев рисуется идентично с точностью до переноса. То есть изображение каждого поддерева не зависит от расположения этого поддерева внутри всего дерева. На Рис. 4.1(а) показан пример изображения дерева с нарущением принципа изоморфизма. Поддеревья с корнем 2 и корнем 7 имеют разные изображения, хотя они и изоморфны. На Рис. 4.1(б) оба поддерева имеют идентичное изображение.
Симметричность: Изображение дерева с инвертированным порядком всех сыновей можно получить, зеркально отразив изображение исходного дерева. На Рис. 4.1(с) показано нарушение принципа симметрии, произошедшее из-за несимметричного размещения вершины 6, а на Рис. 4.1(д) изображение дерева симметрично.

идут до этой замечательной фразы, которую ты привёл.

Я знаю, что я зануда. Но автор статьи не удосужился, и я делаю вывод, что статья чуть менее, чем негодная.

[dimarik]

В упор не вижу рекурсии. Я только за нее и говорил. Никаких других конструктивных предложений я не желал предложить.

[OlmerDale]

Прошла неделя а я так и не смог сделать. Это я говорю не к тому чтобы попросить помочь, а к тому,
что очень хочется назвать того кто писал эту статью - анти-ученым.

Рассмотрим теперь вопрос о том, как реализовать за время O(n) шаг 1. В силу требования об идентичности изображения изоморфных поддеревьев , изображение каждого поддерева не должно зависеть от его положения в объемлющем дереве. Значит, для сравнения координат вершин поддеревьев T' и T'' достаточно рассматривать только координаты вершин, принадлежащих «границе» каждого поддерева. То есть, на каждом уровне можно сравнивать только x-координату самой правой вершины левого поддерева с x-координатой самой левой вершины правого поддерева. Для реализации этой идеи, введем понятие правого и левого контура поддерева.

У меня уже отторжение статьи идет и я не понимаю что написано в первом предложении, цитируемого отрывка. Тут автор хочет реализовать O(n)? Шаг? Или Шаг 1, которого нет.. Или все же шаг, а после пишет пункт 1, когда второго пункта не существует..
И так вся статья. Её писал безумный ...

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

[Simplifier]

OMG, OlmerDale.

В алгоритме 2 шага:
1. Обход дерева Т в обратном порядке
2. Обход в прямом порядке

Реализация описывается не с первого шага, а со второго.
Затем, в процитированном вами фрагменте, рассматривается вопрос, как реализовать первый шаг за время O(n)

Статьи довольно краткие, сильно материал не разжевывают, поэтому явно подразумевается, что читатель уже имеет базовые знания по теории алгоритмов. И, например, знает, что такое оценка сложности: https://ru.wikipedia.org/wiki/Вычислительная_сложность
http://cybern.ru/asimtotic-oboz.html
А не начинает нападать на автора, увидев незнакомые обозначения.

[OlmerDale]

А не начинает нападать на автора, увидев незнакомые обозначения.

Это не нападок, а внутренний вопрос - почему если уж делаешь не сделать на пять с плюсом.

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

Добавлено через 1 минуту
Поймал себя на мысли, что свой многоэтажный дом я стал воспринимать как дерево