遍历二叉树的非递归算法
时间: 2023-07-10 20:09:23 浏览: 48
遍历二叉树的非递归算法可以使用栈来实现。具体步骤如下:
1. 首先将根节点压入栈中。
2. 当栈不为空时,循环执行以下操作:
a. 弹出栈顶节点,并打印该节点的值。
b. 如果该节点有右子树,则将右子树压入栈中。
c. 如果该节点有左子树,则将左子树压入栈中。
下面是一个示例代码,可以实现前序遍历、中序遍历、后序遍历的非递归算法:
```python
# 前序遍历
def preorder_traversal(root):
stack = [root]
while stack:
node = stack.pop()
if node:
print(node.val, end=' ')
stack.append(node.right)
stack.append(node.left)
# 中序遍历
def inorder_traversal(root):
stack = []
node = root
while stack or node:
while node:
stack.append(node)
node = node.left
node = stack.pop()
print(node.val, end=' ')
node = node.right
# 后序遍历
def postorder_traversal(root):
stack = []
node = root
last_visited = None
while stack or node:
while node:
stack.append(node)
node = node.left
node = stack[-1]
if not node.right or node.right == last_visited:
node = stack.pop()
print(node.val, end=' ')
last_visited = node
node = None
else:
node = node.right
```
其中,前序遍历和中序遍历的实现比较简单,后序遍历需要使用一个变量来记录上一次访问的节点,以判断当前节点是否可以被访问。