この記事では、バイナリツリーとは何か、そしてバイナリツリーデータ構造の背後にある基本的な概念について学びます。
また、Pythonのクラスを使ってバイナリツリーを実装します。
この記事もチェック：PythonでMax Heapデータ構造を実装する方法
バイナリーツリーとは
バイナリツリーとは、親オブジェクトが存在し、各オブジェクトが0個、1個、または2個の子を持つことができるデータ構造です。
一般にオブジェクトをノードと呼び、各ノードはデータフィールド、左の子への参照、右の子への参照で構成されます。
class BinaryTreeNode:
def __init__(self, data):
self.data = data
self.leftChild = None
self.rightChild=None
|
上の構造からわかるように、ノードはそれ自身のデータを持ち、また、左側と右側の2つのノードへの参照を持つことになる。
この構造を実装するには、クラスを定義し、データに値を割り当て、左の子と右の子への参照を割り当てればよい。
class BinaryTreeNode:
def __init__(self, data):
self.data = data
self.leftChild = None
self.rightChild = None
a1=BinaryTreeNode(10)
a2=BinaryTreeNode(15)
a3=BinaryTreeNode(20)
a4=BinaryTreeNode(60)
a5=BinaryTreeNode(14)
a6=BinaryTreeNode(25)
a7=BinaryTreeNode(6)
a1.leftChild=a2
a1.rightChild=a3
a2.leftChild=a4
a2.rightChild=a5
a3.leftChild=a6
a3.rightChild=a7
print("Root Node is:")
print(a1.data)
print("left child of node is:")
print(a1.leftChild.data)
print("right child of node is:")
print(a1.rightChild.data)
print("Node is:")
print(a2.data)
print("left child of node is:")
print(a2.leftChild.data)
print("right child of node is:")
print(a2.rightChild.data)
print("Node is:")
print(a3.data)
print("left child of node is:")
print(a3.leftChild.data)
print("right child of node is:")
print(a3.rightChild.data)
print("Node is:")
print(a4.data)
print("left child of node is:")
print(a4.leftChild)
print("right child of node is:")
print(a4.rightChild)
print("Node is:")
print(a5.data)
print("left child of node is:")
print(a5.leftChild)
print("right child of node is:")
print(a5.rightChild)
print("Node is:")
print(a6.data)
print("left child of node is:")
print(a6.leftChild)
print("right child of node is:")
print(a6.rightChild)
print("Node is:")
print(a7.data)
print("left child of node is:")
print(a7.leftChild)
print("right child of node is:")
print(a7.rightChild)
|
ここでは、コンストラクタはデータの値を入力として受け取り、 BinaryTreeNode 型のオブジェクトを生成し、与えられた入力と等しいデータフィールドを初期化し、左の子と右の子の参照を None に初期化します。
この記事もチェック：Pythonでバイナリツリーのノードを削除する方法
二分木の基本的な専門用語
それでは、二分木を例にとって、それに関連する用語を見てみましょう。
次のような二分木が与えられたとします。
Root Node is:
10left child of node is:
15right child of node is:
20Node is:
15left child of node is:
60right child of node is:
14Node is:
20left child of node is:
25right child of node is:
6Node is:
60left child of node is:
Noneright child of node is:
NoneNode is:
14left child of node is:
Noneright child of node is:
NoneNode is:
25left child of node is:
Noneright child of node is:
NoneNode is:
6left child of node is:
Noneright child of node is:
None |
- ルートノード。2分木の最上位ノードをルート・ノードと呼ぶ。木が作られるときに最初に作られるノードです。上記の例では、10がルートノードです。
- 親ノード。親ノード：ノードの親は、leftChild 参照または rightChild 参照が現在のノードを指しているノードであ る。例えば、10は15の親ノードです。
- 子ノード。子ノード：親ノードが指しているノードを子ノードと呼ぶ。子ノード：親ノードが指しているノードを子ノードと呼ぶ。
- エッジ: エッジは、ツリー内の任意の 2 つのノードを接続するリンクです。
- 内部ノード。内部ノード：内部ノードは、少なくとも 1 つの子ノードを持つノードです。この例では、データ10,15,20を含むノードが内部ノードです。
- リーフノードまたは外部ノード。バイナリツリーのノードで、子ノードを持たない。leftChildとrightChildはともにNoneを参照します。上の例では、データ 60, 14, 25, 6 を持つノードが、リーフノードまたは外部ノードです。
Pythonでバイナリツリーを実装する
では、上記の例で示された二分木を以下のコードで実装してみましょう。
結果は以下の通りです。
上記のコードでは、まず例で定義した BinaryTreeNode クラスのオブジェクトを生成しています。
次に、ツリーのルートを指定し、ルート・ノードに子ノードを追加し、さらにそれを繰り返す。
そして、各ノードのデータとその子ノードのデータを出力しています。
この記事もチェック：Pythonでのバランスバイナリーツリー(平衡木)の実装について解説する
まとめ
この記事では、バイナリツリーの背後にある理論的な概念を見て、次にその概念に基づいてバイナリツリーを実装しました。
今後も有益なチュートリアルをお届けします。
それでは、よいお年を