H Обходы бинарного дерева в ширину и в глубину (CLR, RCL, LCR) в черновиках Из песочницы

Всем привет! Сегодня мы вспомним азы программирования на C# и повторим, что такое бинарные деревья, чем они отличаются от остальных деревьев, что же такое обход и какой он бывает.



Для начала повторим азы. Дерево – связный граф без циклов. Корень – самая верхняя вершина дерева. Лист – вершина, не имеющая потомков. Обход дерева – систематический просмотр всех вершин, при котором каждая вершина встречается один раз.

В рассматриваемых алгоритмах используется бинарное дерево – то есть дерево, в котором каждая вершина имеет два потомка (правые и левые поддеревья – left и right). Добавление реализуется по следующей схеме: при добавлении каждой новой вершины, если значение меньше корня, то оно записывается в левое поддерево, в противном случае – в правое (древесная сортировка).

Реализуем же все перечисленные алгоритмы на языке C#!

Тех, кто хочет немного обновить в памяти данный материал, либо еще только учится программировать базовые алгоритмы, без которых не обойдется ни один программист, прошу под кат!) Все фрагменты кода подробно прокомментированы, а демонстрационный проект на языке C# (VS2012) опубликован на GitHub.

Опишем класс Tree на языке C#:

    public class Tree
    {
        // подкласс "элемент дерева"
        public class TreeNode
        {
            public int Value; // численное значение
            public int Count = 0; // сколько раз было добавлено данное численное значение
            public TreeNode Left; // левое поддерево
            public TreeNode Right; // правое поддерево
        }
        public TreeNode Node; // экземпляр класса "элемент дерева"
    }

И реализуем методы:

        // добавление значения в дерево (рекурсивно)
 private void AddRecursion(ref TreeNode node, int val)
        // печать дерева (рекурсивно) 
 private void PrintRecursion(TreeNode node, int spaces, ref string s)
        // обход дерева в ширину (итерационно, используется очередь)
 private void Across(TreeNode node, ref string s, bool detailed)
        // прямой обход (CLR - center, left, right)
 private void CLR(TreeNode node, ref string s, bool detailed)
        // обратный обход (LCR - left, center, right) 
 private void LCR(TreeNode node, ref string s, bool detailed)
        // концевой обход (RCL - left, right, center)
 private void RCL(TreeNode node, ref string s, bool detailed)

Обход в глубину

Сперава разберемся с его видами:

• Прямой обход (CLR – center, left, right). Сначала берется значение корня, затем обходится левое поддерево, затем правое.
• Концевой обход (RCL – right, center, left). Сначала обходится правое поддерево, затем берется значение корня, затем левое.
• Обратный обход (LCR – left, center, right). Сначала обходится левое поддерево, затем берется значение корня, затем правое поддерево.

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

Программная реализация всех трех перечисленных алгоритмов схожа, используется рекурсивный вызов методов. Сложность алгоритма O(N*log2(N)), где N – число вершин.

Прямой обход:

// прямой обход (CLR - center, left, right)
private void CLR(TreeNode node, ref string s, bool detailed)
{
    /*
     Аргументы метода:
     1. TreeNode node - текущий "элемент дерева" (ref  передача по ссылке)       
     2. ref string s - строка, в которой накапливается результат (ref - передача по ссылке)
    */
    if (node != null)
    {
        if (detailed)
            s += "    получили значение " + node.Value.ToString() + Environment.NewLine;
        else
            s += node.Value.ToString() + " "; // запомнить текущее значение
        if (detailed) s += "    обходим левое поддерево" + Environment.NewLine;
            CLR(node.Left, ref s, detailed); // обойти левое поддерево
        if (detailed) s += "    обходим правое поддерево" + Environment.NewLine;
            CLR(node.Right, ref s, detailed); // обойти правое поддерево
    }
    else if (detailed) s += "    значение отсутствует - null" + Environment.NewLine;
}

Обратный обход:

// обратный обход (LCR - left, center, right) 
private void LCR(TreeNode node, ref string s, bool detailed)
{
    /*
     Аргументы метода:
     1. TreeNode node - текущий "элемент дерева" (ref - передача по ссылке)       
     2. ref string s - строка, в которой накапливается результат (ref - передача по ссылке)
    */
    if (node != null)
    {
        if (detailed) s += "    обходим левое поддерево" + Environment.NewLine;
        LCR(node.Left, ref s, detailed); // обойти левое поддерево
        if (detailed)
            s += "    получили значение " + node.Value.ToString() + Environment.NewLine;
        else
            s += node.Value.ToString() + " "; // запомнить текущее значение
        if (detailed) s += "    обходим правое поддерево" + Environment.NewLine;
        LCR(node.Right, ref s, detailed); // обойти правое поддерево
    }
    else if (detailed) s += "    значение отсутствует - null" + Environment.NewLine;
}

Концевой обход:

