Engineering Note

プログラミングなどの技術的なメモ

二分木 (Pythonによるアルゴリズムとデータ構造)

binary tree

本記事は、ソフトバンクパブリッシングから発行されている「定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)」を参考にPythonアルゴリズムとデータ構造について学習していきます。

今回は、データ構造として木構造の一種である二分木(Binary Tree)について学んでいきます。

 

 

木構造とは

木構造(Tree Structure)とは、あるもの同士の階層関係を表現するデータ構造になります。

身近なところで木構造の概念が使われているのが、インターネットで使われるURLです。

例えば"www.google.com"というFQDNについては、".(ドット)"というルートドメインが"com"の後ろに隠れています。

ルートドメインを根として、その下位に"com"というトップレベルドメインが存在します。

また"com"ドメインの下位に"google"というドメインが存在し、その下位に"www"というホスト名のサーバがいるという階層関係になっています。

 

domain

 

二分木とは

二分木(Binary Tree)とは、以下の条件を満たすものとして定義されます。

  • 子を持たない
  • 左の子のみを持つ
  • 右の子のみを持つ
  • 左右両方に子を持つ

今回は以下のような二分木を作成してみます。

 

node

 

木のなぞり

木構造の中のデータをひとつ残らず調べる為によく利用されるなぞり(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)