Geek asks and answers

Help needed to implement an InOrder iterator for a tree

I am running an InOrder iterator for homework, which means the iterator is progressing like this:

  • Visiting the left child
  • Visit Node
  • Visiting the right child

There are also the following complexity limitations: Moving throughout the tree should be difficult in terms of execution time o (n), where n is the number of nodes in the tree and memory complexity is o (h), where h is the height of the tree.

I tried using this method to implement the advance (++) operator:

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 , ++. , ++ (frontStack in the - operator). , .

, ( )?

+3
3

, ( ), . . , , node, . ( ).

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;
            }


        };
//...
0

. . . inorder traverse . , . - #, , . 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
    }
-1

More articles:


All Articles