二、红黑树的迭代器
迭代器本质上是指针的一个封装的类，其底层就是指针；好处是可以方便遍历，是数据结构的底层实现与用户透明
对于string,vector,list等容器，其本身的结构上是比较简单的，迭代器的实现也很简单；但是对于二叉树结构的红黑树来说需要考虑很多的问题
1、begin()与end()
STL明确规定：begin()与end()代表的是一段前闭后开的区间
对红黑树进行中序遍历后，可以得到一个有序的序列，因此begin()可以放在红黑树中最小节点(即最左侧节点)的位置，end()放在最大节点(最右侧节点)的下一个位置即nullptr
- 示图：
2、operator++()与operator–()
找到begin()和end()之后，要遍历红黑树最主要的还是能找到要遍历的下一个节点
红黑树的中序遍历是有序的，也就是说：当一个结点的正向迭代器进行++操作后，应该根据红黑树中序遍历的序列找到当前结点的下一个结点
实现++逻辑：
对于中遍历到当前节点来说，该节点的左子树应该是已经被遍历过了，所以只需要考虑右子树
如果当前结点的右子树不为空，则++操作后应该找到其右子树当中的最左结点
如果当前结点的右子树为空，则该子树已经被遍历完了，则++操作后应该在该结点的祖先结点中找到孩子不在父亲右的祖先
说明：
如果是孩子节点在父亲的左，说明父亲的右节点没有遍历
如果孩子在父亲的右，说明以父亲节点为根的子树已经遍历完了，还需要继续向上找
如果一直向上遍历到nullptr说明整颗树已经遍历完了（end()返回的就是nullptr）
注：怎么看该节点的右节点遍历过没有，这里需要一个指针记录上一次经过的节点地址，进行比较地址就行了
实现++代码：
Self& operator++() { if (_node->_right)//右子节点存在 { //找到右子树中最左节点 Node* cur = _node->_right; while (cur->_left) { cur = cur->_left; } _node = cur; } else//右子节点不存在，向上找 { Node* cur = _node;//记录走过的节点 Node* parent = _node->_parent; while (parent && parent->_right == cur) { cur = parent; parent = parent->_parent; } _node = parent; } return *this; }
注：对于–来说可以参考++的实现，逻辑是完全相反的
- 实现–代码：
Self& operator--() { if (_node->_left)//左子节点存在 { //找左子树中的最右节点 Node* cur = _node->_left; while (cur->_right) { cur = cur->_right; } _node = cur; } else//左子节点不存在 { Node* cur = _node; Node* parent = _node->_parent; while (parent && parent->_left == cur) { cur = parent; parent = parent->_parent; } _node = parent; } return *this; }
3、正反迭代器的实现
对于正向迭代器与反向迭代器的区别就是：begin()指向的位置不一样；迭代器的++和–的实现相反，但本质上还是差不多的
所以实现正向迭代器后，我们可以直接使用适配器，在正向迭代器的基础上，对其接口进行封装达到反向迭代器的效果
正向迭代器实现代码：
template<class T, class Ref, class Ptr> struct _TreeIterator { //声明类型，便于反向迭代器对类型的提取 typedef Ref reference; typedef Ptr pointer; typedef RBTreeNode<T> Node; typedef _TreeIterator<T, Ref, Ptr> Self; Node* _node; _TreeIterator(Node* node) :_node(node) {} Ref operator*() { return _node->_data; } Ptr operator->() { return &_node->_data; } bool operator==(const Self& it)const { return _node == it._node; } bool operator!= (const Self& it)const { return _node != it._node; } Self& operator++() { if (_node->_right) { Node* cur = _node->_right; while (cur->_left) { cur = cur->_left; } _node = cur; } else { Node* cur = _node; Node* parent = _node->_parent; while (parent && parent->_right == cur) { cur = parent; parent = parent->_parent; } _node = parent; } return *this; } Self& operator--() { if (_node->_left) { Node* cur = _node->_left; while (cur->_right) { cur = cur->_right; } _node = cur; } else { Node* cur = _node; Node* parent = _node->_parent; while (parent && parent->_left == cur) { cur = parent; parent = parent->_parent; } _node = parent; } return *this; } };
- 反向迭代器实现代码：
//适配器构造反向迭代器 template<class Iterator> struct ReverseIterator { //类型未实例化，无法取出里面的类型，此时需要使用typename：告诉编译器等实例化后再到类里面找对应的类型 typedef typename Iterator::reference Ref; typedef typename Iterator::pointer Ptr; typedef ReverseIterator<Iterator> Self; Iterator _it; ReverseIterator(Iterator it) :_it(it) {} //在正向迭代器接口上进行封装复用 Ref operator*() { return *_it; } Ptr operator->() { return _it.operator->(); } bool operator==(const Self& it)const { return it._it==_it; } bool operator!= (const Self& it)const//两个const { return _it != it._it; } Self& operator++() { --_it; return *this; } Self& operator--() { ++_it; return *this; } };
