本記事は、ソフトバンクパブリッシングから発行されている「定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)」を参考に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
なぞりの方法によって、どこで根に立ち寄るかが異なるため、出力される結果も違ってきます。