sd_5
.pdf11
{
this.Data = data; this.Parent = parent;
}
public bool AddItem(T val)
{
if (val.CompareTo(this.Data) < 0)
{
if (this.Left == null)
{
this.Left = new Node<T>(val, this);
}
else if (this.Left != null)
{
this.Left.AddItem(val);
}
}
else
{
if (this.Right == null)
{
this.Right = new Node<T>(val, this);
}
else if (this.Right != null)
{
this.Right.AddItem(val);
}
}
return true;
}
public int CompareTo(object obj)
{
if (obj is Node<T> item)
{
return Data.CompareTo(item);
}
else
{
throw new ArgumentException("Несовпадение типов");
}
}
public int CompareTo(T other)
{
return Data.CompareTo(other);
}
public override string ToString()
{
12
return Data.ToString();
}
}
class Tree<T>
where T : IComparable, IComparable<T>
{
public Node<T> Root { get; set; }
public bool AddItem(T data)
{
if (Root == null)
{
Root = new Node<T>(data); return true;
}
Root.AddItem(data); return true;
}
public IEnumerable<Node<T>> LevelOrderTraversal()
{
if (Root == null)
{
yield break;
}
var ochered = new Queue<Node<T>>(); ochered.Enqueue(Root);
while (ochered.Count > 0)
{
var node = ochered.Dequeue(); yield return node;
if (node.Left != null)
{
ochered.Enqueue(node.Left);
}
if (node.Right != null)
{
ochered.Enqueue(node.Right);
}
}
}
public void Print()
{
if (Root == null)
{
Console.WriteLine("Дерево пустое");
}
foreach (var item in LevelOrderTraversal())
13
{
Console.Write(item + ", ");
}
Console.WriteLine();
}
public void Clear()
{
Root = null;
}
private Node<T> Searching(Node<T> node, T val)
{
if (node == null) return null;
switch (val.CompareTo(node.Data))
{
case 1:return Searching(node.Right, val); case -1:return Searching(node.Left, val); case 0:return node;
default:return null;
}
}
List<T> enter = new List<T>(); public int[] MaxMin()
{
var Max = this.Root; var Min = this.Root;
while (Max.Right != null)
{
Max = Max.Right;
}
while (Min.Left != null)
{
Min = Min.Left;
}
int[] f = { Convert.ToInt32(Max.Data), Convert.ToInt32(Min.Data) }; return f;
}
public Node<T> Poisk(T val)
{
return Searching(this.Root, val);
}
public bool RemoveItem(T value)
{
Node<T> node = Poisk(value); if (node == null)
{
return false;
}
14
Node<T> cTree;
if (node == this.Root)
{
if (node.Right != null)
{
cTree = node.Right;
}
else
{
cTree = node.Left;
}
while (cTree.Left != null)
{
cTree = cTree.Left;
}
T temp = cTree.Data; this.RemoveItem(temp); node.Data = temp; return true;
}
if (node.Left == null && node.Right == null && this.Root != null)
{
if (node == node.Parent.Left)
{
node.Parent.Left = null;
}
else
{
node.Parent.Right = null;
}
return true;
}
if (node.Left != null && node.Right == null)
{
node.Left.Parent = node.Parent; if (node == node.Parent.Left)
{
node.Parent.Left = node.Left;
}
else if (node == node.Parent.Right)
{
node.Parent.Right = node.Left;
}
return true;
}
if (node.Left == null && node.Right != null)
{
15
node.Right.Parent = node.Parent; if (node == node.Parent.Left)
{
node.Parent.Left = node.Right;
}
else if (node == node.Parent.Right)
{
node.Parent.Right = node.Right;
}
return true;
}
if (node.Right != null && node.Right != null)
{
cTree = node.Right; while (cTree.Left != null)
{
cTree = cTree.Left;
}
if (cTree.Parent == node)
{
cTree.Left = node.Left; node.Left.Parent = cTree; cTree.Parent = node.Parent; if (node == node.Parent.Left)
{
node.Parent.Left = cTree;
}
else if (node == node.Parent.Right)
{
node.Parent.Right = cTree;
}
return true;
}
else
{
if (cTree.Right != null)
{
cTree.Right.Parent = cTree.Parent;
}
cTree.Parent.Left = cTree.Right; cTree.Right = node.Right; cTree.Left = node.Left; node.Left.Parent = cTree; node.Right.Parent = cTree; cTree.Parent = node.Parent;
if (node == node.Parent.Left)
{
16
node.Parent.Left = cTree;
}
else if (node == node.Parent.Right)
{
node.Parent.Right = cTree;
}
return true;
}
}
return false;
}
}
}