c++ - 增加 BST 的迭代器

Question

我对如何正确地执行此操作感到困惑，但我需要能够在我正在实现的使用模板的二叉搜索树类中递增迭代器。

迭代器的结构有一个当前节点，以及一个定义其当前位置的整数。我遇到的唯一问题是，当它执行 ++Iter 操作时，我应该如何确定它应该向右还是向左？

这是整个类的头文件:

template < typename TComparable, typename TValue > 
    class SearchTree
    {
    public:
        class Iterator;
    private:
        struct Node;
        typedef typename Node TNode;
    public:
        SearchTree( void );
        ~SearchTree( void );
    public:
        TValue find( const TComparable& k );
        TValue find( int32_t index );
        TValue find( const Iterator& pIter );

        Iterator begin( void ) const;
        Iterator end( void ) const;

        void insert( const TComparable& k, const TValue& v );
        void insert( const Iterator& pIter );

        friend class Iterator;
        friend class TNode;
    private:
        int32_t mNodeCount;
        TNode* mRoot;
    public:
        class Iterator 
        {
        public:
            Iterator( void );
            Iterator( int32_t position );
            ~Iterator( void );
            inline TNode* operator->( void ) const 
            { return mCurrentNode; }
            void operator++( void );
            bool operator==( const Iterator& pIter );
            bool operator!=( const Iterator& pIter );
        private:
            int32_t getNumStepsLeftToLeaf( void );
            int32_t getNumStepsRightToLeaf( void );
            bool isLeafNode( const Node*& n );
            bool isInternalNode( const Node*& n );
        private:
            TNode* mCurrentNode;
            int32_t mIterPosition;
            friend class TNode;
        };
    private:
        struct Node
        {
        public:
            Node( void ) : mParent( NULL ), mLeftChild( NULL ), mRightChild( NULL )
            {}
            ~Node( void )
            {
                if ( mParent ) delete mParent;
                if ( mLeftChild ) delete mLeftChild;
                if ( mRightChild ) delete mRightChild;
            }
            int32_t index;
            TComparable Key;
            TValue Value;
            TNode* mParent;
            TNode* mLeftChild;
            TNode* mRightChild;
        };
    };

请注意，我不能为此使用异常，因为我计划将大量此代码移植到 Android NDK，我相信它不能使用 STLport 的异常(这就是我将使用的 - GnuSTL 是 GPL'd，它意味着我正在做的事情(这是为了盈利)我不能使用它 - 如果有人对此有任何反驳，请告诉我)

此外，在有人提到提升之前，我已经尝试将其移植到 NDK 但没有成功。我想使用它，因为这会让生活变得更轻松，但现在我愿意编写自己的数据结构和算法。

至于迭代器，我猜我在这里的设计中遗漏了一些东西，如果有人知道这可能是什么，请告诉我。如果有人需要，我也很乐意为此发布整个类(class)的源代码。

Answer 1

首先，前缀自增运算符有这个签名:

Iterator& operator++();

后缀应该以这种方式根据前缀声明和定义:

const Iterator& operator++(int){Iterator old = *this; ++(*this); return old;}

您可能希望前缀向其节点询问下一个(最左边的)节点，

Iterator& Iterator::operator++(){
    myParent = mCurrentNode; 
    return  myParent.getRightOf(mCurrentNode); 
}

你看到我假设你有办法从一个节点构造一个迭代器你可能至少应该有一个 私有(private)的。

我想你想遍历叶节点，(无论如何内部节点的实现没有什么不同)。 您或多或少需要一个 getRightOf 方法来执行以下操作，让我为它写下一些伪代码:

Node* Node::getRightOf(Node* aNode){ 
    if aNode == mLeftChild{
        if mRightNode
            return mRightNode(this); 
        return mParent(this)
    }
    if aNode == mRightChild{
        return mParent(this)
    }
    if aNode == mParent{
        if mLeftNode
            return mLeftNode(this); 
        if mRightNode
            return mRightNode(this); 
        return this; 
    }
}

您需要注意管理容器末尾迭代等案例。

警告

在 Node 的析构函数中，我读到:

if ( mParent ) delete mParent;

这看起来很危险:谁删除了 ParentNode？左 child 还是右 child ？