二叉树遍历python
时间: 2023-10-17 17:30:45 浏览: 118
二叉树遍历有三种常见的方式:前序遍历、中序遍历和后序遍历。以下是使用Python实现这三种遍历方式的示例代码:
```python
# 定义二叉树节点类
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 前序遍历
def preorderTraversal(root):
if root is None:
return []
stack = [root]
result = []
while stack:
node = stack.pop()
result.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return result
# 中序遍历
def inorderTraversal(root):
if root is None:
return []
stack = []
result = []
curr = root
while curr or stack:
while curr:
stack.append(curr)
curr = curr.left
curr = stack.pop()
result.append(curr.val)
curr = curr.right
return result
# 后序遍历
def postorderTraversal(root):
if root is None:
return []
stack = [root]
result = []
while stack:
node = stack.pop()
result.append(node.val)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return result[::-1]
# 创建一个二叉树示例
root = TreeNode(1)
root.right = TreeNode(2)
root.right.left = TreeNode(3)
print("前序遍历结果:", preorderTraversal(root))
print("中序遍历结果:", inorderTraversal(root))
print("后序遍历结果:", postorderTraversal(root))
```
该示例中,我们定义了一个`TreeNode`类来表示二叉树节点,然后实现了前序遍历、中序遍历和后序遍历的函数。通过创建一个二叉树示例,并调用这些函数,可以获得对应的遍历结果。
阅读全文