Pythonでさまざまなデータ構造（２）
こんにちは。前回は連結リスト構造とそれに関連したデータ構造をPythonでプログラムを書き直してみました。
今回は木構造に関係したデータ構造をPythonのプログラムにしてみたいと思います。
木構造の復習
木構造の説明のページは、次のものがありました。
https://joho-ka.mints.ne.jp/binary-tree01
二分探索木については、次の３ページで説明していました。
これらをPythonに直してみます。
MyTreeNodeクラス
木構造のノードを定義するクラスです。プログラムは次のようになります。
class MyTreeNode:
def __init__( self, element = None , left = None , right = None ):
self.__element = element
self.__left = left
self.__right = right
def get_element( self ):
return self.__element
def set_element( self, element ):
self.__element = element
def get_left( self ):
return self.__left
def get_right( self ):
return self.__right
def set_left( self, left ):
self.__left = left
def set_right( self, right ):
self.__right = right
基本的にはJavaで書いたものと同じです。
MyBinatySearchTreeクラス
二分探索木を定義するクラスです。まずは、プログラムです。
import mytreenode
import mystack
import myqueue
import random
class MyBinarySearchTree:
def __init__( self ):
self.__root = None
def find( self, element ):
node = self.__root
while node != None and node.get_element() != element:
if element < node.get_element():
node = node.get_left()
else:
node = node.get_right()
return node
def insert( self, element ):
if self.__root == None:
tmp = mytreenode.MyTreeNode( element )
self.__root = tmp
return
self.__insert( element, self.__root )
def __insert( self, element, node ):
if element < node.get_element():
if node.get_left() == None:
tmp = mytreenode.MyTreeNode( element )
node.set_left( tmp )
return
else:
self.__insert( element, node.get_left() )
return
else:
if node.get_right() == None:
tmp = mytreenode.MyTreeNode( element )
node.set_right( tmp )
return
else:
self.__insert( element, node.get_right() )
return
def delete( self, element ):
if not self.find( element ):
return False
parent = None
child = self.__root
while child.get_element() != element:
if element < child.get_element():
parent = child
child = child.get_left()
else:
parent = child
child = child.get_right()
if child.get_left() == None and child.get_right() == None:
if child == self.__root:
self.__root = None
return True
if child == parent.get_left():
parent.set_left( None )
else:
parent.set_right( None )
return True
if child.get_left() == None or child.get_right() == None:
if child.get_left() == None:
node = child.get_right()
else:
node = child.get_left()
if child == self.__root:
self.__root = node
elif child == parent.get_left():
parent.set_left( node )
else:
parent.set_right( node )
return True
if child == self.__root:
self.__root = child.get_left()
elif parent.get_left() == child:
parent.set_left( child.get_left() )
else:
parent.set_right( child.get_left() )
node = child.get_right()
child = child.get_left()
while child.get_right() != None:
child = child.get_right()
child.set_right( node )
return True
def print_pre_order( self ):
print( 'PreOrder : ' + self.__pre_order( self.__root ) )
def __pre_order( self, node ):
result = ' ' + str( node.get_element() )
if node.get_left() != None:
result += self.__pre_order( node.get_left() )
if node.get_right() != None:
result += self.__pre_order( node.get_right() )
return result
def print_in_order( self ):
print( 'InOrder : ' + self.__in_order( self.__root ) )
def __in_order( self, node ):
result = ''
if node.get_left() != None:
result += self.__in_order( node.get_left() )
result += ' ' + str( node.get_element() )
if node.get_right() != None:
result += self.__in_order( node.get_right() )
return result
def print_post_order( self ):
print( 'PostOrder : ' + self.__post_order( self.__root ) )
def __post_order( self, node ):
result = ''
if node.get_left() != None:
result += self.__post_order( node.get_left() )
if node.get_right() != None:
result += self.__post_order( node.get_right() )
result += ' ' + str( node.get_element() )
return result
def print_depth_first( self ):
print( 'DepthFirstSearch : ' + self.__depth_first( self.__root ) )
def __depth_first( self, node ):
stack = mystack.MyStack()
result = ''
stack.push( node )
while not stack.empty():
tmp = stack.pop()
result += ' ' + str( tmp.get_element() )
if tmp.get_right() != None:
stack.push( tmp.get_right() )
if tmp.get_left() != None:
stack.push( tmp.get_left() )
return result
def print_breadth_first( self ):
print( 'BreadthFirstSearch : ' + self.__breadth_first( self.__root ) )
def __breadth_first( self, node ):
queue = myqueue.MyQueue()
result = ''
queue.offer( node )
while not queue.is_empty():
tmp = queue.poll()
result += ' ' + str( tmp.get_element() )
if tmp.get_left() != None:
queue.offer( tmp.get_left() )
if tmp.get_right() != None:
queue.offer( tmp.get_right() )
return result
def print_tree( self ):
print( self.__tree_to_string( 0, '', self.__root ) )
def __tree_to_string( self, n, direction, node ):
if node == None:
return ''
result = ''
result += '{:2}'.format( node.get_element() )
if node.get_left() != None and node.get_right() != None:
result += '┬'
elif node.get_right() != None:
result += '─'
elif node.get_left() != None:
result += '┐'
if node.get_right() != None and node.get_left() != None:
result += self.__tree_to_string( n + 1, direction + 'R', node.get_right() )
elif node.get_right() != None:
result += self.__tree_to_string( n + 1, direction + 'r', node.get_right() )
if node.get_left() != None:
result += '\n'
for i in range( n + 1 ):
result += ' '
if i < n and direction[ i : i+1 ] == 'R':
result += '│'
elif i < n:
result += ' '
result += '└'
result += self.__tree_to_string( n + 1, direction + 'L', node.get_left())
return result
def my_tree_node_test( self ):
node1 = mytreenode.MyTreeNode( 'i', None, None )
node2 = mytreenode.MyTreeNode( 'h', None, None )
node3 = mytreenode.MyTreeNode( 'g', node1, None )
node4 = mytreenode.MyTreeNode( 'f', None, None )
node5 = mytreenode.MyTreeNode( 'e', None, None )
node6 = mytreenode.MyTreeNode( 'd', None, node2 )
node7 = mytreenode.MyTreeNode( 'c', node4, node3 )
node8 = mytreenode.MyTreeNode( 'b', node6, node5 )
node9 = mytreenode.MyTreeNode( 'a', node8, node7 )
self.__root = node9
self.print_tree()
self.print_pre_order()
self.print_in_order()
self.print_post_order()
self.print_depth_first()
self.print_breadth_first()
def binary_search_tree_test( self ):
bst = MyBinarySearchTree()
count = 0
while count < 20:
r = random.randrange( 100 )
bst.insert( r )
count += 1
bst.print_pre_order()
bst.print_in_order()
bst.print_post_order()
bst.print_depth_first()
bst.print_breadth_first()
bst.print_tree()
for i in range( 5 ):
r = random.randrange( 100 )
if bst.find( r ):
print( str( r ) + 'はあります' )
else:
print( str( r ) + 'はありません' )
count = 0
while count < 10:
r = random.randrange( 100 )
if bst.delete( r ):
print( 'Delete ' + str( r ) )
count += 1
bst.print_tree()
if __name__ == '__main__':
MyBinarySearchTree().my_tree_node_test()
print()
MyBinarySearchTree().binary_search_tree_test()
231～248行目では、手作業でノードを追加して二分木（二分探索木にはなっていない）を作って表示しています。
251～280行目では、乱数を発生させてそれを要素とするノードを追加して二分探索木を作って表示しています。
それらの実行結果は次になります。
a ┬c ┬g ┐
│ │ └i
│ └f
└b ┬e
└d ─h
PreOrder : a b d h e c f g i
InOrder : d h b e a f c i g
PostOrder : h d e b f i g c a
DepthFirstSearch : a c b g f e d i h
BreadthFirstSearch : a b c d e f g h i
PreOrder : 90 63 57 32 19 8 12 16 28 36 44 41 44 53 58 73 64 63 93 94
InOrder : 8 12 16 19 28 32 36 41 44 44 53 57 58 63 63 64 73 90 93 94
PostOrder : 16 12 8 28 19 41 53 44 44 36 32 58 57 63 64 73 63 94 93 90
DepthFirstSearch : 90 93 63 94 73 57 64 58 32 63 36 19 44 28 8 44 41 12 53 16
BreadthFirstSearch : 90 63 93 57 73 94 32 58 64 19 36 63 8 28 44 12 41 44 16 53
90┬93─94
└63┬73┐
│ └64┐
│ └63
└57┬58
└32┬36─44┬44─53
│ └41
└19┬28
└ 8─12─16
14はありません
17はありません
75はありません
8はあります
79はありません
Delete 28
Delete 58
Delete 64
Delete 93
Delete 57
Delete 90
Delete 63
Delete 53
Delete 19
Delete 16
32┬36─44┬44─73┬94
│ │ └63
│ └41
└ 8─12
これで一旦データ構造についての内容はおしまいにします。それではまた。