Обход бинарного дерева с помощью итератора

Tags: вопросы на собеседовании, структуры данных, алгоритмы

Исходники для статьи

Недавно мне пришлось проходить собеседование в Microsoft. По моим впечатлениям, я проявил себя довольно неплохо, но взяли другого разработчика, который по каким-то причинам подошёл лучше меня. Интервьюировали меня в несколько этапов. Задания и вопросы, в отличии от большинства вопросов в наших компаниях, были интереснее и разумнее, что-ли. Поэтому мне захотелось опубликовать серию статей с разбором заданий. Сегодня я рассмотрю задание, с частью которого я не справился, но хорошенько подумав на досуге нашёл хорошее решение.

Задание, собственно, было такое. Напишите класс-итератор для обхода бинарного дерева. Первую половину – обход дерева breadth-first traversal – я решил довольно быстро, а вот со второй – inorder depth-first traversal возникли проблемы. Выполнить какое-либо действие (например, распечатать значение поля данных узла) для всех узлов с помощью рекурсии не представляет проблем, а вот с итератором у меня что-то не заладилось.

Теория

Для начал немного теории. Бинарное дерево – древовидная структура данных, в которой каждый узел имеет не более двух потомков (детей). Как правило, первый называется родительским узлом, а дети называются левым и правым наследниками.

Далее по тексту я буду использовать следующее бинарное дерево.

binary-tree-1

Дерево можно обойти различными способами:

  1. Обход в прямом порядке (preorder depth-first traversal) – каждый узел посещается до того, как посещены его дети. Для нашего дерева это будет последовательность: {10, 8, 4, 3, 5, 2, 9, 20, 6, 23, 21}. Для корня дерева рекурсивно вызывается следующая процедура:
    • Посетить узел
    • Обойти левое поддерево
    • Обойти правое поддерево
  2. Симметричный обход (inorder depth-first traversal) – посещается сначала левое поддерево, затем узел, затем правое поддерево: {3, 4, 2, 5, 8, 9, 10, 6, 20, 21, 23}. Для корня дерева рекурсивно вызывается следующая процедура:
    • Обойти левое поддерево
    • Посетить узел
    • Обойти правое поддерево
  3. Обход в обратном порядке (postorder depth-first traversal) – узлы посещаются снизу вверх: {3, 2, 5, 4, 9, 8, 6, 21, 23, 20, 10}. Для корня дерева рекурсивно вызывается следующая процедура:
    • Обойти левое поддерево
    • Обойти правое поддерево
    • Посетить узел
  4. Обход в ширину (breadth-first traversal) – узлы посещаются уровень за уровнем сверху вниз, каждый уровень слева направо: {10, 8, 20, 4, 9, 6, 23, 3, 5, 21, 2}.

Базовые классы

Ничего специального. Просто минимальный класс узла бинарного дерева.

    /// <summary>
    /// A binary tree node.
    /// </summary>
    public class BinaryTreeNode
    {
        #region Constructors

        public BinaryTreeNode(int aValue, BinaryTreeNode aLeft, BinaryTreeNode aRight)
        {
            Value = aValue;
            Left = aLeft;
            Right = aRight;
        }

        #endregion

        #region Public properties

        public int Value { get; set; }
        public BinaryTreeNode Left { get; set; }
        public BinaryTreeNode Right { get; set; }

        #endregion

        #region Public methods

        public override string ToString()
        {
            string lResult = string.Format("Node: {0}", Value);
            return lResult;
        }

        #endregion
    }

Базовый итератор:

    /// <summary>
    /// Abstract binary tree iterator.
    /// </summary>
    public abstract class BinaryTreeIterator
    {
        #region Public properties

        /// <summary>
        /// Gets the current iterator's node.
        /// </summary>
        public BinaryTreeNode Current { get; protected set; }

        #endregion

        #region Public methods

        /// <summary>
        /// Advances the iterator to the next node if possible.
        /// </summary>
        /// <returns>
        /// Returns <see langword="true"/> if iterator has advanced to the next node, otherwise - 
        /// <see langword="false"/>.
        /// </returns>
        public abstract bool Next();

        /// <summary>
        /// Checks if it's possible to advance the iterator to the next node.
        /// </summary>
        /// <returns>
        /// Returns <see langword="true"/> if iterator could be advanced to the next node, otherwise
        /// - <see langword="false"/>.
        /// </returns>
        public bool HasNext()
        {
            return Current != null;
        }

        #endregion
    }

