Обход дерева по уровням рекурсивно - 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(); } }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д