Pythonでバイナリツリーを実装する方法-Python チュートリアル-php.cn

ホームページ

バックエンド開発

Python チュートリアル

Pythonでバイナリツリーを実装する方法

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB

May 03, 2023 am 09:16 AM

python

Python によるバイナリツリーの実装

Pythonでバイナリツリーを実装する方法

Python は、バイナリツリーノードクラスを定義することで、オブジェクト指向プログラミングを使用してバイナリツリーを実装できます。各ノードには、データ要素、左右の子ノードポインター、およびノードの挿入、ノードの検索、ノードの削除などのいくつかの操作メソッドが含まれています。

以下は、単純なバイナリツリーの実装例です:

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

    def insert(self, data):
        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data

    def find(self, data):
        if data < self.data:
            if self.left is None:
                return str(data) + " Not Found"
            return self.left.find(data)
        elif data > self.data:
            if self.right is None:
                return str(data) + " Not Found"
            return self.right.find(data)
        else:
            return str(self.data) + " is found"

    def inorder_traversal(self, root):
        res = []
        if root:
            res = self.inorder_traversal(root.left)
            res.append(root.data)
            res = res + self.inorder_traversal(root.right)
        return res

上記のコードでは、Node クラスは、データ要素データと左右の子ノードポインターを含むノードを定義します。そしてそのとおりです。 insert メソッドはバイナリツリーにノードを挿入するために使用され、find メソッドはバイナリツリーに特定のノードが存在するかどうかを確認するために使用され、inorder_traversal メソッドはバイナリツリーの順序トラバーサルを実行するために使用されます。

この Node クラスを使用してバイナリツリーを作成する方法は次のとおりです:

root = Node(50)
root.insert(30)
root.insert(20)
root.insert(40)
root.insert(70)
root.insert(60)
root.insert(80)

# 查找节点

print(root.find(70)) # Output: 70 is found
print(root.find(90)) # Output: 90 Not Found

# 中序遍历
print(root.inorder_traversal(root)) # Output: [20, 30, 40, 50, 60, 70, 80]

上記のコードでは、最初にルートノード root が作成され、次に、insert メソッドを使用して、ノードをツリーに追加し、最後に find メソッドを使用してノードを見つけ、inorder_traversal メソッドを使用してバイナリツリーの順序トラバーサルを実行します。

二分木には、挿入、検索、および走査の方法に加えて、ノードの削除、二分探索木であるかどうかの決定、木の深さの計算などの他の操作方法もあります。以下は、もう少し完全なバイナリツリーのサンプルコードです:

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

    def insert(self, data):
        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data

    def find(self, data):
        if data < self.data:
            if self.left is None:
                return None
            return self.left.find(data)
        elif data > self.data:
            if self.right is None:
                return None
            return self.right.find(data)
        else:
            return self

    def delete(self, data):
        if self is None:
            return self

        if data < self.data:
            self.left = self.left.delete(data)
        elif data > self.data:
            self.right = self.right.delete(data)
        else:
            if self.left is None:
                temp = self.right
                self = None
                return temp
            elif self.right is None:
                temp = self.left
                self = None
                return temp
            temp = self.right.minimum()
            self.data = temp.data
            self.right = self.right.delete(temp.data)
        return self

    def minimum(self):
        if self.left is None:
            return self
        return self.left.minimum()

    def is_bst(self):
        if self.left:
            if self.left.data > self.data or not self.left.is_bst():
                return False

        if self.right:
            if self.right.data < self.data or not self.right.is_bst():
                return False

        return True

    def height(self, node):
        if node is None:
            return 0

        left_height = self.height(node.left)
        right_height = self.height(node.right)

        return max(left_height, right_height) + 1

    def inorder_traversal(self, root):
        res = []
        if root:
            res = self.inorder_traversal(root.left)
            res.append(root.data)
            res = res + self.inorder_traversal(root.right)
        return res

この例では、指定したノードを削除するための delete メソッド、ツリー内の最小のノードを見つけるための minimum メソッド、is_bst メソッドを追加しました。現在のツリーが二分探索ツリーであるかどうかを判断するには、高さ方法を使用してツリーの深さを計算します。

次のコードを使用して、新しいメソッドをテストできます:

# 创建二叉树
root = Node(50)
root.insert(30)
root.insert(20)
root.insert(40)
root.insert(70)
root.insert(60)
root.insert(80)

# 删除节点
print("Deleting node 20:")
root.delete(20)
print(root.inorder_traversal(root))

# 判断是否为二叉搜索树
print("Is it a BST?:", root.is_bst())

# 计算树的深度
print("Tree height:", root.height(root))

この方法で、比較的完全なバイナリツリーの実装が完了し、Python でオブジェクト指向プログラミングを使用する方法も示しました。データ構造を実装するためのアイデア。

