Обход дерева по уровням рекурсивно - 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();
    }
}

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

15   голосов , оценка 3.733 из 5