Тема: Бінарне дерево
Потрібна допомога з бінарним деревом. Я код для реалізації дерева знайшов в інтернеті і дописав ще свою функцію valCount яка має шукати к-сть входжень певного елемента в дереві. Але я зіткнувся з тим що в дерево не можна записати значення-дублікати(тобто дерево без повторів). Я пробував розібратися з функцією вставки Add елемента в дерево але все марно. Допоможіть будь-ласка переробити дерево щоб в нього можна було записувати однакові елементи.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Laba_7
{
class Proga1
{
// Розташування вузла відносно предка
public enum Side
{
Left,
Right
}
// Вузол бінарного дерева
public class BinaryTreeNode<T> where T : IComparable
{
public BinaryTreeNode(T data)
{
Data = data;
}
public T Data { get; set; }
public BinaryTreeNode<T> LeftNode { get; set; }
public BinaryTreeNode<T> RightNode { get; set; }
public BinaryTreeNode<T> ParentNode { get; set; }
// Розташування вузла відносно його предка
public Side? NodeSide =>
ParentNode == null
? (Side?)null
: ParentNode.LeftNode == this
? Side.Left
: Side.Right;
// Перетворення екземпляра класу в рядок
public override string ToString() => Data.ToString();
public int ToInt()
{
return int.Parse(ToString());
}
}
public class BinaryTree<T> where T : IComparable
{
/// Корінь бінарного дерева
public BinaryTreeNode<T> RootNode { get; set; }
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);
}
public BinaryTreeNode<T> Add(T data)
{
return Add(new BinaryTreeNode<T>(data));
}
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);
}
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;
}
}
}
public void Remove(T data)
{
var foundNode = FindNode(data);
Remove(foundNode);
}
public void PrintTree()
{
PrintTree(RootNode);
}
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);
}
}
public int valCount(int val)
{
if (RootNode != null)
{
return valCount(val, RootNode, 0);
}
return 0;
}
private int valCount(int val, BinaryTreeNode<T> startNode, int count)
{
if (startNode != null)
{
if (startNode.ToInt() == val)
{
count++;
}
count = valCount(val, startNode.LeftNode, count);
count = valCount(val, startNode.RightNode, count);
}
return count;
}
}
static void Main(string[] args)
{
var binaryTree = new BinaryTree<int>();
Random rng = new Random();
for(int i = 0; i < 10; i++)
{
binaryTree.Add(rng.Next(20));
}
binaryTree.PrintTree();
//Console.WriteLine(new string('-', 40));
//binaryTree.Remove(3);
//binaryTree.PrintTree();
//Console.WriteLine(new string('-', 40));
//binaryTree.Remove(8);
//binaryTree.PrintTree();
for (int i = 0; i < 20; i++)
{
int result = binaryTree.valCount(i);
Console.WriteLine("Value = " + i + " Result = " + result);
}
Console.ReadLine();
}
}
}