通过红黑树封装 map 和 set 容器（1）：红黑树的迭代器

一、红黑树的迭代器

红黑树的遍历默认为中序遍历 —— key 从小到大，因此 begin() 应该获取到红黑树的最左节点 —— 最小，end() 获取到红黑树最右节点的下一个位置， operator++() 也应保证红黑树的遍历为中序的状态。

首先对红黑树节点进行改造：

引入一个模板参数 T ，使 RBTreeNode / RBTree 成为一个适配器，当我们向 RBTree 中传 key 时，封装 set 容器；向 RBTree 中传 pair<key, value> 时，封装 map 容器。

1.1 定义红黑树的迭代器：

	template<class T, class Ref, class Ptr> // 与 list 迭代器处没有区别，Ref —— T& ，Ptr —— T*struct RBTreeIterator{typedef RBTreeNode<T> Node;typedef RBTreeNodeIterator<T， Ref, Ptr> Self;Node* _node;RBTreeIterator(Node* node):_node(node){}};

1.2 红黑树 operator++()

请务必记住：红黑树迭代器 ++ 为中序遍历 —— 左子树 — 根 — 右子树 ！

假设 cur —— 迭代器 已经走到了 key 为 8 的节点 位置，这代表着 key 为 8 的节点 的左子树已经遍历过了，若 key 为 8 的节点 的右子树不为空，则中序遍历 key 为 8 的节点 的右子树。

	iterator operator++(){if (_node == nullptr) // 空树，直接返回 空 的迭代器{return iterator(nullptr); }if (_node->_right){Node* subLeft = _node->_right;while (subLeft->_left){subLeft = subLeft->_left;}_node = subLeft;}return *this;}

经过 operator++() 后，cur 到了 key 为 11 的节点 位置，此时 cur->_right 为空，表明以 key 为 11 的节点 为最右节点的子树已经全部遍历过，要去找从根到当前节点的简单路径中，cur 所在子树 为 左子树 的最近祖宗节点。

	iterator operator++(){// ...if (_node->_right){ //... }else {Node* cur = _node;Node* parent = cur->_parent;while (parent && cur != parent->_left) // parent 存在 且 cur所在子树不是parent的左子树时{cur = parent;parent = cur->_parent;}_node = parent;}return *this;}

总结：

1. 迭代器指向节点的右子树不为空时， operator++() 的下一个位置就是其右子树的最左节点。
2. 迭代器指向节点的右子树为空，意味当前节点所在的左子树已经全部访问完了，operator++() 的下一个位置是当前子树为左子树的最近祖宗节点。

1.3 operator*()

	Ref operator*(){return _node->_data;}

1.4 operator->()

	Ptr operator->(){return &(_node->_data);}