我要看一集片做网站,企业黄页网站源码,网站文案优化,做直播网站要什么证吗红黑树#xff0c;AVLTree树底层实现逻辑都是平衡二叉树#xff08;AVLTree高度平衡#xff0c;红黑树以某种规则平衡#xff09;#xff0c;但终究不像链表的迭代器那样逻辑简单。 简单叙述以下#xff0c;二叉树上面迭代器的运行逻辑#xff0c;根据下面的图#xff… 红黑树AVLTree树底层实现逻辑都是平衡二叉树AVLTree高度平衡红黑树以某种规则平衡但终究不像链表的迭代器那样逻辑简单。 简单叙述以下二叉树上面迭代器的运行逻辑根据下面的图迭代器的begin就是二叉树的最左节点end是二叉树根节点的父节点NULL。 为什么要这样设计因为平衡二叉树在中序遍历下是升序排列所以只有首部begin在二叉树最左节点向后遍历时才能打印有序数据。 但是为什么end在根节点的父亲 因为外部循环while(it!end()),是不等于end节点所以在遍历完右子树后就像上返回找类似于下图中绿色的parent节点了(右子树遍历完向上找)所以遍历完整颗二叉树后就会向上找节点到了父节点的父亲时就为空了也就是end节点所以就停止遍历了。 代码
templateclass T
struct __TreeIterator
{typedef RBTreeNodeT Node;typedef __TreeIteratorT Self;Node* _node;//迭代器存的是二叉树的节点__TreeIterator(Node* node):_node(node){}T operator*(){return _node-_data;}T* operator-(){return _node-_data;}//这就是平衡二叉树迭代器的运行核心 一定要理解这部分逻辑才能理解好这个迭代器Self operator(){if (_node-_right){// 下一个就是右子树的最左节点Node* cur _node-_right;while (cur-_left){cur cur-_left;}_node cur;}else{// 左子树 根 右子树// 右为空找孩子是父亲左的那个祖先Node* cur _node;Node* parent cur-_parent;while (parent cur parent-_right){cur parent;parent parent-_parent;}_node parent;}return *this;}//给外界判断提供的bool operator!(const Self s){return _node ! s._node;}bool operator(const Self s){return _node s._node;}
}; Self operator--(){if (_node-_left){Node* subRight _node-_left;while (subRight-_right){subRight subRight-_right;}_node subRight;}else{// 孩子是父亲的右的那个节点Node* cur _node;Node* parent cur-_parent;while (parent cur parent-_left){cur cur-_parent;parent parent-_parent;}_node parent;}return *this;}
