1

我对如何正确地做到这一点感到有些困惑，但我需要能够在我正在实现的使用模板的二叉搜索树类中增加一个迭代器。

迭代器的结构有一个当前节点，以及一个定义其当前位置的整数。我遇到的唯一问题是，当它进行++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 的，这意味着什么我正在做（这是为了盈利）我不能使用它 - 如果有人对此有任何反驳，请告诉我）

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

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

4

1 回答 1

1

首先，前缀增量运算符具有以下签名：

Iterator& operator++();

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

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

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

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

你看我假设你有一种方法可以从一个你可能至少应该有一个私有节点的节点构造一个迭代器。

我想您想遍历叶节点（无论如何内部节点的实现并没有什么不同）。您或多或少需要一个 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？左孩子还是右孩子？

于 2013-11-12T10:10:20.860 回答