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

作者：IT小白 | 2024-05-14 17:29:08

踩

c++树的迭代器实现

1.二叉搜索树迭代器的中序遍历

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)

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/569394