今回は、このアルゴリズムを使って、二分木の全ノードの和を求めることにします。
PythonのLevel Order Binary Tree Traversalについては既に説明しました。
How to find sum of all nodes in binary tree?
二分木の全ノードの和を求めるには、二分木の各ノードを走査して、その和を求めます。
この記事では、レベルオーダ木探索アルゴリズムの改良版を使って、全ノードの和を求めることにします。
この作業では、和を保持する変数を保持し、各ノードを処理した後、その値を和に追加することにします。
例えば、以下の二分木の要素の和は150です。
from queue import Queue
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 sumOfNodes(root):
if root is None:
return 0
Q = Queue()
Q.put(root)
current_sum = 0
while not Q.empty():
node = Q.get()
if node is None:
continue
current_sum = current_sum + node.data
Q.put(node.leftChild)
Q.put(node.rightChild)
return current_sum
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 sum of all the elements of the binary tree.")
print(sumOfNodes(root))
|
二分木の全ノードの総和を求めるアルゴリズム
前述したように、レベルオーダーの木探索のアルゴリズムを使って、二分木の全要素の和を求めるアルゴリズムを定式化します。
このアルゴリズムは以下のように定式化できる。
このアルゴリズムは二分木の根を入力とし、全要素の和を出力として与える。
- ルートが空であれば、リターンします。
-
- Qを待ち行列とします。
-
- 総和を0に初期化します。
- Qにrootを挿入します。
- Qからノードを取り出す。
-
- そのノードが空の場合、10に進む。そうでなければ、7に進む。
-
- ノードに含まれる要素をsumに加える。
-
- ノードの左の子をQに挿入します。
- ノードの右の子をQに挿入します。
- Qが空であるかどうかを調べる。Qが空でなければ、5.に進む。
Pythonによるアルゴリズムの実装
これまで説明したように、Pythonでアルゴリズムを実装し、上図のバイナリツリー上で実行します。
Printing the sum of all the elements of the binary tree.
150 |
結果は以下の通りです。
この記事もチェック：Pythonでのバランスバイナリーツリー(平衡木)の実装について解説する
まとめ
今回は、2分木の全要素の和を求めるアルゴリズムについて説明しました。
Pythonで様々なアルゴリズムを実装するための記事を今後も続けていきます。