using System.Collections; namespace tasks; /// /// Interface for an array-based binary tree. /// public interface IArrayBinaryTree : IEnumerable { /// /// Gets the number of nodes in the tree. /// int Count { get; } /// /// Gets the index of the root. /// int RootIndex { get; } /// /// Sets the value of the root node. /// void SetRoot(T value); /// /// Returns the indices of the left and right children for a given parent. /// (int leftIndex, int rightIndex) GetChildrenIndices(int parentIndex); /// /// Sets the value of the left child of a given parent. /// void SetLeftChild(int parentIndex, T value); /// /// Sets the value of the right child of a given parent. /// void SetRightChild(int parentIndex, T value); /// /// Gets the node at the specified index. /// T this[int index] { get; } /// /// Checks if a node at the specified index exists. /// bool Exists(int index); /// /// Clears all nodes from the tree. /// void Clear(); } /// /// An implementation of a binary tree based on an array. /// Indices are calculated as: /// - Left Child: 2 * i + 1 /// - Right Child: 2 * i + 2 /// - Parent: (i - 1) / 2 /// public class ArrayBinaryTree : IArrayBinaryTree { private T[] _nodes; private bool[] _present; public int Count { get; private set; } public int RootIndex => 0; public ArrayBinaryTree(int initialCapacity = 8) { if (initialCapacity < 1) initialCapacity = 8; _nodes = new T[initialCapacity]; _present = new bool[initialCapacity]; Count = 0; } private void EnsureCapacityForIndex(int index) { if (index < _nodes.Length) return; var newSize = _nodes.Length == 0 ? 1 : _nodes.Length; while (newSize <= index) newSize *= 2; Array.Resize(ref _nodes, newSize); Array.Resize(ref _present, newSize); } private void SetAt(int index, T value) { ArgumentOutOfRangeException.ThrowIfNegative(index, nameof(index)); if (index != RootIndex) { var parent = (index - 1) / 2; if (!Exists(parent)) throw new ArgumentOutOfRangeException(nameof(index)); } EnsureCapacityForIndex(index); if (!_present[index]) { _present[index] = true; Count++; } _nodes[index] = value; } public void SetRoot(T value) { SetAt(RootIndex, value); } public (int leftIndex, int rightIndex) GetChildrenIndices(int parentIndex) { ArgumentOutOfRangeException.ThrowIfNegative(parentIndex, nameof(parentIndex)); return (2 * parentIndex + 1, 2 * parentIndex + 2); } public void SetLeftChild(int parentIndex, T value) { if (!Exists(parentIndex)) throw new ArgumentOutOfRangeException(nameof(parentIndex)); var left = GetChildrenIndices(parentIndex).leftIndex; SetAt(left, value); } public void SetRightChild(int parentIndex, T value) { if (!Exists(parentIndex)) throw new ArgumentOutOfRangeException(nameof(parentIndex)); var right = GetChildrenIndices(parentIndex).rightIndex; SetAt(right, value); } public T this[int index] { get { if (!Exists(index)) throw new ArgumentOutOfRangeException(nameof(index)); return _nodes[index]; } } public bool Exists(int index) { return index >= RootIndex && index < _present.Length && _present[index]; } public void Clear() { Array.Clear(_nodes, 0, _nodes.Length); Array.Clear(_present, 0, _present.Length); Count = 0; } public IEnumerator GetEnumerator() { return InOrder(RootIndex).GetEnumerator(); } private IEnumerable InOrder(int index) { if (!Exists(index)) yield break; var (left, right) = GetChildrenIndices(index); foreach (var v in InOrder(left)) yield return v; yield return _nodes[index]; foreach (var v in InOrder(right)) yield return v; } IEnumerator IEnumerable.GetEnumerator() => GetEnumerator(); }