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

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

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

// Удерживать информацию о ветке.
private class BranchInfo
{
    public float X, Y, Theta, Length;
    public int Depth;
    public BranchInfo(float x, float y, float theta,
        float length, int depth)
    {
        X = x;
        Y = y;
        Theta = theta;
        Length = length;
        Depth = depth;
    }
}

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

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

// Рисуем двоичное дерево.
private void DrawTree(Graphics gr, Pen pen,
    int max_depth, float x, float y, float max_length,
    float initial_theta, float length_scale, float dtheta)
{
    // Добавим соединительную линию в очередь.
    Queue branches = new Queue();
    branches.Enqueue(new BranchInfo(x, y, initial_theta,
        max_length, max_depth));

    // Обработает ветви до тех пор, пока очередь не будет пуста.
    while (branches.Count > 0)
    {
        // Нарисуем следующую ветку.
        BranchInfo branch = branches.Dequeue();

        // Установите цвет пера в зависимости от глубины.
        if (branch.Depth == 1) pen.Color = Color.Red;
        else
        {
            int g = 255 * (max_depth - branch.Depth) / max_depth;
            int r = 139 * (branch.Depth - 3) / max_depth;
            if (r < 0) r = 0;
            int b = 0;
            pen.Color = Color.FromArgb(r, g, b);
        }

        // Установите толщину пера в зависимости от глубины.
        int thickness = 10 * branch.Depth / max_depth;
        if (thickness < 0) thickness = 0;
        pen.Width = thickness;

        // См., Где должна заканчиваться эта ветка.
        float x1 = (float)(branch.X +
            branch.Length * Math.Cos(branch.Theta));
        float y1 = (float)(branch.Y +
            branch.Length * Math.Sin(branch.Theta));

        // Нарисуем ветку.
        gr.DrawLine(pen, branch.X, branch.Y, x1, y1);

        // Если branch.depth & gt; 1, добавьте дочерние ветви в очередь.
        if (branch.Depth > 1)
        {
            branches.Enqueue(new BranchInfo(x1, y1,
                branch.Theta + dtheta,
                branch.Length * length_scale,
                branch.Depth - 1));
            branches.Enqueue(new BranchInfo(x1, y1,
                branch.Theta - dtheta,
                branch.Length * length_scale,
                branch.Depth - 1));
        }
    }
}

Метод начинается с создания 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/

(Пока оценок нет)