Обход дерева по уровням рекурсивно - C#
Формулировка задачи:
Задача следующая. Необходимо реализовать обход бинарного дерева по уровням, используя рекурсию (без использования очередей).
Решение задачи: «Обход дерева по уровням рекурсивно»
textual
Листинг программы
class BinaryTree<T> : IEnumerable<T>
{
class Node
{
public Node Left { get; set; }
public Node Right { get; set; }
public T Value { get; set; }
public Node(T value)
{
this.Value = value;
}
}
private IComparer<T> comparer;
private Node root;
public int Count { get; private set; }
public BinaryTree()
: this(Comparer<T>.Default)
{
}
public BinaryTree(IComparer<T> comparer)
{
if (comparer == null)
throw new ArgumentNullException("comparer");
this.comparer = comparer;
}
public void Add(T value)
{
var node = new Node(value);
if (root == null)
root = node;
else
{
Node current = root, parent = null;
while (current != null)
{
parent = current;
if (comparer.Compare(value, current.Value) < 0)
current = current.Left;
else
current = current.Right;
}
if (comparer.Compare(value, parent.Value) < 0)
parent.Left = node;
else
parent.Right = node;
}
Count++;
}
private int GetHeight(Node root)
{
if (root == null)
return 0;
return Math.Max(GetHeight(root.Left), GetHeight(root.Right)) + 1;
}
private IEnumerable<T> TraverseLevel(Node root, int level)
{
if (root == null)
yield break;
if (level == 0)
yield return root.Value;
else
{
foreach (var value in TraverseLevel(root.Left, level - 1)) yield return value;
foreach (var value in TraverseLevel(root.Right, level - 1)) yield return value;
}
}
public IEnumerator<T> GetEnumerator()
{
int height = GetHeight(root);
for (int i = 0; i < height; i++)
{
foreach (var value in TraverseLevel(root, i))
yield return value;
}
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
}