Далее исходники классов-итераторов для каждого случая.

Обход в прямом порядке (preorder depth-first traversal)

    /// <summary>
    /// Binary tree preorder depth-first iterator.
    /// </summary>
    public class BinaryTreePreorderIterator : BinaryTreeIterator
    {
        #region Constructors

        /// <summary>
        /// Initializes a new instance of binary tree preorder depth-first iterator with the root
        /// node of the traversing tree.
        /// </summary>
        /// <param name="aRoot">
        /// Root node of the traversing tree.
        /// </param>
        public BinaryTreePreorderIterator(BinaryTreeNode aRoot)
        {
            // The tree root is the initial iterator's current node.
            Current = aRoot;

            if (Current == null)
            {
                // The tree is empty.
                return;
            }

            // Push the terminator.
            NodeStack.Push(null);
        }

        #endregion

        #region Public methods

        /// <summary>
        /// Advances the iterator to the next node if possible.
        /// </summary>
        /// <returns>
        /// Returns <see langword="true"/> if iterator has advanced to the next node, otherwise - 
        /// <see langword="false"/>.
        /// </returns>
        public override bool Next()
        {
            if (Current == null)
            {
                // Iterating finished already.
                return false;
            }

            if (Current.Right != null)
            {
                // Right subtree in place.
                // Push the right node. If the left node is missed, it would be processed next.
                // Otherwise it will be processed after left subtree.
                NodeStack.Push(Current.Right);
            }

            if (Current.Left != null)
            {
                // The left node in place.
                // It would be the next current.
                Current = Current.Left;
            }
            else
            {
                // Go one level up if there hadn't been right subtree,
                // otherwise the right subtree would be processed.
                Current = NodeStack.Pop();
            }

            return HasNext();
        }

        #endregion

        #region Private properties

        private Stack<BinaryTreeNode> NodeStack
        {
            get { return mNodeStack; }
        }

        #endregion

        #region Private data

        private readonly Stack<BinaryTreeNode> mNodeStack = new Stack<BinaryTreeNode>();

        #endregion
    }

Симметричный обход (inorder depth-first traversal)

    /// <summary>
    /// Binary tree inorder depth-first iterator.
    /// </summary>
    public class BinaryTreeInorderIterator : BinaryTreeIterator
    {
        #region Constructors

        /// <summary>
        /// Initializes a new instance of binary tree inorder depth-first iterator with the root
        /// node of the traversing tree.
        /// </summary>
        /// <param name="aRoot">
        /// Root node of the traversing tree.
        /// </param>
        public BinaryTreeInorderIterator(BinaryTreeNode aRoot)
        {
            Current = aRoot;

            if (Current == null)
            {
                // The tree is empty.
                return;
            }

            // Push the terminator.
            NodeStack.Push(null);

            // To initialize inorder iterator go deep to the leftmost node of the left subtree 
            // of the root node along the way pushing nodes traversed so far.
            while (Current.Left != null)
            {
                NodeStack.Push(Current);
                Current = Current.Left;
            }
        }

        #endregion

        #region Public methods

        /// <summary>
        /// Advances the iterator to the next node if possible.
        /// </summary>
        /// <returns>
        /// Returns <see langword="true"/> if iterator has advanced to the next node, otherwise - 
        /// <see langword="false"/>.
        /// </returns>
        public override bool Next()
        {
            if (Current == null)
            {
                // Iterating finished already.
                return false;
            }

            if (Current.Right != null)
            {
                // There is right subtree.
                // Go deep to the leftmost node of the left subtree 
                // of the current node along the way pushing nodes traversed so far.
                Current = Current.Right;
                while (Current.Left != null)
                {
                    NodeStack.Push(Current);
                    Current = Current.Left;
                }
            }
            else
            {
                // There is no right subtree.
                // Go a level up.
                Current = NodeStack.Pop();
            }

            return HasNext();
        }

        #endregion

        #region Private properties

        private Stack<BinaryTreeNode> NodeStack
        {
            get { return mNodeStack; }
        }

        #endregion

        #region Private data

        private readonly Stack<BinaryTreeNode> mNodeStack = new Stack<BinaryTreeNode>();

        #endregion
    }

