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

Question

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

• 拜访左孩
• 访问节点
• 拜访正确的 child

还有这些复杂性限制:遍历整棵树的运行时复杂度应为 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

与其尝试手动实现递归算法(使用堆栈)，不如将其递归编写。更容易理解。而且很简单，访问左，节点，右。(因为这是作业，我不会详细介绍)。