如何设计 C++ 的二叉树的迭代器

中序历遍

　　我们希望以升序的方式历遍二叉树，这种历遍方式就是中序历遍，好了，那看看中序历遍的非递归实现：

template <typename UnaryFuncion>
void inorderTraverse( UnaryFuncion visit ) const 
{
    auto curr = root_;        
    std::stack<node_ptr> nodeStack;
    
    while( curr || !nodeStack.empty() )
    {
        while( curr )
        {
            nodeStack.push( curr );
            curr = curr->left;
        }
        auto top = nodeStack.top();
        nodeStack.pop();
        visit( top->value );
        curr = top->right;
    }
}

　　可以想到，将中序历遍分成两部分，初始化阶段，以及迭代阶段。先看看初始化阶段：

auto curr = root;
while( curr )
{
    nodeStack.push( curr );
    curr = curr->left;
}

　　还有，迭代阶段：

auto curr = stack.top();
stack.pop();
curr = curr->right;
while( curr )
{
    stack.push( curr );
    curr = curr->left;
}

迭代器设计

　　二叉树的迭代器是 input iterator，可以这样设计：

class const_iterator
{
    friend class BinaryTree;
public:
    using value_type          = T;
    using pointer             = const T*;
    using reference           = const T&;
    using iterator_category   = std::input_iterator_tag;        
    reference operator*() const;
    pointer operator->() const;
    const_iterator &operator++();
    const const_iterator operator++(int);
    bool operator==( const const_iterator &other ) const noexcept;
    bool operator!=( const const_iterator &other ) const noexcept;
protected:
    const_iterator( const BinaryTree *t, bool end ) 
        : tree( t ), index( 0 ) 
    {
        // ...
    }
    const BinaryTree             *tree;
    size_type                    index;
    std::stack<node_ptr>         stack;
};

　　你可能觉得奇怪，为什么有一个成员变量index，考虑一下，我们要怎样比较两个迭代器相等？

bool operator==( const const_iterator &other ) const noexcept
{
    return tree == other.tree && stack == other.stack;
}

　　比较两个栈是否相等的开销比较大，使用index表示元素的编号，我们可以将其改成这样：

bool operator==( const const_iterator &other ) const noexcept
{
    return tree == other.tree && index == other.index;
}
bool operator!=( const const_iterator &other ) const noexcept
{
    return !( *this == other );
}

　　接着看看构造函数，end为true的时候，表示我们创建的是由end()返回的迭代器：

const_iterator( const BinaryTree *t, bool end ) 
    : tree( t ), index( 0 )
{
    if( end || tree->empty() )
    {
        index = tree->size();
    } 
    else
    {
        auto curr = tree->root_;
        while( curr )
        {
            stack.push( curr );
            curr = curr->left;
        }
    }
}

　　可以这样创建迭代器：

const_iterator begin() const
{
    return { this, false };
}
const_iterator end() const
{
    return { this, true };
}

　　迭代器的操作：

reference operator*() const
{ 
    return stack.top()->value;
}
pointer operator->() const
{
    return &( operator*() );
}

自增操作

　　首先，看一下自增操作符：

1
2
3

const_iterator &operator++();                  // 前缀自增，例如 ++i
const const_iterator operator++(int);          // 后缀自增，例如 i++

　　使用后缀自增形式时，编译器会自动传递参数 0 给它：

1
2
3

auto iter = tree.begin();
++i;                        // call iter.operator++();
i++;                        // call iter.operator++(0);

　　为什么后缀自增需要返回一个 const 的 const_iterator 呢？让我们看看基本类型后缀自增：

1 2	int i = 0; i++++; // error: expression is not assignable

　　如果后缀自增返回的不是 const 的 const_iterator，那么，下面的操作就是合法的：

1 2	auto iter = tree.begin(); iter++++; // iter.operator++(0).operator++(0)

　　这种连续的后缀自增操作十分混淆，比如说iter++返回一个临时对象，接着对这个临时对象执行后缀自增操作，但实际上iter只增加了一次。所以我们让后缀自增返回一个 const 对象，以禁止iter++++这种操作。

　　来看看自增操作的实现：

const_iterator &operator++() 
{
    auto curr = stack.top();
    stack.pop();
    
    curr = curr->right;
    while( curr )
    {
        stack.push( curr );
        curr = curr->left;
    }
    ++index;
    
    return *this;
}
const const_iterator operator++(int) 
{
    const auto oldIter = *this;
    ++(*this);
    return oldIter;
}

　　完整的代码：

class const_iterator
{
    friend class BinaryTree;
public:
    using value_type          = T;
    using pointer             = const T*;
    using reference           = const T&;
    using iterator_category   = std::input_iterator_tag;        
    reference operator*() const
    { 
        return stack.top()->value;
    }
    pointer operator->() const
    {
        return &( operator*() );
    }
    
    const_iterator &operator++() 
    {
        auto curr = stack.top();
        stack.pop();
        
        curr = curr->right;
        while( curr )
        {
            stack.push( curr );
            curr = curr->left;
        }
        ++index;
        
        return *this;
    }
    const const_iterator operator++(int) 
    {
        const auto oldIter = *this;
        ++(*this);
        return oldIter;
    }
    bool operator==( const const_iterator &other ) const noexcept
    {
        return tree == other.tree && index == other.index;
    }
    
    bool operator!=( const const_iterator &other ) const noexcept
    {
        return !( *this == other );
    }
protected:
    const_iterator( const BinaryTree *t, bool end ) 
        : tree( t ), index( 0 )
    {
        if( end || tree->empty() )
        {
            index = tree->size();
        } 
        else
        {
            auto curr = tree->root_;
            while( curr )
            {
                stack.push( curr );
                curr = curr->left;
            }
        }
    }
    
    const BinaryTree             *tree;
    size_type                    index;
    std::stack<node_ptr>         stack;
};

中序历遍

迭代器设计

自增操作

参考资料