Бинарные деревья в C#: код и разбор операций

Обновлено: 31.10.2026 · 6 мин чтения

Что такое бинарное дерево

Дерево состоит из узлов. Верхний узел называется корнем, у каждого узла есть значение и не более двух ссылок: на левого и правого потомка. Узел без потомков называют листом. Расстояние от корня до самого глубокого листа задаёт высоту дерева, и именно от неё зависит скорость почти всех операций.

Чаще всего на практике встречается бинарное дерево поиска (BST). В нём для каждого узла все значения в левом поддереве меньше его значения, а в правом - больше. Это свойство позволяет находить элемент, шаг за шагом отбрасывая половину оставшихся вариантов, как в двоичном поиске по массиву. Обычное бинарное дерево без этого условия применяется реже: например, для разбора выражений или хранения иерархий.

Класс узла и каркас дерева

Для начала достаточно узла с ключом и двумя ссылками. Сделаем его обобщённым, чтобы хранить числа, строки и любые типы, умеющие сравнивать себя. Для этого накладываем ограничение IComparable<T>.

public class Node<T> where T : IComparable<T>
{
    public T Value { get; set; }
    public Node<T>? Left { get; set; }
    public Node<T>? Right { get; set; }

    public Node(T value) => Value = value;
}

public class BinarySearchTree<T> where T : IComparable<T>
{
    private Node<T>? _root;

    public int Count { get; private set; }
}

Все дальнейшие методы добавляются в класс BinarySearchTree<T>. Корень хранится в приватном поле, снаружи он не нужен: пользователь работает только с методами вставки, поиска и обхода.

Вставка элемента

Чтобы добавить значение, начинаем с корня и идём вниз: если новое значение меньше текущего, поворачиваем влево, если больше - вправо. Дойдя до пустого места, создаём там новый узел. Дубликаты в этой реализации не добавляются, и метод возвращает false.

public bool Add(T value)
{
    if (_root == null)
    {
        _root = new Node<T>(value);
        Count++;
        return true;
    }

    var current = _root;
    while (true)
    {
        int cmp = value.CompareTo(current.Value);
        if (cmp == 0) return false;

        if (cmp < 0)
        {
            if (current.Left == null) { current.Left = new Node<T>(value); break; }
            current = current.Left;
        }
        else
        {
            if (current.Right == null) { current.Right = new Node<T>(value); break; }
            current = current.Right;
        }
    }

    Count++;
    return true;
}

Цикл вместо рекурсии выбран сознательно: на вырожденном дереве из тысяч элементов рекурсивная вставка может исчерпать стек, а цикл расходует константную память.

Поиск

Поиск устроен так же, как вставка, только без создания узла. Если дошли до null, значения в дереве нет.

public bool Contains(T value)
{
    var current = _root;
    while (current != null)
    {
        int cmp = value.CompareTo(current.Value);
        if (cmp == 0) return true;
        current = cmp < 0 ? current.Left : current.Right;
    }
    return false;
}

public T? Min()
{
    if (_root == null) return default;
    var n = _root;
    while (n.Left != null) n = n.Left;
    return n.Value;
}

public T? Max()
{
    if (_root == null) return default;
    var n = _root;
    while (n.Right != null) n = n.Right;
    return n.Value;
}

Минимум всегда находится в самой левой ветке, максимум - в самой правой. Эти методы пригодятся при удалении.

Обходы дерева

Обход - это порядок посещения узлов. Для глубинного обхода есть три классических варианта, различающихся моментом, когда обрабатывается сам узел. Четвёртый - обход в ширину, по уровням.

Рекурсивные версии короче всего записываются через итераторы yield return, поэтому обход можно использовать в foreach и LINQ.

public IEnumerable<T> InOrder() => InOrder(_root);
public IEnumerable<T> PreOrder() => PreOrder(_root);
public IEnumerable<T> PostOrder() => PostOrder(_root);

private static IEnumerable<T> InOrder(Node<T>? n)
{
    if (n == null) yield break;
    foreach (var v in InOrder(n.Left)) yield return v;
    yield return n.Value;
    foreach (var v in InOrder(n.Right)) yield return v;
}

private static IEnumerable<T> PreOrder(Node<T>? n)
{
    if (n == null) yield break;
    yield return n.Value;
    foreach (var v in PreOrder(n.Left)) yield return v;
    foreach (var v in PreOrder(n.Right)) yield return v;
}

private static IEnumerable<T> PostOrder(Node<T>? n)
{
    if (n == null) yield break;
    foreach (var v in PostOrder(n.Left)) yield return v;
    foreach (var v in PostOrder(n.Right)) yield return v;
    yield return n.Value;
}

Вложенные итераторы удобны, но на каждый уровень добавляют слой вызовов, так что для очень глубоких деревьев лучше явный стек. Вот обход in-order без рекурсии и обход в ширину через очередь.

public IEnumerable<T> InOrderIterative()
{
    var stack = new Stack<Node<T>>();
    var current = _root;

    while (current != null || stack.Count > 0)
    {
        while (current != null)
        {
            stack.Push(current);
            current = current.Left;
        }
        current = stack.Pop();
        yield return current.Value;
        current = current.Right;
    }
}

