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

[dimarik]

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

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

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

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

[garymar]

Сообщение от dimarik

Вот, скажем, garymar не знает, что такое рекурсия и демонстрирует свои слабые знания в открытую:

Это твоя невнимательность, вот и все) Ты же не до конца всё просмотрел, наверняка так и было. Или я хз... Из твоих сообщений абсолютно всё - критика, и одно предложение - хвастовство... (Воспитан в TimeZero?) Ничего конструктивного не написал, так лишь бы считалось...))

Да собственно как и все сообщения на форуме как я погляжу.

[gloomyBrain]

Сообщение от dimarik

На дереве рекурсия немного не подпадает под определение

Я хотел написать гневный комментарий, но мне стало лень =) Ерунда это, короче. И в особенности ерунда применительно к рисованию деревьев по данным. Использование рекурсии подходит как нельзя лучше для этой задачи.
Имеем данные, представленные деревом. Все дерево можно построить из, например, вот таких объектов:

public class Node
{
    // массив детей, которые могут иметь своих детей и т.д.
    // может быть пустым
    public var children:Vector.<Node>;
 
    // данные, которые мы хотим хранить в узле дерева
    // может быть null
    public var info:String;
 
    public function Node(info:String = null)
    {
        this.children = new Vector.<Node>();
        this.info = info;
    }
}

В коде можем теперь делать вот такие штуки:

var parent:Node = new Node("I'm a parent!");
var child:Node = new Node("I'm a child!");
 
parent.children.push(child);

Замечательно, теперь наша структура может стать похожей на то что было у автора поста.

Теперь попробуем рисовать что-то по этим данным. Для начала сделаем класс для отображения одного узла:

public class NodeView extends Sprite
{
    private var _data:Node;
    private var _textView:TextField;
 
    public function NodeView(data:Node)
    {
        super();
 
        _data = data;
 
        this.draw();
    }
 
    // тут мы рисуем что-то, что отображает наши данные
    // так как в наши данные входит текст, то рисуем текстовое поле
    // а раз уж у нас есть еще и дети - сразу создаем отображения детей
    // "по образу и подобию" =)
    private function draw():void
    {
        _textView = new TextField();
        _textView.text = _data.info;
 
        for each (var childData:Node in _data.children)
        {
            var childView:NodeView = new NodeView(childData);
 
            // выравниваем детишек друг относительно друга
            childView.x = ...;
            childView.y = ...;
 
            // и добавляем в список отображения
            super.addChild(childView);
        }
    }
}

На выходе будем иметь экземпляр NodeView, у которого есть ширина и высота. При чем ширина и высота NodeView определяются их размеров текстового поля с информацией и размерами и положением его детей. А размеры детей определяются размерами их детей. И так далее вниз по каждой ветке дерева.

[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 минуту
Поймал себя на мысли, что свой многоэтажный дом я стал воспринимать как дерево