using System; using System.Collections; using System.Collections.Generic; namespace laba { public class BinaryTree : ICollection { //Сам узел protected class Node { public TValue Value { get; set; } public Node Left { get; set; } public Node Right { get; set; } public Node(TValue value) { Value = value; } } protected Node root; protected IComparer comparer; public BinaryTree() : this(Comparer.Default) { } public BinaryTree(IComparer defaultComparer) { if (defaultComparer == null) throw new ArgumentNullException("Default comparer is null"); comparer = defaultComparer; } public BinaryTree(IEnumerable collection) : this(collection, Comparer.Default) { } public BinaryTree(IEnumerable collection, IComparer defaultComparer) : this(defaultComparer) { AddRange(collection); } protected static string ShowTree(Node root) { if (root == null) { throw new Exception("ПУСТО В ОГОРОДЕ НЕ ГУСТО"); } if (root.Left == null && root.Right == null) { return root.Value.ToString(); } if (root.Left != null && root.Right == null) { return root.Value + "(" + ShowTree(root.Left) + ",_)"; } if (root.Left == null && root.Right != null) { return root.Value + "(_," + ShowTree(root.Right) + ")"; } return root.Value + "(" + ShowTree(root.Left) + ", " + ShowTree(root.Right) + ")"; } public static string ST(BinaryTree s){ return ShowTree(s.root); } public T MaxValue { get { if (root == null) throw new InvalidOperationException("Деревое пустое!"); var current = root; while (current.Right != null) current = current.Right; return current.Value; } } public T MinValue { get { if (root==null) { throw new InvalidOperationException("Деревое пустое!"); } var current = root; while (current.Left!=null) { current = current.Left; } return current.Value; } } public static bool Part(BinaryTree n) { if (n.MinValue.Equals(n.MaxValue)) { return true; } else { return false; } } public void AddRange(IEnumerable collection) { foreach (var value in collection) Add(value); } public IEnumerable Inorder() { if (root == null) yield break; var stack = new Stack>(); var node = root; while (stack.Count > 0 || node != null) { if (node == null) { node = stack.Pop(); yield return node.Value; node = node.Right; } else { stack.Push(node); node = node.Left; } } } public IEnumerable Preorder() { if (root == null) yield break; var stack = new Stack>(); stack.Push(root); while (stack.Count > 0) { var node = stack.Pop(); yield return node.Value; if (node.Right != null) stack.Push(node.Right); if (node.Left != null) stack.Push(node.Left); } } public IEnumerable Postorder() { if (root == null) yield break; var stack = new Stack>(); var node = root; while (stack.Count > 0 || node != null) { if (node == null) { node = stack.Pop(); if (stack.Count > 0 && node.Right == stack.Peek()) { stack.Pop(); stack.Push(node); node = node.Right; } else { yield return node.Value; node = null; } } else { if (node.Right != null) stack.Push(node.Right); stack.Push(node); node = node.Left; } } } public IEnumerable Levelorder() { if (root == null) yield break; var queue = new Queue>(); queue.Enqueue(root); while (queue.Count > 0) { var node = queue.Dequeue(); yield return node.Value; if (node.Left != null) queue.Enqueue(node.Left); if (node.Right != null) queue.Enqueue(node.Right); } } #region ICollection Members public int Count { get; protected set; } //добавление public virtual void Add(T item) { var node = new Node(item); if (root == null) root = node; else { Node current = root, parent = null; while (current != null) { parent = current; if (comparer.Compare(item, current.Value) < 0) current = current.Left; else current = current.Right; } if (comparer.Compare(item, parent.Value) < 0) parent.Left = node; else parent.Right = node; } ++Count; } //удаление елемента public virtual bool Remove(T item) { if (root == null) return false; Node current = root, parent = null; int result; do { result = comparer.Compare(item, current.Value); if (result < 0) { parent = current; current = current.Left; } else if (result > 0) { parent = current; current = current.Right; } if (current == null) return false; } while (result != 0); if (current.Right == null) { if (current == root) root = current.Left; else { result = comparer.Compare(current.Value, parent.Value); if (result < 0) parent.Left = current.Left; else parent.Right = current.Left; } } else if (current.Right.Left == null) { current.Right.Left = current.Left; if (current == root) root = current.Right; else { result = comparer.Compare(current.Value, parent.Value); if (result < 0) parent.Left = current.Right; else parent.Right = current.Right; } } else { Node min = current.Right.Left, prev = current.Right; while (min.Left != null) { prev = min; min = min.Left; } prev.Left = min.Right; min.Left = current.Left; min.Right = current.Right; if (current == root) root = min; else { result = comparer.Compare(current.Value, parent.Value); if (result < 0) parent.Left = min; else parent.Right = min; } } --Count; return true; } //Удаление дерева public void Clear() { root = null; Count = 0; } public void CopyTo(T[] array, int arrayIndex) { foreach (var value in this) array[arrayIndex++] = value; } public virtual bool IsReadOnly { get { return false; } } public bool Contains(T item) { var current = root; while (current != null) { var result = comparer.Compare(item, current.Value); if (result == 0) return true; if (result < 0) current = current.Left; else current = current.Right; } return false; } #endregion #region IEnumerable Members public IEnumerator GetEnumerator() { return Inorder().GetEnumerator(); } #endregion #region IEnumerable Members IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); } #endregion } class Program { static void Main(string[] args) { BinaryTree integerTree = new BinaryTree(); Random rand = new Random(); for (int i = 0; i < 20; i++) { int value = rand.Next(1000); Console.WriteLine("Adding {0}", value); integerTree.Add(value); } Console.WriteLine("Amount of nodes {0}", integerTree.Count); Console.WriteLine("Max vaue {0}", integerTree.MaxValue); Console.WriteLine("Min value {0}", integerTree.MinValue); Console.WriteLine("Equals? :){0}", BinaryTree.Part(integerTree)); Console.WriteLine("Show my tree"); Console.WriteLine(BinaryTree.ST(integerTree)); Console.WriteLine("Preorder обход:"); Console.WriteLine(string.Join(" ", integerTree.Preorder())); Console.WriteLine("Inorder обход:"); Console.WriteLine(string.Join(" ", integerTree.Inorder())); Console.WriteLine("Postorder обход:"); Console.WriteLine(string.Join(" ", integerTree.Postorder())); Console.WriteLine("Levelorder обход:"); Console.WriteLine(string.Join(" ", integerTree.Levelorder())); Console.WriteLine("inorder обход:"); foreach (int n in integerTree) { Console.Write("{0} ", n); } Console.WriteLine(); Console.WriteLine("After deleting"); integerTree.Clear(); Console.WriteLine("Amount of nodes {0}", integerTree.Count); } } }

My First Binary Tree