C++数据结构——二叉搜索树迭代器的实现

骑猪看日落 2021-11-22 16:22 189阅读 0赞

**1.二叉搜索树迭代器的中序遍历  
![20130802171739000][]  
  
  
  
  
  
  
2.迭代器的++指向中序遍历的下一个节点  
\*如果右子树不空，则移动到右子树，并沿着左边向下，直到当前节点的左指针为空，例如12的下一节点14  
\*如果右子树为空，则沿着父指针链向上查找，直到找到以当前节点作为左子结点的父节点，例如23的下一节点25  
特殊情况:  
(1)沿着父指针链向上查找，最终父节点为空，说明迭代器指向的是最后一个节点，直接返回end()  
(2)迭代器本身是end().  
  
  
  
  
  
3.迭代器的--与++类似  
\*如果左子树不空，则移动到左子树，并沿着右边向下，直到当前节点的右指针为空，例如25的前驱23  
\*如果左子树为空，则沿着父指针链向上查找，直到找到一当前节点作为右节点的父节点，例如14的前驱节点12  
特殊情况:  
(1)沿着父指针链向上查找，最终父节点为空，说明迭代器指向的是第一个节点，直接返回end()  
(2)迭代器本身是begin(),此时返回最后一个节点  
  
实现代码：  
  
node.h  
\#ifndef node\_H  
\#define node\_H  
template<typename T>  
class node  
\{  
public:  
node<T> \*parent; //父节点指针  
node<T> \*left; //左节点指针  
node<T> \*right; //右节点指针  
T val; //节点值   
  
node():parent(nullptr),left(nullptr),right(nullptr)\{\}  
node(T v, node<T> \*p=nullptr, node<T> \*l=nullptr, node<T> \*r=nullptr):val(v),parent(p),left(l),right(r)\{\}  
  
\};  
  
  
  
  
\#endif  
  
  
  
myIterator.h  
  
  
\#ifndef myIterator\_H  
\#define myIterator\_H  
\#include"node.h"  
  
  
class myIterator  
\{  
friend class bs\_Tree<T>;  
private:  
node<T> \*curr; //迭代器指向的当前指针  
bs\_Tree<T> \*obj; //迭代器所在的对象  
myIterator(node<T> \*c, bs\_Tree<T> \*o):curr(c),obj(o)\{\}  
  
//查找按中序遍历时的第一个节点   
node<T>\* findLeftFirst(node<T>\* root)  
\{   
node<T> \*temp=root;  
while(temp->left)  
\{   
temp=temp->left;  
\}   
  
return temp;  
\}   
  
//查找按中序遍历时的最后节点   
node<T>\* findRightLast(node<T>\* root)  
\{   
while(root->right)  
\{   
root=root->right;  
\}   
  
return root;  
\}   
  
  
public:  
myIterator()\{\};  
  
 T operator\*()//解引用运算符  
 \{   
return curr->val;  
 \}  
  
 bool operator==(const myIterator &rf) //等于运算符   
\{   
return curr==rf.curr;  
\}   
  
bool operator!=(const myIterator &rf)//不等于运算符   
\{   
return curr!=rf.curr;  
\}   
  
 myIterator& operator++()//前置++   
 \{   
  
if(!curr)//迭代器指向的指针为空，说明为end()   
\{   
 curr=findLeftFirst(obj->root);//使tem指向中序遍历二叉树的第一个节点  
\}  
else  
\{   
if(curr->right) //当前节点的右子树非空  
\{   
  
 curr=findLeftFirst(curr->right);//使curr指向curr->right中序遍历二叉树curr节点的后继  
\}   
else //当前节点的右子树为空  
\{   
node<T> \*prt=curr->parent;  
  
  
while(prt&&prt->right==curr)//沿着父指针链向上查找，直到找到以当前节点作为左子结点的父节点  
\{   
curr=prt;   
prt=prt->parent;  
  
\}  
  
  
  
curr=prt; //此时curr返回的可能为返回空指针（表明当前迭代器指向最后一个节点）或者中序遍历二叉树curr节点的后继  
  
\}   
\}   
  
return \*this;   
 \}  
  
 myIterator operator++(int)//后置++   
 \{   
myIterator tem(\*this);  
\++\*this;  
return tem;  
 \}  
  
 myIterator& operator--() //前置--  
\{   
 if(!curr)//迭代器为end()   
 \{   
curr=findRightLast(obj->root);//返回最后一个元素  
 \}  
 else  
 \{   
  
if(curr->left)//左子树不空，则移动到左子树，并沿着右边向下，直到当前节点的右指针为空  
\{   
curr=findRightLast(curr->left);  
\}  
else//左子树为空  
\{   
node<T> \*prt=curr->parent;  
while(prt&&prt->left==curr)//沿着父指针链向上查找，直到找到一当前节点作为右节点的父节点  
\{   
curr=prt;  
prt=prt->parent;  
  
  
\}   
  
  
curr=prt;//此时curr返回的可能为返回空指针（表明当前迭代器指向第一个节点）或者中序遍历二叉树curr节点的前驱  
  
  
\}  
  
 \}  
 return \*this;  
\}   
  
myIterator operator--(int)//后置--  
 \{   
myIterator tem(\*this);  
\--\*this;  
return tem;  
 \}  
  
  
\};  
  
  
  
  
  
\#endif  
  
  
  
二叉搜索树迭代器的测试代码详见**

### [C++数据结构——二叉搜索树（实现自定义迭代器）][C] ###

[20130802171739000]: /images/20211122/d34ad858d41540ba8e4a9129dc686708.png
[C]: http://blog.csdn.net/piniheaven/article/details/9719683