本記事は、ソフトバンクパブリッシングから発行されている「」を参考にPythonでアルゴリズムとデータ構造について学習していきます。
今回は、データ構造として木構造の一種である二分木（Binary Tree）について学んでいきます。
木構造とは
木構造（Tree Structure）とは、あるもの同士の階層関係を表現するデータ構造になります。
身近なところで木構造の概念が使われているのが、インターネットで使われるURLです。
例えば"www.google.com"というFQDNについては、".（ドット）"というルートドメインが"com"の後ろに隠れています。
ルートドメインを根として、その下位に"com"というトップレベルドメインが存在します。
また"com"ドメインの下位に"google"というドメインが存在し、その下位に"www"というホスト名のサーバがいるという階層関係になっています。
二分木とは
二分木（Binary Tree）とは、以下の条件を満たすものとして定義されます。
- 子を持たない
- 左の子のみを持つ
- 右の子のみを持つ
- 左右両方に子を持つ
今回は以下のような二分木を作成してみます。
木のなぞり
木構造の中のデータをひとつ残らず調べる為によく利用されるなぞり（Traverse）があります。
このなぞりには、行きがけ順（Preorder）、通りがけ順（Inorder）および帰りがけ順（Postorder）の3つがあります。
行きがけ順
- 根に立ち寄る
- 左部分木をなぞる
- 右部分木をなぞる
通りがけ順
- 左部分木をなぞる
- 根に立ち寄る
- 右部分木をなぞる
帰りがけ順
- 左部分木をなぞる
- 右部分木をなぞる
- 根に立ち寄る
なお、上記のなぞりは再帰呼び出し（Recursive Call）で実現します。
Pythonで二分木を作ってみる
それでは、Pythonで二分木を実装してみます。
# binary_tree.py
class Node:
def __init__(self, label):
self.label = label
self.left = None
self.right = None
def preorder(node):
if node == None:
return
print(node.label)
preorder(node.left)
preorder(node.right)
def inorder(node):
if node == None:
return
inorder(node.left)
print(node.label)
inorder(node.right)
def postorder(node):
if node == None:
return
postorder(node.left)
postorder(node.right)
print(node.label)
root = Node('A')
root.left = Node('B')
root.right = Node('H')
root.left.left = Node('C')
root.left.right = Node('D')
root.left.right.left = Node('E')
root.left.right.right = Node('F')
root.left.right.left.left = Node('G')
print('preorder...')
preorder(root)
print()
print('inorder...')
inorder(root)
print()
print('postorder...')
postorder(root)
動作確認
それでは上記で作成したスクリプトを実行してみます。
> python binary_tree.py preorder... A B C D E G F H inorder... C B G E D F A H postorder... C G E F D B H A
なぞりの方法によって、どこで根に立ち寄るかが異なるため、出力される結果も違ってきます。
参考書籍
定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)