Обход в обратном порядке (postorder depth-first traversal)

    /// <summary>
    /// Binary tree postorder depth-first iterator.
    /// </summary>
    public class BinaryTreePostorderIterator : BinaryTreeIterator
    {
        #region Constructors

        /// <summary>
        /// Initializes a new instance of binary tree postorder depth-first iterator with the root
        /// node of the traversing tree.
        /// </summary>
        /// <param name="aRoot">
        /// Root node of the traversing tree.
        /// </param>
        public BinaryTreePostorderIterator(BinaryTreeNode aRoot)
        {
            Current = aRoot;

            if (Current == null)
            {
                // The tree is empty.
                return;
            }

            // Push the terminator.
            NodeStack.Push(null);

            // Iterator initialization. Go to the deepest node on the left subtree of the root.
            // If there is no the left subtree, go to the deepest node on the right subtree of the root.
            while (Current.Left != null || Current.Right != null)
            {
                NodeStack.Push(Current);
                if (Current.Left != null)
                {
                    Current = Current.Left;
                }
                else
                {
                    Current = Current.Right;
                }
            }
        }

        #endregion

        #region Public methods

        /// <summary>
        /// Advances the iterator to the next node if possible.
        /// </summary>
        /// <returns>
        /// Returns <see langword="true"/> if iterator has advanced to the next node, otherwise - 
        /// <see langword="false"/>.
        /// </returns>
        public override bool Next()
        {
            if (Current == null)
            {
                // Iterating finished already.
                return false;
            }

            BinaryTreeNode lParent = NodeStack.Peek();
            if (lParent != null && // the current node isn't the tree root node
                Current == lParent.Left && // it is the left subtree of the next node on stack
                lParent.Right != null) // the next node on the stack has right subtree
            {
                // It is necessary to process the right subtree of the next node on stack.
                Current = lParent.Right;
                // Go to the deepest node on the left subtree of right subtree of the next node on stack.
                // If there is no the left subtree, go to the deepest node on the right subtree of the root.
                while (Current.Left != null || Current.Right != null)
                {
                    NodeStack.Push(Current);
                    if (Current.Left != null)
                    {
                        Current = Current.Left;
                    }
                    else
                    {
                        Current = Current.Right;
                    }
                }
            }
            else
            {
                // Go one level up.
                Current = NodeStack.Pop();
            }

            return HasNext();
        }

        #endregion

        #region Private properties

        private Stack<BinaryTreeNode> NodeStack
        {
            get { return mNodeStack; }
        }

        #endregion

        #region Private data

        private readonly Stack<BinaryTreeNode> mNodeStack = new Stack<BinaryTreeNode>();

        #endregion
    }

Обход в ширину (breadth-first traversal)

    /// <summary>
    /// Binary tree breadth-first iterator.
    /// </summary>
    public class BinaryTreeBreadthFirstIterator : BinaryTreeIterator
    {
        #region Constructors

        /// <summary>
        /// Initializes a new instance of binary tree breadth-first with the root node of the
        /// traversing tree.
        /// </summary>
        /// <param name="aRoot">
        /// Root node of the traversing tree.
        /// </param>
        public BinaryTreeBreadthFirstIterator(BinaryTreeNode aRoot)
        {
            Current = aRoot;

            if (Current == null)
            {
                // The tree is empty.
                return;
            }

            // Enqueue left and right nodes of the current node.
            if (Current.Left != null)
            {
                NodeQueue.Enqueue(Current.Left);
            }
            if (Current.Right != null)
            {
                NodeQueue.Enqueue(Current.Right);
            }
        }

        #endregion

        #region Public methods

        /// <summary>
        /// Advances the iterator to the next node if possible.
        /// </summary>
        /// <returns>
        /// Returns <see langword="true"/> if iterator has advanced to the next node, otherwise - 
        /// <see langword="false"/>.
        /// </returns>
        public override bool Next()
        {
            if (Current == null)
            {
                // Iterating finished already.
                return false;
            }

            if (NodeQueue.Count > 0)
            {
                // There are nodes on the queue.
                Current = NodeQueue.Dequeue();

                // Enqueue left and right nodes of the current node.
                if (Current.Left != null)
                {
                    NodeQueue.Enqueue(Current.Left);
                }
                if (Current.Right != null)
                {
                    NodeQueue.Enqueue(Current.Right);
                }
            }
            else
            {
                // There are no nodes on the queue anymore.
                Current = null;
            }

            return HasNext();
        }

        #endregion

        #region Private properties

        private Queue<BinaryTreeNode> NodeQueue
        {
            get { return mNodeQueue; }
        }

        #endregion

        #region Private data

        private readonly Queue<BinaryTreeNode> mNodeQueue = new Queue<BinaryTreeNode>();

        #endregion
    }

