Python3实现二叉树的遍历算法（源代码）
需积分: 1 193 浏览量
2024-04-30
14:43:06
上传
评论
收藏 74KB PDF 举报
首先，我们需要定义一个二叉树节点类（TreeNode）：
然后，我们可以实现前序、中序和后序遍历的算法：
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
# 前序遍历（根-左-右）
def preorderTraversal(root):
if root is None: # 如果根节点为空，则返回空列表
return []
result = []
stack = [root] # 使用栈来辅助遍历
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 []
result = []
stack = [] # 使用栈来辅助遍历
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 []
result = []
# 使用递归实现后序遍历
资源评论
