Pythonで2分木を実装します。
2分木
二分木（binary tree; 二進木、バイナリツリー）は、データ構造の1つである。根付き木構造の中で、あるノード（節点 node）が持つ子の数が高々2であるものをいう。典型的には2つの子はそれぞれ「左」「右」と呼ばれる。
たとえば、二分探索や二分ヒープを実装するために使われる。
出典: フリー百科事典『ウィキペディア（Wikipedia）』
大きさ9、深さ3、根は値2を持つ 2分木。Wikipediaより。
ノードクラスの定義
木構造の中のノードを定義します。ノードは、値と左の子、右の子を持ちます。
class Node(object):
def __init__(self, value):
self.value = value
self.left = None
self.right = None
2分木クラスの定義
class BinaryTree(object):
def __init__(self, root):
self.root = Node(root)
これにより、例えば以下のような形で、2分木を定義できます。
tree = BinaryTree(1) tree.root.left = Node(2) tree.root.right = Node(3) tree.root.left.left = Node(4) tree.root.left.right = Node(5) tree.root.right.left = Node(6) tree.root.right.right = Node(7) tree.root.right.right.right = Node(8)
二分木を巡回する方法
行きがけ順、通りがけ順、帰りがけ順探索
二分木においてはあるノードとその子孫もまた二分木を構成する。これを部分木と呼ぶ。 従って二分木を部分木に分け、再帰を用いて探索する方法は自然である。
出典: フリー百科事典『ウィキペディア（Wikipedia）』
行きがけ順 (preorder)
行きがけ順 (preorder) は、根を調べてからそれにぶらさがる部分木を調べます。
2分木クラスのメソッドとして定義します。
def preorder_print(self, start, traversal):
"""Root -> Left -> Right"""
if start:
traversal += (str(start.value) + "-")
traversal = self.preorder_print(start.left, traversal)
traversal = self.preorder_print(start.right, traversal)
return traversal
上で定義した2分木で出力します。
print(tree.preorder_print(tree.root, '')) # 出力 1-2-4-5-3-6-7-8-
通りがけ順 (in-order)
通りがけ順 (in-order) では、片方の部分木を調べ、根を調べ、次いで反対の部分木を調べます。
2分木クラスのメソッドとして定義します。
def inorder_print(self, start, traversal):
"""Left -> Root -> Right """
if start:
traversal = self.inorder_print(start.left, traversal)
traversal += (str(start.value) + "-")
traversal = self.inorder_print(start.right, traversal)
return traversal
上で定義した2分木で出力します。
print(tree.inorder_print(tree.root, '')) # 出力 4-2-5-1-6-3-7-8-
帰りがけ順 (postorder)
帰りがけ順 (postorder) では、部分木を調べてからその根を調べます。
2分木クラスのメソッドとして定義します。
def postorder_print(self, start, traversal):
"""Left -> Right -> Root"""
if start:
traversal = self.postorder_print(start.left, traversal)
traversal = self.postorder_print(start.right, traversal)
traversal += (str(start.value) + '-')
return traversal
上で定義した2分木で出力します。
print(tree.postorder_print(tree.root, '')) # 出力 4-5-2-6-8-7-3-1-
幅優先探索
深さ優先探索と対照的に、未だに訪れていないノードを、根に近い方から探索する。
出典: フリー百科事典『ウィキペディア（Wikipedia）』
キューを用いることで幅優先探索を実装します。
まずはキューを定義します。
class Queue(object):
def __init__(self):
self.items = []
def enqueue(self, item):
self.items.insert(0, item)
def dequeue(self):
if not self.is_empty():
return self.items.pop()
def is_empty(self):
return len(self.items) == 0
def peek(self):
if not self.is_empty():
return self.items[-1].value
def __len__(self):
return self.size()
def size(self):
return len(self.items)
幅優先探索を 2分木クラスのメソッドとして実装します。
def levelorder_print(self, start):
if start is None:
return
queue = Queue()
queue.enqueue(start)
traversal = ''
while len(queue) > 0:
traversal += str(queue.peek()) + "-"
node = queue.dequeue()
if node.left:
queue.enqueue(node.left)
if node.right:
queue.enqueue(node.right)
return traversal
上で定義した2分木で出力します。
print(tree.levelorder_print(tree.root)) # 出力 1-2-3-4-5-6-7-8-
葉に近いほうからの幅優先探索
逆に、葉に近いほうからの幅優先探索を定義します。
スタックとキューを用いて実装します。
スタックを定義します。
class Stack(object):
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
if not self.is_empty():
return self.items.pop()
def is_empty(self):
return len(self.items) == 0
def peek(self):
if not self.is_empty():
return self.items[-1]
def size(self):
return len(self.items)
def __len__(self):
return self.size()
葉に近いほうからの幅優先探索を 2分木クラスのメソッドとして実装します。
def reverse_levelorder_print(self, start):
if start is None:
return
queue = Queue()
stack = Stack()
queue.enqueue(start)
traversal = ''
while len(queue) > 0:
node = queue.dequeue()
stack.push(node)
if node.right:
queue.enqueue(node.right)
if node.left:
queue.enqueue(node.left)
while len(stack) > 0:
node = stack.pop()
traversal += str(node.value) + '-'
return traversal
上で定義した2分木で出力します。
print(tree.reverse_levelorder_print(tree.root)) # 出力 8-4-5-6-7-2-3-1-
2分木の高さ
2分木の高さを再帰的に巡回することで求めます。
2分木クラスのメソッドとして実装します。
def height(self, node):
if node is None:
return -1
left_height = self.height(node.left)
right_height = self.height(node.right)
return 1 + max(left_height, right_height)
上で定義した2分木で出力します。
print(tree.height(tree.root)) # 出力 3
ノードの数
2分木のノードの数を求めます。
スタックを用いてノードの数を求める
2分木クラスのメソッドとして実装します。
def size(self):
if self.root is None:
return 0
stack = Stack()
stack.push(self.root)
size = 1
while stack:
node = stack.pop()
if node.left:
size += 1
stack.push(node.left)
if node.right:
size += 1
stack.push(node.right)
return size
上で定義した2分木で出力します。
print(tree.size()) # 出力 8
再帰でノードの数を求める
2分木クラスのメソッドとして実装します。
def size_recursive(self, node):
if node is None:
return 0
return 1 + self.size_recursive(node.left) + self.size_recursive(node.right)
上で定義した2分木で出力します。
print(tree.size_recursive(tree.root)) # 出力 8