Модульные тесты

    [TestClass]
    public class BinaryTreeIteratorsTests
    {
        #region Public methods

        [TestMethod]
        public void InorderIteratorTest()
        {
            BinaryTreeNode lResultNodes = GetTestTree();

            BinaryTreeInorderIterator lIterator = new BinaryTreeInorderIterator(lResultNodes);
            int[] lExpectedSequence = new[] {3, 4, 2, 5, 8, 9, 10, 6, 20, 21, 23};
            int lIndex = 0;
            while (lIterator.HasNext())
            {
                Trace.WriteLine(lIterator.Current.Value);
                Assert.AreEqual(lExpectedSequence[lIndex], lIterator.Current.Value);
                lIterator.Next();
                lIndex++;
            }

            Assert.AreEqual(11, lIndex, "Wrong number of elements!!!");
            Assert.IsNull(lIterator.Current);
        }

        [TestMethod]
        public void PreorderIteratorTest()
        {
            BinaryTreeNode lResultNodes = GetTestTree();

            BinaryTreePreorderIterator lIterator = new BinaryTreePreorderIterator(lResultNodes);
            int[] lExpectedSequence = new[] {10, 8, 4, 3, 5, 2, 9, 20, 6, 23, 21};
            int lIndex = 0;
            while (lIterator.HasNext())
            {
                Trace.WriteLine(lIterator.Current.Value);
                Assert.AreEqual(lExpectedSequence[lIndex], lIterator.Current.Value);
                lIterator.Next();
                lIndex++;
            }

            Assert.AreEqual(11, lIndex, "Wrong number of elements!!!");
            Assert.IsNull(lIterator.Current);
        }

        [TestMethod]
        public void PostorderIteratorTest()
        {
            BinaryTreeNode lResultNodes = GetTestTree();

            BinaryTreePostorderIterator lIterator = new BinaryTreePostorderIterator(lResultNodes);
            int[] lExpectedSequence = new[] {3, 2, 5, 4, 9, 8, 6, 21, 23, 20, 10};
            int lIndex = 0;
            while (lIterator.HasNext())
            {
                Trace.WriteLine(lIterator.Current.Value);
                Assert.AreEqual(lExpectedSequence[lIndex], lIterator.Current.Value);
                lIterator.Next();
                lIndex++;
            }

            Assert.AreEqual(11, lIndex, "Wrong number of elements!!!");
            Assert.IsNull(lIterator.Current);
        }

        [TestMethod]
        public void BreadthFirstIteratorTest()
        {
            BinaryTreeNode lResultNodes = GetTestTree();

            BinaryTreeBreadthFirstIterator lIterator =
                new BinaryTreeBreadthFirstIterator(lResultNodes);
            int[] lExpectedSequence = new[] {10, 8, 20, 4, 9, 6, 23, 3, 5, 21, 2};
            int lIndex = 0;
            while (lIterator.HasNext())
            {
                Trace.WriteLine(lIterator.Current.Value);
                Assert.AreEqual(lExpectedSequence[lIndex], lIterator.Current.Value);
                lIterator.Next();
                lIndex++;
            }

            Assert.AreEqual(11, lIndex, "Wrong number of elements!!!");
            Assert.IsNull(lIterator.Current);
        }

        #endregion

        #region Private methods

        private BinaryTreeNode GetTestTree()
        {
            return new BinaryTreeNode(
                10,
                new BinaryTreeNode(
                    8,
                    new BinaryTreeNode(
                        4,
                        new BinaryTreeNode(
                            3,
                            null,
                            null),
                        new BinaryTreeNode(
                            5,
                            new BinaryTreeNode(
                                2,
                                null,
                                null),
                            null)),
                    new BinaryTreeNode(
                        9,
                        null,
                        null)),
                new BinaryTreeNode(
                    20,
                    new BinaryTreeNode(
                        6,
                        null,
                        null),
                    new BinaryTreeNode(
                        23,
                        new BinaryTreeNode(
                            21,
                            null,
                            null),
                        null)));
        }

        #endregion
    }