お知らせ

ただいま、シンタックスハイライターの設定を見直しております。
プログラムが見にくくなっているページがありますが、ご容赦ください。

Pythonでさまざまなデータ構造(2)

データ構造

こんにちは。前回は連結リスト構造とそれに関連したデータ構造をPythonでプログラムを書き直してみました。

今回は木構造に関係したデータ構造をPythonのプログラムにしてみたいと思います。

木構造の復習

木構造の説明のページは、次のものがありました。

二分探索木については、次の3ページで説明していました。

これらを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

これで一旦データ構造についての内容はおしまいにします。それではまた。

この記事を書いた人
春日井 優

高校で情報科という教科を担当しています。以前は数学科も担当していました。(今でも数学科の教員免許状は有効です。)プログラムを覚えたのは、「ゲームセンターあらし」という漫画のキャラクターがBASICを解説する「こんにちはマイコン」を読んだことがきっかけでした。

Posted by kasugai