Python 二分木走査アルゴリズムの実装とコード例

Pythonで、二叉木の3つの走査アルゴリズム（前順走査、中順走査、後順走査）を再帰を使って実装することができる。

以下是一个简单的二叉树节点类的定义：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

次に、前順探査、中順探査、後順探査アルゴリズムを実装するために、三つの関数を定義することができます。

1. 前順序走査：まず根ノードを訪れ、その後左部分木を再帰的に走査し、最後に右部分木を再帰的に走査する。

def preorderTraversal(root):
    result = []
    if root:
        result.append(root.val)
        result += preorderTraversal(root.left)
        result += preorderTraversal(root.right)
    return result

1. 木構造の中で、インオーダー・トラバーサルは、まず左の子ノードを再帰的に訪問し、次に親ノードを訪問し、最後に右の子ノードを再帰的に訪問する方法です。

def inorderTraversal(root):
    result = []
    if root:
        result += inorderTraversal(root.left)
        result.append(root.val)
        result += inorderTraversal(root.right)
    return result

1. 後行（ポストオーダー）：まず左の子ツリーを再帰的に探索し、次に右の子ツリーを再帰的に探索して、最後に根ノードを訪問する。

def postorderTraversal(root):
    result = []
    if root:
        result += postorderTraversal(root.left)
        result += postorderTraversal(root.right)
        result.append(root.val)
    return result

次に、二分木を作成し、上記の関数を使用して走査できます。

# 创建一个二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

# 前序遍历
print(preorderTraversal(root))  # Output: [1, 2, 4, 5, 3]

# 中序遍历
print(inorderTraversal(root))   # Output: [4, 2, 5, 1, 3]

# 后序遍历
print(postorderTraversal(root)) # Output: [4, 5, 2, 3, 1]

これがPythonを使用して二分木を実装する3つの遍歴アルゴリズムの方法です。