二叉搜索树的迭代器版本实现

2017-05-27 14:27 阅读 668 次 评论 0 条

迭代器在某种程度上可以理解为智能指针(Smart Pointer),我们之所以在实现了BinarySearchTree之后还要实现迭代器版本,原因在于二叉搜索树中的算法与底层的数据结构的耦合性很高(软件工程追求高内聚,低耦合),而迭代器则将算法与数据结构解耦,使得算法可以适应不同的数据结构。

迭代器的设计要求

迭代器其实就是将指针封装成一个类,因此我们在原先BinarySearchTree的基础上,也应该实现指针的操作:

当然,上述操作中,我将对前置++、后置++、前置--、后置--作以详细说明,在代码中,前置与后置是可以复用的,因此我只需要实现Increment()++函数Decrement()--函数

Increment()的实现

为了方便起见,我们会引入一个头结点(pHead或end),它与根节点互为双亲关系,且它的左指针域指向二叉搜索树中序遍历的第一个节点(标记为begin),右指针域指向中序遍历的最后一个节点。如下图所示:

情况①:右子树存在:当前节点的下一个节点为右子树中最小的结点。

情况②:右子树不存在:则分为根节点的右子树存在不存在两种情况。若存在:则指向指向根节点。不存在:指向根节点,在循环过程中会导致死循环,需要重新处理。

Decrement()的实现

情况①:左子树存在:找到左子树中最右边的结点。

情况②:左子树不存在:指向当前二叉搜索树的根节点。

源代码及注释

实现代码中仅对迭代器部分作以注释,其他部分的详细注释见我的二叉搜索树

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:二叉搜索树的迭代器版本实现 | 术与道的分享
分类:编程素养 标签:,
1024do.com导航_术与道导航平台

发表评论


表情