宁夏建网站报价,山东省住房建设部网站首页,福田网站制作,重庆农村网站建设一、红黑树的迭代器 红黑树的遍历默认为中序遍历 —— key 从小到大#xff0c;因此 begin() 应该获取到红黑树的最左节点 —— 最小#xff0c;end() 获取到红黑树最右节点的下一个位置#xff0c; operator() 也应保证红黑树的遍历为中序的状态。 首先对红黑树节点进行改造…一、红黑树的迭代器 红黑树的遍历默认为中序遍历 —— key 从小到大因此 begin() 应该获取到红黑树的最左节点 —— 最小end() 获取到红黑树最右节点的下一个位置 operator() 也应保证红黑树的遍历为中序的状态。 首先对红黑树节点进行改造 引入一个模板参数 T 使 RBTreeNode / RBTree 成为一个适配器当我们向 RBTree 中传 key 时封装 set 容器向 RBTree 中传 pairkey, value 时封装 map 容器。 1.1 定义红黑树的迭代器 templateclass T, class Ref, class Ptr // 与 list 迭代器处没有区别Ref —— T Ptr —— T*struct RBTreeIterator{typedef RBTreeNodeT Node;typedef RBTreeNodeIteratorT 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;}总结
迭代器指向节点的右子树不为空时 operator() 的下一个位置就是其右子树的最左节点。迭代器指向节点的右子树为空意味当前节点所在的左子树已经全部访问完了operator() 的下一个位置是当前子树为左子树的最近祖宗节点。
1.3 operator*() Ref operator*(){return _node-_data;}1.4 operator-() Ptr operator-(){return (_node-_data);}
