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 サイトの他の関連記事を参照してください。
ホットAIツール
Undresser.AI Undress
リアルなヌード写真を作成する AI 搭載アプリ
AI Clothes Remover
写真から衣服を削除するオンライン AI ツール。
Undress AI Tool
脱衣画像を無料で
Clothoff.io
AI衣類リムーバー
AI Hentai Generator
AIヘンタイを無料で生成します。
人気の記事
ホットツール
メモ帳++7.3.1
使いやすく無料のコードエディター
SublimeText3 中国語版
中国語版、とても使いやすい
ゼンドスタジオ 13.0.1
強力な PHP 統合開発環境
ドリームウィーバー CS6
ビジュアル Web 開発ツール
SublimeText3 Mac版
神レベルのコード編集ソフト（SublimeText3）
ホットトピック
7549
15
1382
52
83
11
22
90
PHPおよびPython：コードの例と比較
Apr 15, 2025 am 12:07 AM
PHPとPythonには独自の利点と短所があり、選択はプロジェクトのニーズと個人的な好みに依存します。 1.PHPは、大規模なWebアプリケーションの迅速な開発とメンテナンスに適しています。 2。Pythonは、データサイエンスと機械学習の分野を支配しています。
CentosのPytorchのGPUサポートはどのようにサポートされていますか
Apr 14, 2025 pm 06:48 PM
Pytorch GPUアクセラレーションを有効にすることで、CentOSシステムでは、PytorchのCUDA、CUDNN、およびGPUバージョンのインストールが必要です。次の手順では、プロセスをガイドします。CUDAおよびCUDNNのインストールでは、CUDAバージョンの互換性が決定されます。NVIDIA-SMIコマンドを使用して、NVIDIAグラフィックスカードでサポートされているCUDAバージョンを表示します。たとえば、MX450グラフィックカードはCUDA11.1以上をサポートする場合があります。 cudatoolkitのダウンロードとインストール：nvidiacudatoolkitの公式Webサイトにアクセスし、グラフィックカードでサポートされている最高のCUDAバージョンに従って、対応するバージョンをダウンロードしてインストールします。 cudnnライブラリをインストールする：
Dockerの原則の詳細な説明
Apr 14, 2025 pm 11:57 PM
DockerはLinuxカーネル機能を使用して、効率的で孤立したアプリケーションランニング環境を提供します。その作業原則は次のとおりです。1。ミラーは、アプリケーションを実行するために必要なすべてを含む読み取り専用テンプレートとして使用されます。 2。ユニオンファイルシステム（UnionFS）は、違いを保存するだけで、スペースを節約し、高速化する複数のファイルシステムをスタックします。 3.デーモンはミラーとコンテナを管理し、クライアントはそれらをインタラクションに使用します。 4。名前空間とcgroupsは、コンテナの分離とリソースの制限を実装します。 5.複数のネットワークモードは、コンテナの相互接続をサポートします。これらのコア概念を理解することによってのみ、Dockerをよりよく利用できます。
Python vs. JavaScript：コミュニティ、ライブラリ、リソース
Apr 15, 2025 am 12:16 AM
PythonとJavaScriptには、コミュニティ、ライブラリ、リソースの観点から、独自の利点と短所があります。 1）Pythonコミュニティはフレンドリーで初心者に適していますが、フロントエンドの開発リソースはJavaScriptほど豊富ではありません。 2）Pythonはデータサイエンスおよび機械学習ライブラリで強力ですが、JavaScriptはフロントエンド開発ライブラリとフレームワークで優れています。 3）どちらも豊富な学習リソースを持っていますが、Pythonは公式文書から始めるのに適していますが、JavaScriptはMDNWebDocsにより優れています。選択は、プロジェクトのニーズと個人的な関心に基づいている必要があります。
ミニオペンCentosの互換性
Apr 14, 2025 pm 05:45 PM
MINIOオブジェクトストレージ：CENTOSシステムの下での高性能展開Minioは、Amazons3と互換性のあるGO言語に基づいて開発された高性能の分散オブジェクトストレージシステムです。 Java、Python、JavaScript、Goなど、さまざまなクライアント言語をサポートしています。この記事では、CentosシステムへのMinioのインストールと互換性を簡単に紹介します。 Centosバージョンの互換性Minioは、Centos7.9を含むがこれらに限定されない複数のCentosバージョンで検証されています。
CentosでPytorchの分散トレーニングを操作する方法
Apr 14, 2025 pm 06:36 PM
Pytorchの分散トレーニングでは、Centosシステムでトレーニングには次の手順が必要です。Pytorchのインストール：PythonとPipがCentosシステムにインストールされていることです。 CUDAバージョンに応じて、Pytorchの公式Webサイトから適切なインストールコマンドを入手してください。 CPUのみのトレーニングには、次のコマンドを使用できます。PipinstalltorchtorchtorchvisionTorchaudioGPUサポートが必要な場合は、CUDAとCUDNNの対応するバージョンがインストールされ、インストールに対応するPytorchバージョンを使用してください。分散環境構成：分散トレーニングには、通常、複数のマシンまたは単一マシンの複数GPUが必要です。場所
CentosでPytorchバージョンを選択する方法
Apr 14, 2025 pm 06:51 PM
PytorchをCentosシステムにインストールする場合、適切なバージョンを慎重に選択し、次の重要な要因を検討する必要があります。1。システム環境互換性：オペレーティングシステム：Centos7以上を使用することをお勧めします。 Cuda and Cudnn：PytorchバージョンとCudaバージョンは密接に関連しています。たとえば、pytorch1.9.0にはcuda11.1が必要ですが、pytorch2.0.1にはcuda11.3が必要です。 CUDNNバージョンは、CUDAバージョンとも一致する必要があります。 Pytorchバージョンを選択する前に、互換性のあるCUDAおよびCUDNNバージョンがインストールされていることを確認してください。 Pythonバージョン：Pytorch公式支店
NginxをCentosにインストールする方法
Apr 14, 2025 pm 08:06 PM
NGINXのインストールをインストールするには、次の手順に従う必要があります。開発ツール、PCRE-Devel、OpenSSL-Develなどの依存関係のインストール。 nginxソースコードパッケージをダウンロードし、それを解凍してコンパイルしてインストールし、/usr/local/nginxとしてインストールパスを指定します。 nginxユーザーとユーザーグループを作成し、アクセス許可を設定します。構成ファイルnginx.confを変更し、リスニングポートとドメイン名/IPアドレスを構成します。 nginxサービスを開始します。依存関係の問題、ポート競合、構成ファイルエラーなど、一般的なエラーに注意する必要があります。パフォーマンスの最適化は、キャッシュをオンにしたり、ワーカープロセスの数を調整するなど、特定の状況に応じて調整する必要があります。