public IEnumerable<T> LevelOrder()
{
    if (_root == null) yield break;
    var queue = new Queue<Node<T>>();
    queue.Enqueue(_root);

    while (queue.Count > 0)
    {
        var n = queue.Dequeue();
        yield return n.Value;
        if (n.Left != null) queue.Enqueue(n.Left);
        if (n.Right != null) queue.Enqueue(n.Right);
    }
}

Удаление узла

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

1. У узла нет потомков: его просто убирают, заменяя ссылку родителя на null.
2. Есть один потомок: узел заменяется этим потомком.
3. Есть два потомка: находим наименьший узел в правом поддереве (преемник), копируем его значение в удаляемый узел, а затем удаляем преемника из правого поддерева.

public bool Remove(T value)
{
    bool removed = false;
    _root = Remove(_root, value, ref removed);
    if (removed) Count--;
    return removed;
}

private static Node<T>? Remove(Node<T>? node, T value, ref bool removed)
{
    if (node == null) return null;

    int cmp = value.CompareTo(node.Value);
    if (cmp < 0) node.Left = Remove(node.Left, value, ref removed);
    else if (cmp > 0) node.Right = Remove(node.Right, value, ref removed);
    else
    {
        removed = true;
        if (node.Left == null) return node.Right;
        if (node.Right == null) return node.Left;

        var successor = node.Right;
        while (successor.Left != null) successor = successor.Left;

        node.Value = successor.Value;
        bool dummy = false;
        node.Right = Remove(node.Right, successor.Value, ref dummy);
    }
    return node;
}

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

Высота, количество листьев и проверка

Простые метрики вычисляются рекурсивно. Высота пустого дерева считается равной нулю, высота дерева из одного узла - единице.

public int Height() => Height(_root);

private static int Height(Node<T>? n) =>
    n == null ? 0 : 1 + Math.Max(Height(n.Left), Height(n.Right));

public int LeafCount() => LeafCount(_root);

private static int LeafCount(Node<T>? n)
{
    if (n == null) return 0;
    if (n.Left == null && n.Right == null) return 1;
    return LeafCount(n.Left) + LeafCount(n.Right);
}

Проверка работы

Соберём всё вместе в консольной программе. Значения in-order должны выйти по возрастанию, независимо от порядка добавления.

var tree = new BinarySearchTree<int>();
foreach (int x in new[] { 50, 30, 70, 20, 40, 60, 80 })
    tree.Add(x);

Console.WriteLine(string.Join(" ", tree.InOrder()));    // 20 30 40 50 60 70 80
Console.WriteLine(string.Join(" ", tree.PreOrder()));   // 50 30 20 40 70 60 80
Console.WriteLine(string.Join(" ", tree.LevelOrder())); // 50 30 70 20 40 60 80
Console.WriteLine(tree.Contains(60));                   // True
Console.WriteLine(tree.Height());                       // 3

tree.Remove(50);
Console.WriteLine(string.Join(" ", tree.InOrder()));    // 20 30 40 60 70 80

Кстати, обход in-order фактически сортирует данные. На этом основан алгоритм, описанный в статье про сортировку с помощью бинарного дерева поиска.

Сложность операций и проблема вырождения

Скорость поиска, вставки и удаления пропорциональна высоте дерева. У сбалансированного дерева она составляет порядка log n, но у обычного BST всё зависит от порядка добавления. Если вставлять уже отсортированные числа 1, 2, 3, 4, 5, дерево выродится в цепочку, где каждый узел имеет только правого потомка, и операции станут линейными.

Для защиты применяют самобалансирующиеся деревья: AVL, красно-чёрные, B-деревья. После вставки или удаления они выполняют повороты, удерживая высоту логарифмической. Если данные приходят в случайном порядке, обычный BST справляется хорошо, а если порядок предсказуемо возрастающий, перемешайте вход или используйте готовую структуру.

Готовые деревья в .NET

Писать своё дерево стоит для учёбы, собеседований и специфических задач вроде деревьев выражений. В продакшене обычно хватает стандартной библиотеки. Класс SortedSet<T> и словарь SortedDictionary<TKey, TValue> построены на красно-чёрном дереве, поэтому гарантируют логарифмическое время операций и перечисление в отсортированном порядке.

var set = new SortedSet<int> { 50, 30, 70, 20 };
set.Add(40);
Console.WriteLine(string.Join(" ", set));   // 20 30 40 50 70
Console.WriteLine(set.Min + " " + set.Max); // 20 70
var range = set.GetViewBetween(25, 55);     // 30 40 50

Метод GetViewBetween возвращает диапазон значений без копирования, что удобно для запросов вида "все ключи от A до B". Сравнение со списками и словарями поможет сделать выбор: если нужен быстрый поиск по ключу без порядка, берите Dictionary, а если упорядоченность важна, берите SortedSet.

Когда пригодится бинарное дерево

• Упорядоченный набор с частыми вставками и удалениями, когда сортировать массив заново слишком дорого.
• Деревья выражений: листья хранят числа, внутренние узлы - операции, а вычисление выполняется обходом post-order.
• Деревья решений и игровые деревья, где у каждого шага два исхода.
• Кучи и приоритетные очереди, которые строятся на полном бинарном дереве.
• Индексы и словари в памяти, когда нужен порядок ключей.

Если вы работаете с иерархическими данными вроде файловой системы, где потомков может быть больше двух, нужно обычное дерево со списком потомков. Один из примеров разбора такой иерархии - чтение XML-файлов в C#, где документ представлен деревом элементов.

Частые вопросы