Бинарное дерево

Бинарное дерево (binary tree) – это структура данных, которая состоит из узлов, при этом каждый узел может иметь не более двух дочерних. Первый узел называется корневым или родительским, а дочерние – правым и левым наследником(потомком).

Бинарное дерево поиска

Двоичное дерево поиска (binary search tree) – это бинарное дерево, которое соответствует следующим условиям:

• Дочерние узлы являются двоичными деревьями поиска;
• Для произвольного узла:
  • Все значения левого поддерева, меньше значения родительского узла;
  • Все значения правого поддерева, больше значения родительского узла.

Класс для описания узла

Для начала необходимо создать класс для описания узла бинарного дерева. Для того, чтобы иметь возможность хранить произвольный тип данных, используем обобщенный тип T, к которому применима операция сравнения, иными словами, можно будет использовать любой тип данных, реализующий интерфейс IComparable:

/// <summary>
/// Расположения узла относительно родителя
/// </summary>
public enum Side
{
    Left,
    Right
}

/// <summary>
/// Узел бинарного дерева
/// </summary>
/// <typeparam name="T"></typeparam>
public class BinaryTreeNode<T> where T : IComparable
{
    /// <summary>
    /// Конструктор класса
    /// </summary>
    /// <param name="data">Данные</param>
    public BinaryTreeNode(T data)
    {
        Data = data;
    }

    /// <summary>
    /// Данные которые хранятся в узле
    /// </summary>
    public T Data { get; set; }

    /// <summary>
    /// Левая ветка
    /// </summary>
    public BinaryTreeNode<T> LeftNode { get; set; }

    /// <summary>
    /// Правая ветка
    /// </summary>
    public BinaryTreeNode<T> RightNode { get; set; }

    /// <summary>
    /// Родитель
    /// </summary>
    public BinaryTreeNode<T> ParentNode { get; set; }

    /// <summary>
    /// Расположение узла относительно его родителя
    /// </summary>
    public Side? NodeSide =>
        ParentNode == null
        ? (Side?)null
        : ParentNode.LeftNode == this
            ? Side.Left
            : Side.Right;

    /// <summary>
    /// Преобразование экземпляра класса в строку
    /// </summary>
    /// <returns>Данные узла дерева</returns>
    public override string ToString() => Data.ToString();
}

Класс бинарное дерево

Создадим новый класс BinaryTree, который будет описывать бинарное дерево поиска и содержать в себе все необходимые методы для работы с данными. Для начала добавим в него родительский элемент:

/// <summary>
/// Бинарное дерево
/// </summary>
/// <typeparam name="T">Тип данных хранящихся в узлах</typeparam>
public class BinaryTree<T> where T : IComparable
{
    /// <summary>
    /// Корень бинарного дерева
    /// </summary>
    public BinaryTreeNode<T> RootNode { get; set; }
}

Добавление данных

Первый метод, который мы реализуем, будет добавлять новый узел в дерево:

/// <summary>
/// Добавление нового узла в бинарное дерево
/// </summary>
/// <param name="node">Новый узел</param>
/// <param name="currentNode">Текущий узел</param>
/// <returns>Узел</returns>
public BinaryTreeNode<T> Add(BinaryTreeNode<T> node, BinaryTreeNode<T> currentNode = null)
{
    if (RootNode == null)
    {
        node.ParentNode = null;
        return RootNode = node;
    }

    currentNode = currentNode ?? RootNode;
    node.ParentNode = currentNode;
    int result;
    return (result = node.Data.CompareTo(currentNode.Data)) == 0
        ? currentNode
        : result < 0
            ? currentNode.LeftNode == null
                ? (currentNode.LeftNode = node)
                : Add(node, currentNode.LeftNode)
            : currentNode.RightNode == null
                ? (currentNode.RightNode = node)
                : Add(node, currentNode.RightNode);
}

Данный метод сначала проверяет корневой узел и если он пустой, то присваивает ему значение нового узла. В противном случае производит сравнение данных нового узла с значением узла в который вставляется узел, и если:

• Значения совпадают, то значение узла остается прежним;
• Новое значение меньше текущего – вставляем в левую ветку дерева;
• Новое значение больше текущего – вставляем в правую ветку дерева.

Для упрощения непосредственного добавления данных, создадим перегрузку метода:

/// <summary>
/// Добавление данных в бинарное дерево
/// </summary>
/// <param name="data">Данные</param>
/// <returns>Узел</returns>
public BinaryTreeNode<T> Add(T data)
{
    return Add(new BinaryTreeNode<T>(data));
}

Поиск узла дерева по значению

Напишем рекурсивный метод для поиска узла по его значению:

/// <summary>
/// Поиск узла по значению
/// </summary>
/// <param name="data">Искомое значение</param>
/// <param name="startWithNode">Узел начала поиска</param>
/// <returns>Найденный узел</returns>
public BinaryTreeNode<T> FindNode(T data, BinaryTreeNode<T> startWithNode = null)
{
    startWithNode = startWithNode ?? RootNode;
    int result;
    return (result = data.CompareTo(startWithNode.Data)) == 0
        ? startWithNode
        : result < 0
            ? startWithNode.LeftNode == null
                ? null
                : FindNode(data, startWithNode.LeftNode)
            : startWithNode.RightNode == null
                ? null
                : FindNode(data, startWithNode.RightNode);
}

