Java meets Python - 第3回 構造体とクラス：二分木

よろずプログラマーのためのPython導入ガイド (5)

二分木を出力する：表形式

　ここでは、単語とその出現頻度を、各行に項目を列挙した表として表示します。各項目をカンマ「,」で区切るなら、その出力結果を表計算ソフトなどにも流用できます。

class Tnode:
    def table(self):
        format = "%%%dr: %%d\n"%(self.max_len_word()+2)
        return self._table(format)

　メソッドtableは、二分木を構成する各ノードを、表形式「単語:出現頻度」で表現します。関数max_len_wordは、最も長い単語の文字数を獲得します。補助関数_tableは、書式formatに従って、各ノードの文字列表現を獲得します。

class Tnode:
    def max_len_word(self):
        node = len(self.word)
        left = right = 0
        if self.left : left  = self.left.max_len_word()
        if self.right: right = self.right.max_len_word()
        return max(left, node, right)

　メソッドmax_len_wordは、二分木を構成する各ノードの中から、最も長い単語の文字数を獲得します。変数nodeには、自身のノードに含まれる単語の文字数を設定します。変数left/rightには、左右の部分木に含まれる最も長い単語の文字数として、初期値0を設定します。ifに続く条件式self.leftを満たすときには、左部分木を持つので、self.left.max_len_word()によって、左部分木に含まれる最も長い単語の文字数を得ます。右部分木も同様です。

class Tnode:
    def _table(self, format):
        node = format%(self.word, self.count)
        left = right = ""
        if self.left : left  = self.left._table(format)
        if self.right: right = self.right._table(format)
        return left + node + right

　補助関数_tableは、二分木を構成する各ノードを表形式で表現した文字列を生成します。変数nodeには、自身のノードに関する表形式の文字列表現を設定します。変数left/rightには、左右の部分木に関する表形式の文字列表現として、初期値""を設定します。ifに続く条件式self.leftを満たすときには、左部分木を持つので、self.left._table(format)によって、左部分木の文字列表現を獲得します。右部分木も同様です。

ためしてごらん

　では、実際にその動作を確認してみましょう。

>>> p = Tnode()
>>> p.table()
'': 0

　空ノードTnode()を生成して、結果を出力します。このとき、二分木pの表形式による文字列表現が使われます。すると、単語を含まないので、空文字列''に対する出現頻度は0となることが分かります。

>>> s = "CABDECEADEAEADE"
>>> p = None
>>> for e in s: p = addtree(p, e)
>>> p.table()
'A': 4
'B': 1
'C': 2
'D': 3
'E': 5

　二分木の「表形式」による文字列表現を使って、指定した文字列を構成する、各文字とその出現頻度を出力します。例えば、表形式'E':5から、文字'E'を5個含むことが分かります。

>>> s = "now is the time for all good men to come to the aid
 of their party"
>>> p = None
>>> for e in s.split(" "): p = addtree(p, e)
>>> p.table()
  'aid': 1
  'all': 1
 'come': 1
  'for': 1
 'good': 1
   'is': 1
  'men': 1
  'now': 1
   'of': 1
'party': 1
  'the': 2
'their': 1
 'time': 1
   'to': 2

　二分木の文字列表現を使って、先の例文を構成する、各単語とその出現頻度を出力します。例えば、表形式'the':2から、定冠詞'the'を2個含むことが分かります。

二分木を出力する：グラフ形式（CUI）

　ここでは、単語とその出現頻度を、グラフとして表示します。ただし、キャラクター端末（K&Rの初版が出版された年の時代背景を象徴する）を模してCUIを使います。グラフィックス端末を模してGUIを使った事例は、後の連載で紹介します。

class Tnode:
    tab = " "*6
    def tree(self):
        return self._tree(0)

　メソッドtreeは、二分木を構成する各ノードを、グラフ形式で表現します。補助関数_treeは、ルートを頂点とする階層構造に従って、各ノードの情報を表現します。

class Tnode:
    def _tree(self, indent):
        node = "%s+-- %r(%d)\n"%(
            self.tab*indent, self.word, self.count)
        left = right = "%s+--\n"%(self.tab*(indent+1))
        if self.left:
            left = self.left._tree(indent+1)
        if self.right:
            right = self.right._tree(indent+1)
        return left + node + right

　補助関数_treeは、二分木を構成する各ノードの情報をもとに、ルートを頂点とする階層構造に従って（グラフ形式で表現した）文字列を生成します。変数nodeには、自身のノードに関する文字列表現を設定します。二分木の高さ（深さ）indentに相当するタブself.tabを設定した後で、文字列表現「+--単語(出現頻度)」を設定します。変数left/rightには、左右の部分木を持たない場合に備えて、二分木の高さに相当するタブを出力した後で、左右の部分木に相当する文字列表現"+--"を初期値として設定しておきます。ifに続く条件式self.leftを満たすときには、左部分木を持つので、self.left._tree(indent+1)によって、左部分木の文字列表現を生成します。右部分木も同様です。

ためしてごらん

　では、実際にその動作を確認してみましょう。

>>> p = Tnode()
>>> p.tree()
      +--
+-- ''(0)
      +--

　空ノードTnode()を生成して、結果を出力します。このとき、二分木のグラフ形式による文字列表現が使われます。すると、単語を含まないので、空文字列""に対する出現頻度は0となることが分かります。左右の部分木を持たないので、相当数のタブに続いて文字列"+--"だけを出力します。

>>> s = "CABDECEADEAEADE"
>>> p = None
>>> for e in s: p = addtree(p, e)
>>> p.tree()
            +--
      +-- 'A'(4)
                  +--
            +-- 'B'(1)
                  +--
+-- 'C'(2)
            +--
      +-- 'D'(3)
                  +--
            +-- 'E'(5)
                  +--

　二分木の「グラフ形式」による文字列表現を使って、指定した文字列を構成する、各文字とその出現頻度を出力します。例えば、グラフ形式の表現+-- 'E'(5)から、文字'E'を5個含むだけでなく、その部分木の構造も明確になります。

>>> s = "now is the time for all good men to come to the aid
 of their party"
>>> p = None
>>> for e in s.split(" "): p = addtree(p, e)
>>> p.tree()
...

　二分木のグラフ形式の表現を、K&R（p.139）の事例と比較してください。

♪あの時君は若かった

　K&Rの時代背景を象徴する、キャラクター端末の出力を疑似体験したい読者の皆さんは、付属のコードを実行してください。すると、次のように、

　等幅フォントCourierを使って、グラフが表示されます。