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

私はそれをテストする必要はありませんが、うまくいくはずだと思います。私の問題は、後退 (--) 演算子を実装しようとしたときに始まりました。私の最初のアプローチは、2 番目のスタックである recedeStack を用意し、++ 演算子に使用したのと同じ方法で使用することでした。しかし、後退スタックを ++ 演算子で同期させ、その逆 (- 演算子での AdvanceStack) を維持する方法がわかりませんでした。とにかく、メモリの複雑さの制限を超えていないわけではありません。

この問題を解決する方法についてのアイデアはありますか (現在の実装の有無にかかわらず)?

4

3 に答える 3

0

(スタックを使用して) 再帰アルゴリズムを手動で実装しようとする代わりに、再帰的に記述します。はるかに簡単でわかりやすい。そして、左、ノード、右にアクセスするのと同じくらい簡単です。（宿題なので詳しくは書きません。）

于 2011-05-02T18:46:33.770 に答える
-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 に答える