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

[garymar]

Почитай про паттерн Компоновщик (Composite). Хотя я до сих пор не въеха в суть, что ты в итоге хочешь. Никакой конкретики.

[ZackMercury]

garymar, ТС хочет увидеть дерево визуально.

[Nooob]

для обхода дерева лучше всего подходит паттерн Visitor

[garymar]

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

для обхода дерева лучше всего подходит паттерн Visitor

Посетитель сюда не совсем подойдет. Это поведенческий паттерн. В Компоновщике (структурный паттерн) никто не запрещает реализовать в каждом элементе дерева (и ветках и листьях) метод использующий технику рекурсивного обхода дерева.

[OlmerDale]

Nooob, а можете привести минимальный пример, а то очень интересно.

garymar, да я понимаю что тут композиция нужна для нод, но сложность не в
создании нод, а в идентичном построении.

Я уже отказался от построения в один проход. Мне кажется что этот график строился
по физическим законам, так как других объяснений я найти не могу. Пример на самом деле
безумно сложный.

[garymar]

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

garymar, да я понимаю что тут композиция нужна для нод, но сложность не в
создании нод, а в идентичном построении.

Если ты тупо хочешь повторить дерево на картинке из твоего первого сообщения (насколько я правильно понял), то тебе нужно изначально представлять дерево в каком-то формате, затем его парсить и выводить как граф. По словами "изначально представлять дерево" я хотел сказать, что тебе нужно задать исходные данные. Ну вот например JSON или XML или HTML, я хз... Если я правильно тебя понял.

Вот пример из JSON дерева на твоей картинке:

{
    "root": {
        "branch_1": {
            "leaf_1": "Hello world"
        },
        "leaf_1": "Hello world",
        "leaf_2": "Hello world",
        "branch_2": {
            "leaf_1": "Hello world",
            "leaf_2": "Hello world",
            "leaf_3": "Hello world",
            "leaf_4": "Hello world",
            "leaf_5": "Hello world"
        },
        "branch_3": {
            "leaf_1": "Hello world",
            "leaf_2": "Hello world",
            "leaf_3": "Hello world",
            "leaf_4": "Hello world",
            "leaf_5": "Hello world",
            "leaf_6": "Hello world"
        },
        "leaf_3": "Hello world"
    }
}

Или вот XML:

<root>
    <branch>
        <leaf/>
    </branch>
    <leaf/>
    <leaf/>
    <branch>
        <leaf/>
        <leaf/>
        <leaf/>
        <leaf/>
        <leaf/>
    </branch>
    <branch>
        <leaf/>
        <leaf/>
        <leaf/>
        <leaf/>
        <leaf/>
        <leaf/>
    </branch>
    <leaf/>
</root>

Вот тебе диаграмма классов http://prntscr.com/6t0gnr

[Wolsh]

Алгоритмы построения поуровневого изображения деревьев

[OlmerDale]

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

[dimarik]

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

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

В ... Компоновщике (структурный паттерн) никто не запрещает реализовать в каждом элементе дерева (и ветках и листьях) метод использующий технику рекурсивного обхода дерева.

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

В программировании рекурсия — вызов функции (процедуры) из неё же самой

Я сам пару лет понемногу занимаюсь деревьями. В контексте их эффективного рендеринга в Stage3D. Многое переосмыслил.

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

Алгоритмы построения поуровневого изображения деревьев

Сходил по ссылке, сразу напрягло

В 1979 году C. Wetherell и A. Shannon представили алгоритм линейной сложности для рисования бинарных деревьев

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

Двои́чное де́рево — иерархическая структура данных, в которой каждый узел имеет не более двух потомков

Глупый источник, негодный.

[Wolsh]

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

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

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

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