首页 文章

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

提问于
浏览 次
7

请你好 - 这是我的第一个问题 . = P

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

无论如何，足够的背景故事 . 项目进展顺利，我从二叉树开始 . 为了更进一步，我需要创建迭代器来遍历树 . 我已经决定为每个遍历方法（常规迭代器和常量迭代器）创建两种类型的迭代器，我只是不知道如何做到这一点 . 我听说从stl的迭代器继承，甚至使用boosts 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
 };

我想就是这样 - 谢谢你的时间！如果您需要其他信息，请告诉我们 .

c++ data-structures iterator binary-tree

2 回答

  • 11

    1.胖迭代器与精益迭代器

    有两种可能的方法来实现树的遍历 . 你可以：

    • 有简单指向其"children"的节点，以及保持堆栈的迭代器（因此，胖迭代器）

    • 有节点有父指针（和你的一样），迭代器只是指向给定节点的指针（精益迭代器）

    这是一个设计权衡，STL实现者通常采用精益方式，因为迭代器（在STL中）应该是便宜的复制 .

    1. Easy Iterators vs From scratch迭代器

    还有几种方法可以实现迭代器：

    • From Scratch：你自己做所有事情，包括定义typedef，所有运算符重载等等......

    • 简单：您使用Boost.Iterator自己实现尽可能少的代码

    我基本上计算从 std::iterator 继承为"from scratch"情况，因为它只提供了5 typedef ...

    是否选择其中一个确实取决于您的情况：

    • 出于学习目的，我建议多次使用"From Scratch"方式

    • 出于 生产环境 目的，我建议采用"From Scratch"方式（从Boost继承并不节省太多，但它确实使调试会话/内存转储复杂化，至少使用gdb，因为gdb暴露了基类）

    • 为了快速测试，我建议采用"Easy"方式

    请注意，您可能处于一个奇怪的情况，您的迭代器无法真正构建在Boost.Iterator之上，在这种情况下，您将别无选择，只能自己构建它 .

    1. Const和非const迭代器

    这也许是重点 .

    如果仅为此，则值得查看Boost.Iterator，因为它们公开了实现 one iterator（模板化）的技术，这将涵盖两种情况 .

    查看Iterator Adaptor中的 Tutorial Example 部分：

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

    第3个构造函数是获取一对 const 和非 const 迭代器的关键点，它们具有从 const 到非 const 的自动转换，而无需进行反向转换 .

    无论你做什么，重用同样的技巧：在 Value 上模板化 BaseIterator ，并提供两个typedef： typedef BaseIterator<Value> iterator 和 typedef BaseIterator<Value const> const_iterator .

    回复于
  • 1

    实现此目的的一种方法是在迭代器中使用堆栈来跟踪父节点 . 每次到达节点时，它都不是叶子，将其推入堆栈并继续搜索顺序中的下一个节点 . 一旦你点击一个叶子，处理它，然后返回到堆栈顶部的节点 . 重复广告nausium直到你访问过所有内容 .

    回复于

相关问题