谈一谈二叉搜索树中序迭代器的重点设计
发布时间：2021-11-19 14:37:15 所属栏目：教程 来源：互联网
导读：之前在完成TinySTL项目中二叉搜索树的设计时发现要想完成其中序迭代器的设计，关键的一步是完成迭代器的++操作，当实现了这个操作时那么这个迭代器的90%的操作都可以很快的完成了。 下面先来看看node的定义： struct node{ typedef T value_type; T data_; n
|
之前在完成TinySTL项目中二叉搜索树的设计时发现要想完成其中序迭代器的设计，关键的一步是完成迭代器的++操作，当实现了这个操作时那么这个迭代器的90%的操作都可以很快的完成了。 下面先来看看node的定义： struct node{ typedef T value_type; T data_; node *left_; node *right_; explicit node(T d = T(), node *l = 0, node *r = 0) :data_(d), left_(l), right_(r){} }; 在二叉树中有： 下面来看看我是怎样实现++操作的。 首先是初始化迭代器： template<class T> bst_iter<T>::bst_iter(const T *ptr, cntrPtr container) :ptr_(ptr), container_(container){ if (!ptr_) return; auto temp = container_->root_; while (temp && temp != ptr_ && temp->data_ != ptr_->data_){ parent_.push(temp); if (temp->data_ < ptr_->data_){ //temp向右走说明temo指向的父节点不需要再次访问了 visited_.insert(temp);//add 2015.01.14 temp = temp->right_; } else if (temp->data_ > ptr_->data_){ temp = temp->left_; } } } 在初始化的过程中传入任意的树中节点指针ptr，然后从root开始沿着向下的方向用一个栈parent_来依次记录节点的父节点，同时我用一个set visited_来记录父节点相对于这个节点来说是否是已经访问过的状态，当节点处于这个父节点的右子树中时这个节点被记录。根据中序遍历的定义来看，当要访问任意节点的下一个节点的时候，如果节点还有右子树未访问则跳转到右子树的最小节点，当节点没有右子树的时候我们需要沿着父节点的顺序后退，此时不是所有的父节点都需要访问的，只有当节点处于父节点的左子树时，此时这个父节点才需要访问。 template<class T> bst_iter<T>& bst_iter<T>::operator ++(){ visited_.insert(ptr_);//此node被访问 if (ptr_->right_){//此node还有右子树 //rvisited_.insert(ptr_); parent_.push(ptr_); ptr_ = ptr_->right_; while (ptr_ && ptr_->left_){ parent_.push(ptr_); ptr_ = ptr_->left_; } }else{//node无右子树则只能向父节点路径移动 ptr_ = 0;//add 2015.01.14 while (!parent_.empty()){ ptr_ = parent_.top(); parent_.pop(); if (visited_.count(ptr_) == 0){//父节点尚未访问,此时ptr_指向此节点 visited_.insert(ptr_); break; } ptr_ = 0;//设为哨兵 }//end of while }//end of if return *this; } 第4-11行代码处理节点有右子树的情况。第12-23行代码处理节点无右子树需要向父节点移动的情况。  （编辑：济南站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
