溫馨提示×

Python TreeNode如何實(shí)現(xiàn)樹的遞歸和非遞歸遍歷

小樊
89
2024-08-17 16:26:38
欄目: 編程語言

實(shí)現(xiàn)樹的遞歸和非遞歸遍歷可以通過Python中的TreeNode類來實(shí)現(xiàn)。TreeNode類表示樹的節(jié)點(diǎn)，包括節(jié)點(diǎn)的值和左右子節(jié)點(diǎn)。以下是一個示例實(shí)現(xiàn)：

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)

# 非遞歸遍歷，使用棧實(shí)現(xiàn)
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類來表示樹的節(jié)點(diǎn)，然后分別實(shí)現(xiàn)了遞歸遍歷和非遞歸遍歷的函數(shù)。在示例用法中，創(chuàng)建了一棵二叉樹，并分別使用遞歸和非遞歸方法進(jìn)行遍歷輸出結(jié)果。

0 踩