python用次遍历写二叉树的前中后序遍历
时间: 2023-11-03 12:25:29 浏览: 40
二叉树的前中后序遍历是树的常见遍历方式,可以使用递归和迭代两种方式进行实现。下面是使用迭代方式实现前中后序遍历的示例代码:
```
# 定义二叉树节点
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
# 二叉树前序遍历
def pre_order(root):
if not root:
return []
stack, res = [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
# 二叉树中序遍历
def in_order(root):
if not root:
return []
stack, res = [], []
while stack or root:
if root:
stack.append(root)
root = root.left
else:
node = stack.pop()
res.append(node.val)
root = node.right
return res
# 二叉树后序遍历
def post_order(root):
if not root:
return []
stack1, stack2, res = [root], [], []
while stack1:
node = stack1.pop()
stack2.append(node)
if node.left:
stack1.append(node.left)
if node.right:
stack1.append(node.right)
while stack2:
res.append(stack2.pop().val)
return res
```
这里使用了栈来模拟递归过程,遍历二叉树的节点。前序遍历是先遍历根节点,然后遍历左子树和右子树;中序遍历是先遍历左子树,然后遍历根节点和右子树;后序遍历是先遍历左子树和右子树,最后遍历根节点。