Python を使用してバイナリ ツリー トラバーサルを実装する方法

一般的に使用されるデータ構造として、バイナリ ツリーはデータの保存、検索、並べ替えによく使用されます。バイナリ ツリーの走査は、非常に一般的な操作の 1 つです。シンプルで使いやすいプログラミング言語である Python には、バイナリ ツリー トラバーサルを実装するためのメソッドが多数あります。この記事では、Python を使用してバイナリ ツリーの事前順序、順序内、および順序後の走査を実装する方法を紹介します。

バイナリ ツリーの基本

バイナリ ツリーの走査方法を学ぶ前に、バイナリ ツリーの基本概念を理解する必要があります。バイナリ ツリーはノードで構成され、各ノードには値と 2 つの子 (左の子と右の子) があります。ノードの子は空にすることもできます。

バイナリ ツリー トラバーサル

バイナリ ツリー トラバーサルとは、バイナリ ツリー内のすべてのノードを特定の順序で訪問することを指します。一般的に使用されるトラバーサル方法には、前順序トラバーサル、順序内トラバーサル、後順序トラバーサルの 3 つがあります。

プレオーダー トラバーサル

プレオーダー トラバーサルの順序は、ルート ノード、左のサブツリー、右のサブツリーです。特定の実装では、最初にルート ノードの値を出力し、次に左のサブツリーと右のサブツリーを再帰的に走査できます。

以下は Python コードの実装です:

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

def preorderTraversal(root: TreeNode):
    if root is None:
        return []
    res = [root.val]
    res += preorderTraversal(root.left)
    res += preorderTraversal(root.right)
    return res

順序トラバーサル

順序トラバーサルの順序は、左のサブツリー、ルート ノード、右のサブツリーです。特定の実装では、左のサブツリーを再帰的に走査し、ルート ノードの値を出力してから、右のサブツリーを再帰的に走査する必要があります。

以下は Python コードの実装です:

def inorderTraversal(root: TreeNode):
    if root is None:
        return []
    res = []
    res += inorderTraversal(root.left)
    res.append(root.val)
    res += inorderTraversal(root.right)
    return res

事後走査

事後走査の順序は、左サブツリー、右サブツリー、ルート ノードです。具体的な実装では、左のサブツリーと右のサブツリーを再帰的に走査し、最終的にルート ノードの値を出力する必要があります。

以下は Python コードの実装です:

def postorderTraversal(root: TreeNode):
    if root is None:
        return []
    res = []
    res += postorderTraversal(root.left)
    res += postorderTraversal(root.right)
    res.append(root.val)
    return res

概要

Python では、バイナリ ツリー トラバーサルを使用すると、前順序、中間順序、後順序を実現できます。再帰による順序トラバーサル。再帰のほかに、スタックや幅優先検索などの手法を使用して実装することもできます。バイナリツリートラバーサルの方法をマスターすると、日々のプログラミング作業に非常に役立ちます。

以上がPython を使用してバイナリ ツリー トラバーサルを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。