今回は、レベルオーダー木探索アルゴリズムを修正して、二分木の最大幅を求める。
バランス2分木に関する前回の記事では、2分木の高さを求めるアルゴリズムを定式化して実装しました。
また、Pythonでレベルオーダーの二分木探索のアルゴリズムも実装しました。
二分木の幅は？
二分木では、任意のレベルLに最大2L個のノードが存在することができます。
ノードがないため、どのレベルでも要素数が少なくなる可能性があります。
例えば、次の図の二分木は、1つのレベルに最大4つのノードが存在するので、最大幅は4です。
class BinaryTreeNode:
def __init__(self, data):
self.data = data
self.leftChild = None
self.rightChild = None
def insert(root, newValue):
# if binary search tree is empty, make a new node and declare it as root
if root is None:
root = BinaryTreeNode(newValue)
return root
# binary search tree is not empty, so we will insert it into the tree
# if newValue is less than value of data in root, add it to left subtree and proceed recursively
if newValue < root.data:
root.leftChild = insert(root.leftChild, newValue)
else:
# if newValue is greater than value of data in root, add it to right subtree and proceed recursively
root.rightChild = insert(root.rightChild, newValue)
return root
def width(root):
if root is None:
return 0
max_width = -1
current_width = 0
Q = [root, None]
while Q:
node = Q.pop(0)
if node is None:
if max_width < current_width:
max_width = current_width
current_width = 0
if not Q or Q[0] is None:
continue
Q.append(None)
else:
current_width = current_width + 1
Q.append(node.leftChild)
Q.append(node.rightChild)
return max_width
root = insert(None, 15)
insert(root, 10)
insert(root, 25)
insert(root, 6)
insert(root, 14)
insert(root, 20)
insert(root, 60)
print("Printing the maximum width of the binary tree.")
print(width(root))
|
How to find the maximum width of a binary tree?
レベルオーダー木探索アルゴリズムの改良版を使って、2分木の最大幅を求めることにします。
このアイデアは、各レベルの要素の数をどうにかして数え、その最大値を見つけることです。
このために、木における異なるレベルの要素を区切るプレースホルダーを使うことができる。
レベルオーダーのトラバーサルで使用するキューでは、あるレベルのすべての要素を挿入した後にプレースホルダーを挿入します。
こうすることで、プレースホルダに遭遇するたびに、木の1つのレベルが走査されたことがわかるので、幅を更新することができる。
二分木の最大幅を求めるアルゴリズム
キューにルートノードを挿入します。
その後、プレースホルダとして None オブジェクトを挿入します。
待ち行列でプレースホルダに出会うたびに、木の幅が更新され、Noneオブジェクトが待ち行列に押し込まれる。
二分木の幅を求めるアルゴリズムは、以下のように定式化できる。
このアルゴリズムは、二分木の根を入力とし、最大の幅を返す。
- ルートが空の場合、0を返す。
-
- maximum_tempta_width変数を-1に初期化します。
-
- current_tica_width変数を0に初期化します。
-
- Qを待ち行列とします。
-
- Qにrootを挿入します。
- 待ち行列にNoneを挿入します。
- Qからノードを取り出す。
- ノードがNoneの場合、9に進む。そうでなければ11に進む。
-
- Compare maximum_width and current counter_width. 両者の最大値をmaximum_widthに代入します。
-
- current_width to 0. Q is empty or First element of Q is None, Go to 14.
-
- current_widthを1つ増やす。
-
- ノードの左の子をQに挿入します。
- ノードの右の子をQに挿入します。
-
- Q が空であるかどうか調べる。Q が空でなければ 7 に進み、そうでなければ停止します。
Pythonによるアルゴリズムの実装
アルゴリズムの概要を理解したところで、Pythonでの実装を見てみましょう。
ここでは、上の画像で示される二分木を作成し、二分木の最大幅を計算しました。
Printing the maximum width of the binary tree.4 |
結果は以下の通りです。
まとめ
この記事では、二分木の最大幅を求めるアルゴリズムについて説明しました。
今後もPythonで様々なアルゴリズムを実装する記事を書いていきますのでお楽しみに。