手机版
你好,游客 登录 注册
背景:
阅读新闻

谈一谈二叉搜索树中序迭代器的关键设计

[日期:2015-05-01] 来源:Linux社区  作者:zxh1210603696 [字体: ]

之前在完成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行代码处理节点无右子树需要向父节点移动的情况。

二叉树的常见问题及其解决程序 http://www.linuxidc.com/Linux/2013-04/83661.htm

【递归】二叉树的先序建立及遍历 http://www.linuxidc.com/Linux/2012-12/75608.htm

Java中实现的二叉树结构 http://www.linuxidc.com/Linux/2008-12/17690.htm

【非递归】二叉树的建立及遍历 http://www.linuxidc.com/Linux/2012-12/75607.htm

二叉树递归实现与二重指针 http://www.linuxidc.com/Linux/2013-07/87373.htm

二叉树先序中序非递归算法 http://www.linuxidc.com/Linux/2014-06/102935.htm

轻松搞定面试中的二叉树题目 http://www.linuxidc.com/linux/2014-07/104857.htm

本文永久更新链接地址http://www.linuxidc.com/Linux/2015-05/116893.htm

linux
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数

       

评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款