使用C ++ 11在二进制（或任意）树上实现迭代器 [英] Implementing an iterator over binary (or arbitrary) tree using C++ 11
问题描述
我想在二叉树上创建一个迭代器，以便能够使用基于范围的for循环。我理解我应该首先实现begin（）和end（）函数。
Begin应该指向根目录。根据规范，end（）函数返回最后一个有效元素之后的元素。哪个元素（节点）是？指向一些无效的地方不是非法的吗？
另一件事是运算符++。在树中返回next元素的最好方法是什么？我只需要一些建议，从这个编程开始。
我想扩展/增加我的问题*。如果我想用一个任意的arity迭代一棵树呢？让每个节点有一个孩子的向量，让begin（）指向真正的根。我可能需要在iterator类中实现一个队列（为广度优先）存储unique_ptr到节点，对吧？然后，当队列为空时，我知道我已经通过了所有的节点，因此应该在调用oprator ++（）时返回TreeIterator（nullptr）。是否有意义？我希望它尽可能简单，只有向前迭代。
*或者我应该创建新主题吗？
你的 begin（）应该指向几乎取决于你要遍历你的树的顺序。使用根可以是明智的，例如，对于树的宽度第一步。 end（）实际上并不坐在树节点上：访问此位置并指示到达序列的结尾。它是否指示与树有关的任何事物取决于您要支持什么样的迭代：当仅支持向前迭代时，它只能指示结束。当还支持双向迭代时，它需要知道如何在结束之前找到该节点。
在任何情况下，指向的地方并不真正访问，需要一个合适的指标。对于正向迭代，只有迭代器 end（）可能只返回一个指向null的迭代器，并且当你从最后一个节点移动时，你只需将迭代器的指针设置为null：平等比较两个指针会产生 true ，表示你已经到达结束。当需要支持双向迭代时，您需要某种链接记录，可以用于导航到上一个节点，但不需要存储值。
有序的关联容器（ std :: map< K，V> ， std：set< V> 。）在内部实现为某种树（例如，红/黑树）。 begin（）迭代器从最左边的节点开始， end（）迭代器指的是最右边的节点。 运算符++（）只是找到当前右侧的下一个节点：
- 如果迭代器坐在没有右子节点的节点上，它沿着父节点链行进，直到找到父节点通过树的左分支到达其子节点
- 在具有右子节点的节点上，它走向该子节点，然后沿着该子节点的左子节点的顺序（如果有的话），找到右子树中最左子节点。
- if the iterator sits on a node without a right child node, it walks along the chain of parents until it finds a parent reaching its child via the left branch of the tree
- if it sits on a node with a right child node it walks to the child and then down the sequence of left children of this child (if any) to find the left-most child in the right subtree.
显然，如果你不从左到右走你的树，而是从顶部到底部，你需要一个不同的算法。对我来说最简单的方法是在一张纸上画一棵树，看看如何到达下一个节点。
如果你没有实现数据结构你自己的迭代器我建议尝试一个简单的顺序数据结构，例如，一个列表：很明显如何到达下一个节点，当到达结束。一旦一般的迭代原理是清楚的，创建树只是一个获得导航权利的问题。
I would like to create an iterator over the binary tree so as to be able to use range-based for loop. I understand I ought to implement the begin() and end() function first.
Begin should probably point to the root. According to the specification, however, the end() functions returns "the element following the last valid element". Which element (node) is that? Would it not be illegal to point to some "invalid" place?
The other thing is the operator++. What is the best way to return "next" element in tree? I just need some advice to begin with this programming.
I would like to expand/augment my question*. What if I wanted to iterate over a tree with an arbitrary arity? Let each node have a vector of children and let begin() point to the "real" root. I would probably have to implement a queue (for breadth-first) inside the iterator class to store the unique_ptr's to nodes, right? Then, when the queue is empty I would know that I have passed all nodes and thus should return TreeIterator(nullptr) when oprator++() is called. Does it make sense? I want it as simple as possible and only forward iteration.
*Or should I create a new thread?
Where your begin() should point to pretty much depends on the order in which you want to traverse your tree. Using the root may be sensible, e.g., for a breadth first walk of the tree. The end() doesn't really sit on a tree node: this position is accessed and indicates that the end of the sequence is reached. Whether it indicates anything related to the tree somewhat depends on what sort of iteration you want to support: when supporting only forward iteration it can just indicate the end. When also supporting bidirectional iteration, it needs to know how to find the node right before the end.
In any case, the place pointed to isn't really accessed and you need a suitable indicator. For a forward iteration only iterator end() could just return an iterator pointing to null and when you move on from the last node you just set the iterator's pointer to null as well: equality comparing the two pointers would yield true, indicating that you have reached the end. When wanting to support bidirectional iteration you'll need some sort of link record which can be used to navigate to the previous node but which doesn't need to store a value.
The ordered associated containers (std::map<K, V>, std:set<V>, etc.) are internally implemented as some sort of tree (e.g., a Red/Black-tree). The begin() iterator starts with the left-most node and the end() iterator refers to the position after the right-most node. The operator++() just finds the next node to the right of the current:
Obviously, if you don't walk your tree from left to right but rather, e.g., from top to bottom, you'll need a different algorithm. The easiest approach for me is to draw a tree on a piece of paper and see how to get to the next node.
If you haven't implemented a data structure using your own iterators I'd recommend trying things out on a simple sequential data structure, e.g., a list: There it is pretty obvious how to reach the next node and when the end is reached. Once the general iteration principle is clear, creating a tree is just a matter of getting the navigation right.
这篇关于使用C ++ 11在二进制（或任意）树上实现迭代器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