最後に、完全なバイナリツリークラス実装コードが添付されます:

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

    def insert(self, data):
        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data

    def find(self, data):
        if data < self.data:
            if self.left is None:
                return None
            return self.left.find(data)
        elif data > self.data:
            if self.right is None:
                return None
            return self.right.find(data)
        else:
            return self

    def delete(self, data):
        if self is None:
            return self

        if data < self.data:
            self.left = self.left.delete(data)
        elif data > self.data:
            self.right = self.right.delete(data)
        else:
            if self.left is None:
                temp = self.right
                self = None
                return temp
            elif self.right is None:
                temp = self.left
                self = None
                return temp
            temp = self.right.minimum()
            self.data = temp.data
            self.right = self.right.delete(temp.data)
        return self

    def minimum(self):
        if self.left is None:
            return self
        return self.left.minimum()

    def is_bst(self):
        if self.left:
            if self.left.data > self.data or not self.left.is_bst():
                return False

        if self.right:
            if self.right.data < self.data or not self.right.is_bst():
                return False

        return True

    def height(self, node):
        if node is None:
            return 0

        left_height = self.height(node.left)
        right_height = self.height(node.right)

        return max(left_height, right_height) + 1

    def inorder_traversal(self, root):
        res = []
        if root:
            res = self.inorder_traversal(root.left)
            res.append(root.data)
            res = res + self.inorder_traversal(root.right)
        return res

if __name__ == '__main__':
    # 创建二叉树
    root = Node(50)
    root.insert(30)
    root.insert(20)
    root.insert(40)
    root.insert(70)
    root.insert(60)
    root.insert(80)

    # 删除节点
    print("Deleting node 20:")
    root.delete(20)
    print(root.inorder_traversal(root))

    # 判断是否为二叉搜索树
    print("Is it a BST?:", root.is_bst())

    # 计算树的深度
    print("Tree height:", root.height(root))

コードを実行すると、次の出力が得られます:

ノード 20 の削除 :
[30, 40, 50, 60, 70, 80]
Is it a BST?: True
Tree height: 3

この例挿入と検索、削除、トラバース、二分探索木かどうかの判断、木の深さの計算などが含まれます。

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

声明

この記事は亿速云で複製されています。侵害がある場合は、admin@php.cn までご連絡ください。

リストと配列の選択は、大規模なデータセットを扱うPythonアプリケーションの全体的なパフォーマンスにどのように影響しますか？May 03, 2025 am 12:11 AM

forhandlinglaredataSetsinpython、usenumpyArrays forbetterperformance.1）numpyarraysarememory-effictientandfasterfornumericaloperations.2）nusinnnnedarytypeconversions.3）レバレッジベクトル化は、測定済みのマネージメーシェイメージーウェイズデイタイです

Pythonのリストと配列にメモリがどのように割り当てられるかを説明します。May 03, 2025 am 12:10 AM

inpython、listsusedynamicmemoryallocation with allocation、whilenumpyArraysalocatefixedmemory.1）listsallocatemorememorythanneededededinitivative.2）numpyArrayasallocateexactmemoryforements、rededicablebutlessflexibilityを提供します。

Pythonアレイ内の要素のデータ型をどのように指定しますか？May 03, 2025 am 12:06 AM

inpython、youcanspecthedatatypeyfelemeremodelernspant.1）usenpynernrump.1）usenpynerp.dloatp.ploatm64、フォーマーpreciscontrolatatypes。

Numpyとは何ですか、そしてなぜPythonの数値コンピューティングにとって重要なのですか？May 03, 2025 am 12:03 AM

numpyisessentialfornumericalcomputinginpythonduetoitsspeed、memory efficiency、andcomprehensivematicalfunctions.1）それは、performsoperations.2）numpyArraysaremoremory-efficientthanpythonlists.3）Itofderangeofmathematicaloperty

「隣接するメモリ割り当て」の概念と、配列にとってその重要性について説明します。May 03, 2025 am 12:01 AM

contiguousMemoryAllocationisucial forArraysは、ForeffienceAndfastelementAccess.1）iteenablesConstantTimeAccess、O（1）、DuetodirectAddresscalculation.2）itemprovesefficiencyByAllowingMultiblementFechesperCacheLine.3）itimplifieMememm

Pythonリストをどのようにスライスしますか？May 02, 2025 am 12:14 AM

slicingapythonlistisdoneusingtheyntaxlist [start：stop：step] .hore'showitworks：1）startisthe indexofthefirstelementtoinclude.2）spotisthe indexofthefirmenttoeexclude.3）staptistheincrementbetbetinelements

Numpyアレイで実行できる一般的な操作は何ですか？May 02, 2025 am 12:09 AM

numpyallows forvariousoperationsonarrays：1）basicarithmeticlikeaddition、減算、乗算、および分割; 2）AdvancedperationssuchasmatrixMultiplication;

Pythonを使用したデータ分析では、配列はどのように使用されていますか？May 02, 2025 am 12:09 AM

Arraysinpython、特にnumpyandpandas、aresentialfordataanalysis、offeringspeedandeficiency.1）numpyarraysenable numpyarraysenable handling forlaredatasents andcomplexoperationslikemoverages.2）Pandasextendsnumpy'scapabivitieswithdataframesfortruc

See all articles