温馨提示×

Python TreeNode如何实现树的递归和非递归遍历

小樊
87
2024-08-17 16:26:38
栏目: 编程语言

实现树的递归和非递归遍历可以通过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类来表示树的节点,然后分别实现了递归遍历和非递归遍历的函数。在示例用法中,创建了一棵二叉树,并分别使用递归和非递归方法进行遍历输出结果。

0