Требуется помощь в реализации итератора InOrder для дерева - PullRequest
Новая
       27

Требуется помощь в реализации итератора InOrder для дерева

3 голосов
/ 02 мая 2011

Я реализую итератор 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;
}

Я не проверял егоно я думаю, что это должно работать нормально.Мои проблемы начались, когда я пытался реализовать оператор Rede (-).Мой первоначальный подход состоял в том, чтобы иметь второй стек: recedeStack и использовать его так же, как я использовал его для оператора ++.Но я не мог понять, как синхронизировать стек возвратов в операторе ++ и наоборот (advanceStack в операторе -).Во всяком случае, не без превышения ограничения сложности памяти.

Есть идеи, как решить эту проблему (с моей текущей реализацией или без)?

Ответы [ 3 ]

0 голосов
/ 08 октября 2012

У меня был похожий вопрос на собеседовании, и я мог найти решение.Пройти через рекурсию просто.Написать итератор для обхода в ширину просто.Но написать итератор для inorder traverse стал для меня головоломкой.Поэтому после некоторых исследований в Интернете я нашел хорошее решение среди других, которое слишком многословно и относительно сложно.Мой язык - 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
    }
0 голосов
/ 23 июня 2015 
    //......    
       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 голосов
/ 02 мая 2011

Вместо того, чтобы пытаться вручную реализовать рекурсивный алгоритм (используя стек), просто напишите его рекурсивный.намного проще и понятнее.И это так же просто, как посетить слева, узел, справа.(так как это домашнее задание, я не буду вдаваться в подробности).

...