树的 InOrder 迭代器实现需要帮助

Question

我正在为家庭作业实现一个 InOrder 迭代器，这意味着迭代器将这样前进：

• 访问左子节点
• 访问节点
• 访问右子节点

还有这些复杂性限制： 遍历整棵树的运行时复杂度应为 o(n)，其中 n 是树中的节点数，内存复杂度为 o(h)，其中 h 是树的高度。

我尝试过使用这种方法来实现 advance(++) 运算符：

Tree<DataT>::_InOrderIterator::operator++()
{
    TreeNode* node = this->Node->GetRightChild();
    while(node != NULL)
    {
        advanceStack.Push(node);
        node = node->GetLeftChild();
    }
    node = advanceStack.Pop();
    if (node == NULL)
    {
        node = end; //reserved end node
    }
    this->Node = node;
    return *this;
}

我还没有测试它，但我认为它应该可以正常工作。当我尝试实现后退 (--) 运算符时，我的问题就开始了。我最初的方法是使用第二个堆栈：recedeStack 并以与 ++ 运算符相同的方式使用它。 但我不知道如何在 ++ 运算符中保持后退堆栈同步，反之亦然（-- 运算符中的 advanceStack）。无论如何，这都会超出内存复杂性的限制。

关于如何解决这个问题的任何想法（使用我当前的实现或不使用）？

Answer 1

不必尝试手动实现递归算法（使用堆栈），只需将其递归编写即可。更加容易和容易理解。而且很简单，就是访问左、节点、右。
（因为这是家庭作业，我不会讲更多细节）。

Answer 2

    //......    
       class Iterator{
              friend class BST<T>;
              stack<Node<T>*> stack;
              bool goLeft;
              Iterator(Node<T> *root):goLeft(true)
              {
                  stack.push(NULL);
                  stack.push(root);
              }
        public:

          const T &next()
            {
                Node<T> *curr = stack.top();
                if(curr == NULL) throw exception("The tree is empty");
                if(goLeft){
                    while(curr->left){
                        stack.push(curr->left);
                        curr = curr->left;
                    }
                    goLeft =false;
                }
                stack.pop();
                if(curr->right)
                {
                    stack.push(curr->right);
                    goLeft = true;
                }
                return curr->value;
            }


        };
//...

Answer 3

我在面试时遇到了类似的问题，并且可以找到解决方案。使用递归进行遍历很简单。编写一个广度优先遍历的迭代器很简单。但是为中序遍历编写一个迭代器对我来说是一个脑筋急转弯。因此，经过对网络的一些研究后，我发现了一个很好的解决方案，但过于冗长且相对复杂。我的语言是 C#，但我希望将其翻译成任何其他语言并不困难。 BinaryTreeNode类具有Data、Left、Right属性，此处省略。

    public class BinaryTreeInorderIterator
    {
        #region Constructors

        public BinaryTreeInorderIterator(BinaryTreeNode aRoot)
        {
            Current = aRoot;

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

            // Push the terminator.
            mNodeStack.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)
            {
                mNodeStack.Push(Current);
                Current = Current.Left;
            }
        }

        #endregion

        #region Public properties

        public BinaryTreeNode Current { get; private set; }

        #endregion

        #region Public methods

        public 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)
                {
                    mNodeStack.Push(Current);
                    Current = Current.Left;
                }
            }
            else
            {
                // There is no right subtree.
                // Go a level up.
                Current = mNodeStack.Pop();
            }

            return HasNext();
        }

        public bool HasNext()
        {
            return Current != null;
        }

        #endregion

        #region Private data

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

        #endregion
    }