#region "Задание"
//1.Реализуйте тестовую программу, в которой выполняются все основные
//операции с бинарным деревом поиска (обход(следует реализовать все виды
//обхода бинарного дерева в виде рекуррентных процедур, а также один вариант
//обхода с помощью не рекуррентной процедуры согласно варианту задания из
//приложения А, таблицы А.2), поиск, добавление,
//удаление с заданным ключом и удаление всего дерева), а также два
//дополнительных задания из приложения А, таблицы А.3. Бинарное дерево
//следует реализовать в виде указанном в приложении А, в таблице А.1., для
//этого составьте последовательность из целочисленных элементов
//принадлежащих диапазону [10..99]. Тестирование каждой из процедур
//добавления и удаления узла в бинарное дерево поиска следует чередовать
//с выводом бинарного дерева в наглядном виде. Для этого можно
//использовать представленную в приложении Б процедуру printBinTree
//(или разработайте свой собственный аналог).
//2. Воспользуйтесь вариантом задания для бригады из первой лабораторной
//работы и сформулируйте постановку задачи как описано в примере из
//приложения А. Составьте программу с использованием бинарного дерева и
//проиллюстрируйте результаты её работы на тестовом примере.
//При объявлении бинарных деревьев выполните комментирование
//используемых полей. Программу для решения каждого задания необходимо
//разработать методом процедурной абстракции. Разработанные подпрограммы и
//типы структур данных включить в один модуль (unit файл).
#endregion
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace for_Firuz_z2
{
class Program
{
public enum BinSide
{
Left,
Right
}
/// <summary>
/// Бинарное дерево поиска
/// </summary>
public class BinaryTree
{
public long? Data { get; private set; }
public BinaryTree Left { get; set; }
public BinaryTree Right { get; set; }
public BinaryTree Parent { get; set; }
/// <summary>
/// Вставляет целочисленное значение в дерево
/// </summary>
/// <param name="data">Значение, которое добавится в дерево</param>
public void Insert(long data)
{
if (Data == null || Data == data)
{
Data = data;
return;
}
if (Data > data)
{
if (Left == null) Left = new BinaryTree();
Insert(data, Left, this);
}
else
{
if (Right == null) Right = new BinaryTree();
Insert(data, Right, this);
}
}
/// <summary>
/// Вставляет значение в определённый узел дерева
/// </summary>
/// <param name="data">Значение</param>
/// <param name="node">Целевой узел для вставки</param>
/// <param name="parent">Родительский узел</param>
private void Insert(long data, BinaryTree node, BinaryTree parent)
{
if (node.Data == null || node.Data == data)
{
node.Data = data;
node.Parent = parent;
return;
}
if (node.Data > data)
{
if (node.Left == null) node.Left = new BinaryTree();
Insert(data, node.Left, node);
}
else
{
if (node.Right == null) node.Right = new BinaryTree();
Insert(data, node.Right, node);
}
}
/// <summary>
/// Уставляет узел в определённый узел дерева
/// </summary>
/// <param name="data">Вставляемый узел</param>
/// <param name="node">Целевой узел</param>
/// <param name="parent">Родительский узел</param>
private void Insert(BinaryTree data, BinaryTree node, BinaryTree parent)
{
if (node.Data == null || node.Data == data.Data)
{
node.Data = data.Data;
node.Left = data.Left;
node.Right = data.Right;
node.Parent = parent;
return;
}
if (node.Data > data.Data)
{
if (node.Left == null) node.Left = new BinaryTree();
Insert(data, node.Left, node);
}
else
{
if (node.Right == null) node.Right = new BinaryTree();
Insert(data, node.Right, node);
}
}
/// <summary>
/// Определяет, в какой ветви для родительского лежит данный узел
/// </summary>
/// <param name="node"></param>
/// <returns></returns>
private BinSide? MeForParent(BinaryTree node)
{
if (node.Parent == null) return null;
if (node.Parent.Left == node) return BinSide.Left;
if (node.Parent.Right == node) return BinSide.Right;
return null;
}
/// <summary>
/// Удаляет узел из дерева
/// </summary>
/// <param name="node">Удаляемый узел</param>
public void Remove(BinaryTree node)
{
if (node == null) return;
var me = MeForParent(node);
//Если у узла нет дочерних элементов, его можно смело удалять
if (node.Left == null && node.Right == null)
{
if (me == BinSide.Left)
{
node.Parent.Left = null;
}
else
{
node.Parent.Right = null;
}
return;
}
//Если нет левого дочернего, то правый дочерний становится на место удаляемого
if (node.Left == null)
{
if (me == BinSide.Left)
{
node.Parent.Left = node.Right;
}
else
{
node.Parent.Right = node.Right;
}
node.Right.Parent = node.Parent;
return;
}
//Если нет правого дочернего, то левый дочерний становится на место удаляемого
if (node.Right == null)
{
if (me == BinSide.Left)
{
node.Parent.Left = node.Left;
}
else
{
node.Parent.Right = node.Left;
}
node.Left.Parent = node.Parent;
return;
}
//Если присутствуют оба дочерних узла
//то правый ставим на место удаляемого
//а левый вставляем в правый
if (me == BinSide.Left)
{
node.Parent.Left = node.Right;
}
if (me == BinSide.Right)
{
node.Parent.Right = node.Right;
}
if (me == null)
{
var bufLeft = node.Left;
var bufRightLeft = node.Right.Left;
var bufRightRight = node.Right.Right;
node.Data = node.Right.Data;
node.Right = bufRightRight;
node.Left = bufRightLeft;
Insert(bufLeft, node, node);
}
else
{
node.Right.Parent = node.Parent;
Insert(node.Left, node.Right, node.Right);
}
}
/// <summary>
/// Удаляет значение из дерева
/// </summary>
/// <param name="data">Удаляемое значение</param>
public void Remove(long data)
{
var removeNode = Find(data);
if (removeNode != null)
{
Remove(removeNode);
}
}
/// <summary>
/// Ищет узел с заданным значением
/// </summary>
/// <param name="data">Значение для поиска</param>
/// <returns></returns>
public BinaryTree Find(long data)
{
if (Data == data) return this;
if (Data > data)
{
return Find(data, Left);
}
return Find(data, Right);
}
/// <summary>
/// Ищет значение в определённом узле
/// </summary>
/// <param name="data">Значение для поиска</param>
/// <param name="node">Узел для поиска</param>
/// <returns></returns>
public BinaryTree Find(long data, BinaryTree node)
{
if (node == null) return null;
if (node.Data == data) return node;
if (node.Data > data)
{
return Find(data, node.Left);
}
return Find(data, node.Right);
}
/// <summary>
/// Количество элементов в дереве
/// </summary>
/// <returns></returns>
public long CountElements()
{
return CountElements(this);
}
/// <summary>
/// Количество элементов в определённом узле
/// </summary>
/// <param name="node">Узел для подсчета</param>
/// <returns></returns>
private long CountElements(BinaryTree node)
{
long count = 1;
if (node.Right != null)
{
count += CountElements(node.Right);
}
if (node.Left != null)
{
count += CountElements(node.Left);
}
return count;
}
}
public class BinaryTreeExtensions
{
public static void Print(BinaryTree node)
{
if (node != null)
{
if (node.Parent == null)
{
Console.WriteLine("ROOT:{0}", node.Data);
}
else
{
if (node.Parent.Left == node)
{
Console.WriteLine("Left for {1} --> {0}", node.Data, node.Parent.Data);
}
if (node.Parent.Right == node)
{
Console.WriteLine("Right for {1} --> {0}", node.Data, node.Parent.Data);
}
}
if (node.Left != null)
{
Print(node.Left);
}
if (node.Right != null)
{
Print(node.Right);
}
}
}
};
static void Main()
{
var tree = new BinaryTree();
tree.Insert(20);
tree.Insert(40);
tree.Insert(10);
tree.Insert(30);
tree.Insert(80);
tree.Insert(29);
tree.Insert(31);
tree.Insert(32);
tree.Insert(70);
BinaryTreeExtensions.Print(tree);
tree.Remove(40);
BinaryTreeExtensions.Print(tree);
tree.Remove(20);
BinaryTreeExtensions.Print(tree);
Console.ReadKey();
}
}
}