C++，实现二叉树的自定义迭代器（长）

Question

请保持好 - 这是我的第一个问题。 = P

基本上作为一个暑期项目，我一直在浏览wikipedia page上的数据结构列表并试图实现它们。上个学期我参加了一门C++课程，发现它非常有趣，作为最后一个项目，我实现了一个Binomial堆 - 这也非常有趣。也许我很讨厌，但我喜欢数据结构。

无论如何，足够的背景故事。该项目进展顺利，我从Binary Trees开始。尽管我需要创建遍历树的迭代器，但要进一步深入。我已经决定为每个遍历方法（常规迭代器和常量迭代器）创建两种类型的迭代器，但我不知道如何执行此操作。我听说过从stl的迭代器的东西继承，甚至使用提升iterator_facade（这似乎是一个很好的选择）

我甚至没有试图写迭代器代码，因为我不知道从哪里开始，但我在github上有我的当前代码。你可以看看here。

如果你反对github，我正在粘贴相关的类定义。这些功能的实现不会有任何帮助，但如果您出于某种原因需要它们，请告诉我。此外，节点类还有一个用于迭代目的的父指针。

#ifndef __TREES_HXX 
#define __TREES_HXX 
#include <cstdlib> // For NULL 
#include <algorithm> // for std::max 

// Node class definition. These nodes are to be used for any 
// tree where the structure is 
// node 
//  /\ 
// left right 
// /\ /\ 
// 
// etc., basically two children. 
template <typename T> 
class Node 
{ 
    public: 
    T data_; 
    Node<T>* left_; 
    Node<T>* right_; 
    Node<T>* parent_; // Needed for iterators 

    explicit Node(T const&); 
    Node(Node<T> const&); 
}; 

template <typename T> 
class BinaryTree 
{ 
    protected: 
    typedef Node<T>* node_t; 
    size_t tree_size; 

    public: 
    typedef T value_type; 

    explicit BinaryTree(); 
    explicit BinaryTree(T const&); 
    ~BinaryTree(); 

    virtual node_t insert(node_t&, T) = 0; 
    virtual T& lookup(node_t const&, T const&) const = 0; 
    inline virtual size_t size() const; 
    inline virtual size_t depth(node_t const&) const; 
    inline bool empty() const; 
    inline void clear(node_t); 

    node_t root; 
}; 

这是我们抽象类的基本二叉树扩展，基本上它（将）是一个BST。有关为什么我需要迭代器的示例，请查看查找函数的定义。它应该将一个迭代器返回到找到该东西的节点。

/* Implementation of our Binary Tree is in 
* this file. The node class is in Trees.hxx 
* because it's intended to be a general class. 
*/ 

#ifndef __BINARY_TREE_HXX 
#define __BINARY_TREE_HXX 

#include "Trees.hxx" 


template <typename T> 
class BiTree : public BinaryTree<T> 
{ 
    private: 
    typedef typename BinaryTree<T>::node_t node_t; 

    public: 
    typedef typename BinaryTree<T>::value_type value_type; 

    BiTree() : BinaryTree<T>() 
    { 
    } 

    BiTree(T const& data) : BinaryTree<T>(data) 
    { 
    } 

    node_t insert(node_t&, T); 
    T& lookup(node_t const&, T const&) const; // Note: This should return an iterator to the node where the stuff is found 
}; 

我认为这就是 - 感谢您的时间！如果您需要其他信息，请告诉我。

Answer 1

1.脂肪迭代器VS精益迭代

有实现树的遍历两种可能的方式。您可以：

• 有一个简单的指向是保持一个堆栈自己的“孩子”，和迭代器节点（因此，脂肪迭代）
• 有有父指针（像你这样）节点，和迭代器只是指向给定节点（瘦迭代）

这是一个设计权衡，STL的实现者通常会瘦的方法，因为迭代器（在STL）应该是便宜复制。

2。易迭代器VS从无到有的迭代器

也有实现迭代几种方法：

• 从零开始：你自己做的一切，其中包括typedef的定义，所有的运算符重载等...
• 容易：您使用Boost.Iterator自己执行尽可能少的代码尽可能

我基本上算从std::iterator继承为“从头开始”的局面，因为它提供了一个只有5 typedef ...

是否选择一种或另一种完全取决于您的情况：

• 对于学习的目的，我建议去了“从零开始”的方式几次
• 的生产用，我建议去了“从零开始”的方式（与Boost继承不会节省很多，但它确实复杂调试会话/内存转储，至少用gdb，因为GDB暴露基类）
• 为了快速测试，我会推荐走“易”路

请注意，你可能会在一个奇怪的情况下你的迭代器不能真正对Boost.Iterator上方内置，在这种情况下，你别无选择，只能自己去建立它。

3.常量和非const迭代器

这或许是要点。

如果只是为了这一点，这是值得看的Boost.Iterator，因为它们暴露于实现一个迭代器（模板），将覆盖都箱子技术。

看在Iterator Adaptor的教程例部分：

template <class Value> 
class node_iter 
    : public boost::iterator_adaptor< 
     node_iter<Value>    // Derived 
     , Value*       // Base 
     , boost::use_default    // Value 
     , boost::forward_traversal_tag // CategoryOrTraversal 
    > 
{ 
private: 
    struct enabler {}; // a private type avoids misuse 

public: 
    node_iter() 
     : node_iter::iterator_adaptor_(0) {} 

    explicit node_iter(Value* p) 
     : node_iter::iterator_adaptor_(p) {} 

    /// !!! Highlight !!! 
    template <class OtherValue> 
    node_iter(
     node_iter<OtherValue> const& other 
     , typename boost::enable_if< 
      boost::is_convertible<OtherValue*,Value*> 
      , enabler 
     >::type = enabler() 
    ) 
     : node_iter::iterator_adaptor_(other.base()) {} 

private: 
    friend class boost::iterator_core_access; 
    void increment() { this->base_reference() = this->base()->next(); } 
}; 

的第三构造是关键点，以得到一个对const和非const迭代器与自动转换从const到非const没有反向转换是可能的。

不管你做什么，重复使用相同的伎俩：模板化上Value一个BaseIterator，并且提供两个类型定义：​​和typedef BaseIterator<Value const> const_iterator。

Answer 2

实现此目的的一种方法是在迭代器中有一个跟踪父节点的堆栈。每次到达一个节点时，它都不是一片叶子，将它推入堆栈并按照搜索顺序进入下一个节点。一旦你点击一个叶子，处理它，然后返回到堆栈顶部的节点。重复广告Nausium，直到你访问了所有东西。