Метод начинает поиск с указанного узла(если не задан, то с корня дерева), сравнивая значения текущего элемента с искомым, если значение найдено, возвращается ссылка на узел, если нет, то производится рекурсивный обход дочерних веток дерева.

Удаление узла бинарного дерева

/// <summary>
/// Удаление узла бинарного дерева
/// </summary>
/// <param name="node">Узел для удаления</param>
public void Remove(BinaryTreeNode<T> node)
{
    if (node == null)
    {
        return;
    }

    var currentNodeSide = node.NodeSide;
    //если у узла нет подузлов, можно его удалить
    if (node.LeftNode == null && node.RightNode == null)
    {
        if (currentNodeSide == Side.Left)
        {
            node.ParentNode.LeftNode = null;
        }
        else
        {
            node.ParentNode.RightNode = null;
        }
    }
    //если нет левого, то правый ставим на место удаляемого 
    else if (node.LeftNode == null)
    {
        if (currentNodeSide == Side.Left)
        {
            node.ParentNode.LeftNode = node.RightNode;
        }
        else
        {
            node.ParentNode.RightNode = node.RightNode;
        }

        node.RightNode.ParentNode = node.ParentNode;
    }
    //если нет правого, то левый ставим на место удаляемого 
    else if (node.RightNode == null)
    {
        if (currentNodeSide == Side.Left)
        {
            node.ParentNode.LeftNode = node.LeftNode;
        }
        else
        {
            node.ParentNode.RightNode = node.LeftNode;
        }

        node.LeftNode.ParentNode = node.ParentNode;
    }
    //если оба дочерних присутствуют, 
    //то правый становится на место удаляемого,
    //а левый вставляется в правый
    else
    {
        switch (currentNodeSide)
        {
            case Side.Left:
                node.ParentNode.LeftNode = node.RightNode;
                node.RightNode.ParentNode = node.ParentNode;
                Add(node.LeftNode, node.RightNode);
                break;
            case Side.Right:
                node.ParentNode.RightNode = node.RightNode;
                node.RightNode.ParentNode = node.ParentNode;
                Add(node.LeftNode, node.RightNode);
                break;
            default:
                var bufLeft = node.LeftNode;
                var bufRightLeft = node.RightNode.LeftNode;
                var bufRightRight = node.RightNode.RightNode;
                node.Data = node.RightNode.Data;
                node.RightNode = bufRightRight;
                node.LeftNode = bufRightLeft;
                Add(bufLeft, node);
                break;
        }
    }
}

Поскольку в метод для удаления, необходимо передавать экземпляр класса, то для удобства сделаем перегрузку для поиска и удаления:

/// <summary>
/// Удаление узла дерева
/// </summary>
/// <param name="data">Данные для удаления</param>
public void Remove(T data)
{
    var foundNode = FindNode(data);
    Remove(foundNode);
}

Вывод бинарного дерева на экран

Напишем рекурсивный метод для вывода дерева в экран консоли:

/// <summary>
/// Вывод бинарного дерева
/// </summary>
public void PrintTree()
{
    PrintTree(RootNode);
}

/// <summary>
/// Вывод бинарного дерева начиная с указанного узла
/// </summary>
/// <param name="startNode">Узел с которого начинается печать</param>
/// <param name="indent">Отступ</param>
/// <param name="side">Сторона</param>
private void PrintTree(BinaryTreeNode<T> startNode, string indent = "", Side? side = null)
{
    if (startNode != null)
    {
        var nodeSide = side == null ? "+" : side == Side.Left ? "L" : "R";
        Console.WriteLine($"{indent} [{nodeSide}]- {startNode.Data}");
        indent += new string(' ', 3);
        //рекурсивный вызов для левой и правой веток
        PrintTree(startNode.LeftNode, indent, Side.Left);
        PrintTree(startNode.RightNode, indent, Side.Right);
    }
}

Программа для работы с бинарным деревом поиска

Напишем программу для работы с двоичным деревом, для простоты будем использовать целочисленный тип данных:

using System;

class Program
{
    static void Main(string[] args)
    {
        var binaryTree = new BinaryTree<int>();
        
        binaryTree.Add(8);
        binaryTree.Add(3);
        binaryTree.Add(10);
        binaryTree.Add(1);
        binaryTree.Add(6);
        binaryTree.Add(4);
        binaryTree.Add(7);
        binaryTree.Add(14);
        binaryTree.Add(16);

        binaryTree.PrintTree();

        Console.WriteLine(new string('-', 40));
        binaryTree.Remove(3);
        binaryTree.PrintTree();

        Console.WriteLine(new string('-', 40));
        binaryTree.Remove(8);
        binaryTree.PrintTree();

        Console.ReadLine();
    }
}

Результат работы программы: