迭代器实现中序遍历的原理
时间: 2023-08-15 13:21:53 浏览: 46
迭代器实现中序遍历也是使用栈的数据结构来实现的。与迭代实现中序遍历相比,迭代器实现中序遍历更加简洁,因为它不需要考虑如何处理空节点。其基本原理是使用一个栈来保存节点,每次迭代时,首先将当前节点的所有左子节点依次入栈,并将当前节点更新为左子节点;当栈不为空时,弹出栈顶元素作为当前节点,并返回其值;然后将当前节点更新为其右子节点。迭代器实现中序遍历的代码如下:
```python
class InorderIterator:
def __init__(self, root):
self.stack = []
self.cur = root
def __next__(self):
while self.cur or self.stack:
if self.cur:
self.stack.append(self.cur)
self.cur = self.cur.left
else:
node = self.stack.pop()
res = node.val
self.cur = node.right
return res
raise StopIteration
```
在该实现中,`__init__`方法初始化迭代器时,将根节点作为当前节点,并将一个空栈作为辅助结构;`__next__`方法在每次迭代时,首先将当前节点的所有左子节点依次入栈,并将当前节点更新为左子节点;当栈不为空时,弹出栈顶元素作为当前节点,并返回其值;然后将当前节点更新为其右子节点。当迭代结束时,抛出`StopIteration`异常。