// концевой обход (RCL -right, center, left)
private void RCL(TreeNode node, ref string s, bool detailed)
{
    /*
     Аргументы метода:
     1. TreeNode node - текущий "элемент дерева" (ref  передача по ссылке)       
     2. ref string s - строка, в которой накапливается результат (ref - передача по ссылке)
    */
    if (node != null)
    {
        if (detailed) s += "    обходим правое поддерево" + Environment.NewLine;
        RCL(node.Right, ref s, detailed); // обойти правое поддерево
        if (detailed)
            s += "    получили значение " + node.Value.ToString() + Environment.NewLine;
        else
            s += node.Value.ToString() + " "; // запомнить текущее значение
        if (detailed) s += "    обходим левое поддерево" + Environment.NewLine;
        RCL(node.Left, ref s, detailed); // обойти левое поддерево
    }
    else if (detailed) s += "    значение отсутствует - null" + Environment.NewLine;
}

 

Обход в ширину

Поддеревья посещаются уровень за уровнем, каждый уровень обходится слева направо. Сложность алгоритма O(V+E), где V – множество вершин, а E-множество дуг.

// обход дерева в ширину (итерационно, используется очередь)
private void Across(TreeNode node, ref string s, bool detailed)
{
    /*
     Аргументы метода:
     1. TreeNode node - текущий "элемент дерева" (ref  передача по ссылке)       
     2. ref string s - строка, в которой накапливается результат (ref - передача по ссылке)
    */
    var queue = new Queue<TreeNode>(); // создать новую очередь
    if (detailed) s += "    заносим в очередь значение " + node.Value.ToString() + Environment.NewLine; queue.Enqueue(node); // поместить в очередь первый уровень
    while (queue.Count!=0) // пока очередь не пуста
    {    
        //если у текущей ветви есть листья, их тоже добавить в очередь
        if (queue.Peek().Left != null)
        {
            if (detailed) s += "    заносим в очередь значение " + queue.Peek().Left.Value.ToString() + " из левого поддерева" + Environment.NewLine;
            queue.Enqueue(queue.Peek().Left);
        }
        if (queue.Peek().Right != null)
        {
            if (detailed) s += "    заносим в очередь значение " + queue.Peek().Right.Value.ToString() + " из правого поддерева" + Environment.NewLine;
            queue.Enqueue(queue.Peek().Right);
        }
        //извлечь из очереди информационное поле последнего элемента
        if (detailed) s += "    извлекаем значение из очереди: " + queue.Peek().Value.ToString() + Environment.NewLine;
        else s += queue.Peek().Value.ToString() + " "; // убрать последний элемент очереди
        queue.Dequeue();
    }
} 

С использованием данных методов я по-быстрому написал такую вот небольшую программку:

А теперь самое интересное — примеры!

Пример 1

Пример: дерево с большим числом поддеревьев, «правых» и «левых».
В глубину CLR: 5 4 3 1 9 8 6 7 15 10
В глубину LCR: 1 3 4 5 6 7 8 9 10 15
В глубину RCL: 15 10 9 8 7 6 5 4 3 1
В ширину: 5 4 9 3 8 15 1 6 10 7

Пример2

Пример: только отрицательные значения в дереве.
В глубину CLR: -2 -4 -15 -5 -1
В глубину LCR: -15 -5 -4 -2 -1
В глубину RCL: -1 -2 -4 -5 -15
В ширину: -2 -4 -1 -15 -5

Пример 3

Пример: отрицательные и положительные значения в дереве
В глубину CLR: 5 4 3 -30 0 1 2 15 8 30
В глубину LCR: -30 0 1 2 3 4 5 8 15 30
В глубину RCL: 30 15 8 5 4 3 2 1 0 -30
В ширину: 5 4 15 3 8 30 -30 0 1 2

Пример 4

Пример: только правые поддеревья
В глубину CLR: 4 5 6 7 8
В глубину LCR: 4 5 6 7 8
В глубину RCL: 8 7 6 5 4
В ширину: 4 5 6 7 8

Пример 5

Пример: только левые поддеревья
В глубину CLR: 10 9 8 7 6
В глубину LCR: 6 7 8 9 10
В глубину RCL: 10 9 8 7 6
В ширину: 10 9 8 7 6

Пример 6

Пример: наиболее емкая наглядность обходов
В глубину CLR: 10 9 11
В глубину LCR: 9 10 11
В глубину RCL: 11 10 9
В ширину: 10 9 11

Исходники проекта

Полные исходники программы для работы с бинарными деревьями выкладываю на GitHub. Можете свободно пользоваться ими для своих проектов или для более локальных задач, к примеру, выполнения лабораторных работ в университете. Присутствуют возможности загрузки исходных данных из текстового файла, сохранения результатов в файл, а также распечатки подробных действий реализации алгоритма (то есть логирование).

Спасибо за внимание! Если будут вопросы или дополнения — рад выслушать.

class Node:
    def __init__(self, key, left=None, right=None):
        self.key = key
        self.left = left
        self.right = right

class Tree:
    def __init__(self):
        self.root = None

    def print_tree(self):
        stack = []
        p = self.root
        while True:
            if p == None:
                if not stack:
                    return
                p = stack.pop()
                print p.key # Обратный обход
                p = p.right
                continue
            
            #print p.key # Прямой обход
            stack.append(p)
            p = p.left

    # Другие методы
    # ...