検索
ホームページバックエンド開発Python チュートリアルPythonでバイナリツリーを実装する方法
Pythonでバイナリツリーを実装する方法
WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB
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之Seaborn（数据可视化）详细讲解Python之Seaborn（数据可视化）Apr 21, 2022 pm 06:08 PM

本篇文章给大家带来了关于Python的相关知识，其中主要介绍了关于Seaborn的相关问题，包括了数据可视化处理的散点图、折线图、条形图等等内容，下面一起来看一下，希望对大家有帮助。

详细了解Python进程池与进程锁详细了解Python进程池与进程锁May 10, 2022 pm 06:11 PM

本篇文章给大家带来了关于Python的相关知识，其中主要介绍了关于进程池与进程锁的相关问题，包括进程池的创建模块，进程池函数等等内容，下面一起来看一下，希望对大家有帮助。

Python自动化实践之筛选简历Python自动化实践之筛选简历Jun 07, 2022 pm 06:59 PM

本篇文章给大家带来了关于Python的相关知识，其中主要介绍了关于简历筛选的相关问题，包括了定义 ReadDoc 类用以读取 word 文件以及定义 search_word 函数用以筛选的相关内容，下面一起来看一下，希望对大家有帮助。

归纳总结Python标准库归纳总结Python标准库May 03, 2022 am 09:00 AM

本篇文章给大家带来了关于Python的相关知识，其中主要介绍了关于标准库总结的相关问题，下面一起来看一下，希望对大家有帮助。

Python数据类型详解之字符串、数字Python数据类型详解之字符串、数字Apr 27, 2022 pm 07:27 PM

本篇文章给大家带来了关于Python的相关知识，其中主要介绍了关于数据类型之字符串、数字的相关问题，下面一起来看一下，希望对大家有帮助。

分享10款高效的VSCode插件，总有一款能够惊艳到你！！分享10款高效的VSCode插件，总有一款能够惊艳到你！！Mar 09, 2021 am 10:15 AM

VS Code的确是一款非常热门、有强大用户基础的一款开发工具。本文给大家介绍一下10款高效、好用的插件，能够让原本单薄的VS Code如虎添翼，开发效率顿时提升到一个新的阶段。

详细介绍python的numpy模块详细介绍python的numpy模块May 19, 2022 am 11:43 AM

本篇文章给大家带来了关于Python的相关知识，其中主要介绍了关于numpy模块的相关问题，Numpy是Numerical Python extensions的缩写，字面意思是Python数值计算扩展，下面一起来看一下，希望对大家有帮助。

python中文是什么意思python中文是什么意思Jun 24, 2019 pm 02:22 PM

pythn的中文意思是巨蟒、蟒蛇。1989年圣诞节期间，Guido van Rossum在家闲的没事干，为了跟朋友庆祝圣诞节，决定发明一种全新的脚本语言。他很喜欢一个肥皂剧叫Monty Python，所以便把这门语言叫做python。

See all articles

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

AI Hentai Generator

AI Hentai Generator

AIヘンタイを無料で生成します。

もっと見る

人気の記事

R.E.P.O.説明されたエネルギー結晶と彼らが何をするか（黄色のクリスタル）
3週間前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最高のグラフィック設定
3週間前By尊渡假赌尊渡假赌尊渡假赌
アサシンのクリードシャドウズ：シーシェルリドルソリューション
1週間前ByDDD
R.E.P.O.誰も聞こえない場合はオーディオを修正する方法
3週間前By尊渡假赌尊渡假赌尊渡假赌
Atomfallのクレーンコントロールキーカードを見つける場所
1週間前ByDDD
もっと見る

ホットツール

ドリームウィーバー CS6

ドリームウィーバー CS6

ビジュアル Web 開発ツール

MantisBT

MantisBT

Mantis は、製品の欠陥追跡を支援するために設計された、導入が簡単な Web ベースの欠陥追跡ツールです。 PHP、MySQL、Web サーバーが必要です。デモおよびホスティング サービスをチェックしてください。

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

強力な PHP 統合開発環境

メモ帳++7.3.1

メモ帳++7.3.1

使いやすく無料のコードエディター

DVWA

DVWA

Damn Vulnerable Web App (DVWA) は、非常に脆弱な PHP/MySQL Web アプリケーションです。その主な目的は、セキュリティ専門家が法的環境でスキルとツールをテストするのに役立ち、Web 開発者が Web アプリケーションを保護するプロセスをより深く理解できるようにし、教師/生徒が教室環境で Web アプリケーションを教え/学習できるようにすることです。安全。 DVWA の目標は、シンプルでわかりやすいインターフェイスを通じて、さまざまな難易度で最も一般的な Web 脆弱性のいくつかを実践することです。このソフトウェアは、

もっと見る

ホットトピック

Gmailメールのログイン入り口はどこですか？
7444
15
CakePHP チュートリアル
1371
52
Steamのアカウント名の形式は何ですか
76
11
Win11 Activation Key Permanent
38
19
NYTの接続はヒントと回答です
9
6
もっと見る