3

我正在为家庭作业实现一个 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）。无论如何，并非没有超越内存复杂性限制。

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

4

3 回答 3

0

与其尝试手动实现递归算法（使用堆栈），不如将其编写为递归的。更容易理解。就像访问左，节点，右一样简单。（由于是作业，我不会详细说明）。

于 2011-05-02T18:46:33.770 回答
0 
    //......    
       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;
            }


        };
//...
于 2015-06-23T18:34:36.437 回答
-1

我在面试中遇到了类似的问题，并且可以找到解决方案。使用递归进行遍历很简单。为广度优先遍历编写迭代器很简单。但是为中序遍历编写一个迭代器对我来说是一个脑筋急转弯。因此，在对网络进行一些研究之后，我发现了一个很好的解决方案，其中包括过于冗长且相对复杂的解决方案。我的语言是 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
    }
于 2012-10-08T17:11:15.617 回答