Используйте очередь для рисования двоичного дерева с шириной первого цвета в C#

Пример Нарисуйте ширину в ширину двоичное дерево в C# показывает, как использовать Stack для рисования двоичного дерева в порядке глубины. Программа создает Stack, представляющий нижний (trunk) уровень дерева. Для каждого уровня он обрабатывает Stack, добавляя дочерние ветви для следующего уровня к новому Stack.

В этом примере показано, как вы можете использовать Queue для реализации немного более простого подхода. В следующем коде показан класс BranchInfo, который программа использует для хранения информации о ветке, которую он будет потом рисовать.

Этот объект удерживает начальное положение, направление, длину и глубину ветки в дереве.

Следующий код показывает, как программа рисует свое дерево.

Метод начинается с создания Queue и добавления к нему нового объекта BranchInfo для представления ствола дерева. Затем он входит в цикл while, который выполняется до тех пор, пока Queue не пуст.

Внутри цикла код вызывает метод Queue Dequeue, чтобы получить следующий элемент из очереди. В Queue элементы добавляются и удаляются в порядке ввода-вывода или FIFO. Это означает, что метод Dequeue возвращает элемент, который был в очереди самым длинным. (Это то, как линия (или очередь, если вы британцы) работает, когда вы ждете автобус.)

Программа рисует ветку, которая была просто удалена из Queue. Тогда, если глубина ветви больше 1, код добавляет дочерние ветви в Queue.

Программа повторяет цикл while до тех пор, пока Queue не будет пустым.

Внутри Queue все ветви заданной глубины группируются вместе. Чтобы понять, почему, считайте, что изначально соединительная линия является единственной ветвью и предположим, что она имеет глубину 10.

Когда программа обрабатывает соединительную линию, она добавляет две ветви глубины 9. Они являются единственными ветвями в Queue, поэтому они группируются вместе.

Затем программа обрабатывает две ветви глубины 9 и добавляет их детей в конец Queue. Поскольку они идут в конце, а существующие ветви находятся впереди Queue, дети с глубиной 8 сгруппированы в конце.

В более общем плане предположим, что программа удалила все ветви глубины D, а Queue содержит только ветви глубины D - 1. Все они находятся в передней части Queue . По мере обработки этих ветвей код добавляет ветви на глубину D - 2 в конец Queue. Все они приходят после глубины D - 1 ветвей, поэтому они тоже сгруппированы.

Источник: http://csharphelper.com/blog/2015/08/use-a-queue-to-draw-a-breadth-first-colored-binary-tree-in-c/

1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (Пока оценок нет)

Add a Comment

Ваш e-mail не будет опубликован. Обязательные поля помечены *