用非递归实现二叉树的前序、中序、后序遍历算法。 注意:非递归算法写前序、中序、后序遍历算法
时间: 2023-06-27 11:02:56 浏览: 123
二叉树的非递归遍历算法通常借助栈来实现。下面分别给出二叉树的前序、中序、后序非递归遍历算法:
1. 前序遍历算法
前序遍历顺序为:根节点 -> 左子树 -> 右子树。
算法流程:
1. 如果根节点不为空,将根节点入栈。
2. 取出栈顶节点,输出该节点的值。
3. 如果该节点的右子节点不为空,将右子节点入栈。
4. 如果该节点的左子节点不为空,将左子节点入栈。
5. 重复步骤2~4,直到栈为空。
Python代码实现:
```python
def preorderTraversal(root):
if not root:
return []
res = []
stack = [root]
while stack:
node = stack.pop()
res.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return res
```
2. 中序遍历算法
中序遍历顺序为:左子树 -> 根节点 -> 右子树。
算法流程:
1. 将根节点入栈。
2. 如果当前节点不为空,将其左子节点入栈,直到左子节点为空。
3. 取出栈顶节点,输出该节点的值。
4. 将栈顶节点的右子节点入栈。
5. 重复步骤2~4,直到栈为空。
Python代码实现:
```python
def inorderTraversal(root):
if not root:
return []
res = []
stack = []
node = root
while stack or node:
while node:
stack.append(node)
node = node.left
node = stack.pop()
res.append(node.val)
node = node.right
return res
```
3. 后序遍历算法
后序遍历顺序为:左子树 -> 右子树 -> 根节点。
算法流程:
1. 将根节点入栈。
2. 如果当前节点不为空,将其左子节点入栈,直到左子节点为空。
3. 如果当前节点的右子节点为空或者已经被访问过,输出该节点的值,并将其出栈。
4. 标记当前节点已被访问。
5. 将当前节点的右子节点入栈。
6. 重复步骤2~5,直到栈为空。
Python代码实现:
```python
def postorderTraversal(root):
if not root:
return []
res = []
stack = [(root, False)]
while stack:
node, visited = stack.pop()
if not node:
continue
if visited:
res.append(node.val)
else:
stack.append((node, True))
stack.append((node.right, False))
stack.append((node.left, False))
return res
```
阅读全文
相关推荐
















