アルゴリズムクイックリファレンス 第2版

5.5

 二分探索木

■

145

BST

で予期される最後のロジックは、その内容を整列順にイテレーションする

機能だ。この機能は、ハッシュ表では歯が立たない。そのために

BinaryTree

と

BinaryNode

に必要な変更を例5-17に示す。

例

5-17

 間順走査のサポート

＊

1

class BinaryTree:

def __iter__(self):

"""

木の要素を間順走査

"""

if self.root:

return self.root.inorder()

class BinaryNode:

def inorder(self):

"""

与えられた接点を根とする木の間順走査

"""

if self.left:

for n in self.left.inorder():

yield n

yield self.value

if self.right:

for n in self.right.inorder():

yield n

この実装を使って、

BinaryTree

の値を整列順に出力できる。例5-18は、

10

個の

整数を（降順に）空の二分木に追加して、整列順に出力する。

例

5-18

 二分木の値によるイテレーション

bt = BinaryTree()

for i in range(10, 0, -1):

bt.add(i)

for v in bt:

print (v)

＊1 訳注：ここで間順走査（in order traversal）という用語を説明せずに用いているが、これは

深さ優先探

索

を行う際の戦略の ...