Бінарне дерево (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();
}
}
Результат роботи програми: