Python でバイナリ ツリーを印刷する
この記事では、バイナリ ツリーとその使用方法について説明します。 また、Python を使用して印刷する方法についても説明します。
二分木の作業で使用される用語について学習します。 また、Python コードを使用したバイナリ ツリーの例も見ていきます。
Python のバイナリ ツリー
Python のバイナリ ツリーは、利用可能な最も効率的なデータ構造の 1つであり、実装も比較的簡単です。 二分木は、ルート ノードと 2つの子ノード (左と右) を持つツリー状のデータ構造です。
各ノードは、任意の数の子ノードを持つことができます。 この記事では、Python でバイナリ ツリーを作成してトラバースする方法について説明します。
ツリーに関連する用語について理解を深めましょう。
- ルート: 親を持たないツリーの最上位ノード。 すべての木には根が 1つあります。
- Edge: Edge は親子リンクです。
- リーフ: 子を持たないノード。 ツリーの最終ノード。 ツリーには複数のリーフ ノードがあります。
- サブツリー: ツリーはノードをルートとして使用します。
- 深さ: 深さは、ルートからノードまでの距離です。
- 高さ: ノードの高さは、サブツリーの最も深いノードまでの距離です。
- ツリーの高さ: ツリーの高さは最も高いノードであり、ルート ノードと同じ高さに対応します。
ツリーの走査順序
ツリーは、ルート ノードから始めて左右の子ノードにアクセスすることによってトラバースされます。 ノードが訪問される順序は、トラバーサル順序と呼ばれます。
インオーダー トラバーサル ツリー
二分木をたどる方法はいくつかあります。 最も一般的なのは、左、ルート、および右の子ノードを訪問する順序通りのトラバーサルです。
トラバーサル ツリーの予約注文
もう 1つの標準的なトラバーサルは、事前順序トラバーサルです。これは、最初にルート ノードにアクセスし、次に左の子、最後に右の子にアクセスします。
順序通りのトラバーサルは、各ノードを 1 回だけ訪問するため、バイナリ ツリー内のすべてのノードを訪問する最も効率的な方法です。 事前注文トラバーサルは、ルート ノードを 2 回呼び出すため、少し効率が悪くなります。
ただし、最初にルート ノードを変更し、次に左右の子ノードを変更するのは簡単であるため、トラバーサル中にツリーを変更する場合は、プレオーダー トラバーサルがよく使用されます。
Python での 順序通りのトラバーサル の構文と簡単な実装を次に示します。
def inorder(node):
if node is not None:
inorder(node.left)
print(node.val)
inorder(node.right)
というわけで、順番通りのトラバーサル方式を使いたいときのコーディング方法です。
そして、ここに予約注文のトラバーサルがあります：
def preorder(node):
if node is not None:
print(node.val)
preorder(node.left)
preorder(node.right)
ポストオーダー トラバーサル
左の子、右の子、そしてルートノードを訪問するポストオーダーでツリーをトラバースすることもできます。 ただし、ポストオーダー トラバーサルは、他の 2つのトラバーサルよりも効率が悪いため、あまり一般的ではありません。
レベルごとにツリー内のノードを訪問するレベル順トラバーサルなど、バイナリ ツリーをトラバースする方法は他にもあります。 ただし、この記事ではそのトラバーサルについては説明しません。
二分木をトラバースする方法を見たので、1つの二分木を作成し、Python を使用して出力する方法を見てみましょう。
Python でのバイナリ ツリーの実装
二分木とは何か、それに関連する用語は知っています。 二分木がどのように機能するかをよりよく理解するために、Python を使用して二分木を実装します。
-
ここでのクラスとなる二分木用のノードが必要です。 データ型を作成するため、左側と右側のアドレスとともにデータ ポイントを配置します。
そのようなデータ型はまだないので、必要な方法でデータ型を作成します。 というわけで、まずはクラスを作成します。
-
次に、クラスのコンストラクターを作成します。 そして、必要に応じてコンストラクターをクラスに渡します。
ツリーのデータを格納するためのパラメータ データも与えます。
-
dataパラメータにデータを取得するためにselfを使用します。 -
データがないとノードを作成できないためです。 データがない場合、ノードをどうするか?
データがなければ、左も右もありません。 論理的にはデータが必要であり、それがここでデータを使用している理由です。
ここで、ノードが必要になります。
- 左ノード
2.右のノード
以下のコードで実装します。
- 左ノード
-
Binary Tree を実装しました (以下のコード)。 左右のノードを作成し、それらを
Noneに設定しました。ノードが作成されるとき、それらは
Noneに似ているはずだからです。 ツリーはルートから始まるため、左右のデータはありません。 後でデータを追加します。次に、ツリーのオブジェクトをいくつか作成します。 クラス
binaryTreeNodeのオブジェクトを作成するには、変数を作成し、それをクラスbinaryTreeNode()に割り当てる必要があります。 -
class binaryTreeNode用に 3つのオブジェクトを作成しましたが、これらのオブジェクトは現在何にもリンクされていません。 したがって、オブジェクトを印刷して内容を確認する場合は、以下のコードに従います。 -
bnt1、bnt2、bnt3の 3つのオブジェクトを作成したので、ルートの左右にデータ ポイントを指定します。bnt1をルート、bnt2とbnt3をbnt1の左右とします。 -
この場合、バイナリ ツリーは次のようになります。 そして、これがコードの出力になります。
1 / \ / \ 2 3ここでルートは 1 です。左の部分は 2 で、右の部分は 3 です。次に、Python を使用して印刷し、どのように機能するかを確認します。
-
ルートを取得した後、ツリー全体を印刷したいだけです。 そのためには、メソッドを定義する必要があります。
そのコードをここにコピーして、そこに新しいコードを書くだけです。 これはバイナリ ツリーの一部であるため、既に作成されたコードを使用して新しいコードを作成する必要があります。
コード例:
class binaryTreeNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def printTree(root):
print(root.data)
print("L", root.left.data, end=": ")
print("R", root.right.data, end=": ")
bnt1 = binaryTreeNode(1)
bnt2 = binaryTreeNode(2)
bnt3 = binaryTreeNode(3)
bnt1.left = bnt2
bnt1.right = bnt3
bnt2.left = bnt1
bnt2.right = bnt3
bnt3.left = bnt1
bnt3.right = bnt2
メソッド def printTree(root) はルートを提供します。 ツリーのルートを取得すると、ノードを使用してツリー全体にアクセスできるためです。
メソッドを宣言した後、いくつかの条件を確認します。 上記のコードで def PrintTree(root) メソッドを見ることができます。
ルート 1、bnt1 を出力して、何が得られるか見てみましょう。
コード例:
print(bnt1.printTree())
出力：
1
L 2: R 3: None
出力は、ツリーに 2つのノード (左側のノードと右側のノード) が含まれていることを示しています。 左側のノードのデータは 2 で、右側のノードのデータは 3 です。
bnt2 と bnt3 を出力して、それらに含まれるデータ ポイントを確認することもできます。
Python を使用してバイナリ ツリー全体を出力する
これが二分木全体です。 これを実行して、Python の random ライブラリを使用して Python を使用してバイナリ ツリーを出力する方法について詳しく学ぶことができます。
import random
class BinaryTree:
def __init__(self, key):
self.key = key
self.right = None
self.left = None
def insert(self, key):
if self.key == key:
return
elif self.key < key:
if self.right is None:
self.right = BinaryTree(key)
else:
self.right.insert(key)
else: # self.key > key
if self.left is None:
self.left = BinaryTree(key)
else:
self.left.insert(key)
def display(self):
lines, *_ = self._display_aux()
for line in lines:
print(line)
def _display_aux(self):
"""Returns list of strings, width, height, and horizontal coordinate of the root."""
# No child.
if self.right is None and self.left is None:
line = "%s" % self.key
width = len(line)
height = 1
middle = width // 2
return [line], width, height, middle
# Only left child.
if self.right is None:
lines, n, p, x = self.left._display_aux()
s = "%s" % self.key
u = len(s)
first_line = (x + 1) * " " + (n - x - 1) * "_" + s
second_line = x * " " + "/" + (n - x - 1 + u) * " "
shifted_lines = [line + u * " " for line in lines]
return [first_line, second_line] + shifted_lines, n + u, p + 2, n + u // 2
# Only right child.
if self.left is None:
lines, n, p, x = self.right._display_aux()
s = "%s" % self.key
u = len(s)
first_line = s + x * "_" + (n - x) * " "
second_line = (u + x) * " " + "\\" + (n - x - 1) * " "
shifted_lines = [u * " " + line for line in lines]
return [first_line, second_line] + shifted_lines, n + u, p + 2, u // 2
# Two children.
left, n, p, x = self.left._display_aux()
right, m, q, y = self.right._display_aux()
s = "%s" % self.key
u = len(s)
first_line = (x + 1) * " " + (n - x - 1) * "_" + s + y * "_" + (m - y) * " "
second_line = (
x * " " + "/" + (n - x - 1 + u + y) * " " + "\\" + (m - y - 1) * " "
)
if p < q:
left += [n * " "] * (q - p)
elif q < p:
right += [m * " "] * (p - q)
zipped_lines = zip(left, right)
lines = [first_line, second_line] + [a + u * " " + b for a, b in zipped_lines]
return lines, n + m + u, max(p, q) + 2, n + u // 2
b = BinaryTree(100)
for _ in range(100):
b.insert(random.randint(50, 150))
b.display()
出力：
コードの出力は、実行するたびに変化し続けます。 これは、Python の random モジュールを使用しているためです。
この記事が、Python を使用してバイナリ ツリーを出力する方法を理解するのに役立つことを願っています。
My name is Abid Ullah, and I am a software engineer. I love writing articles on programming, and my favorite topics are Python, PHP, JavaScript, and Linux. I tend to provide solutions to people in programming problems through my articles. I believe that I can bring a lot to you with my skills, experience, and qualification in technical writing.
LinkedIn