实现树的递归和非递归遍历可以通过Python中的TreeNode类来实现。TreeNode类表示树的节点,包括节点的值和左右子节点。以下是一个示例实现:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 递归遍历
def recursive_traversal(node):
if node is None:
return
print(node.val)
recursive_traversal(node.left)
recursive_traversal(node.right)
# 非递归遍历,使用栈实现
def iterative_traversal(node):
if node is None:
return
stack = []
current = node
while stack or current:
while current:
stack.append(current)
current = current.left
current = stack.pop()
print(current.val)
current = current.right
# 示例用法
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print("递归遍历:")
recursive_traversal(root)
print("\n非递归遍历:")
iterative_traversal(root)
以上代码中,首先定义了一个简单的TreeNode类来表示树的节点,然后分别实现了递归遍历和非递归遍历的函数。在示例用法中,创建了一棵二叉树,并分别使用递归和非递归方法进行遍历输出结果。