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

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

二分木を出力する：K&R形式

　K&Rでは、単語とその出現頻度を、各行に一つずつ表示しています。

K＆R, p.142

void treeprint(struct tnode *p)
{
    if (p != NULL) {
        treeprint(p->left);
        printf("%4d %s\n", p->count, p->word);
        treeprint(p->right);
    }
}

　C言語版の関数treeprintは、二分木を構成する各ノードpが保持する、単語wordとその出現頻度countを、間順走査（左部分木→ノード→右部分木）に従って出力します。

def treeprint(p):
    if p:
        treeprint(p.left)
        print "%4d %s"%(p.count, p.word)
        treeprint(p.right)

　関数treeprintでは、ifに続く条件式pを満たすときには、そこにノードpが存在します。まず、左部分木p.leftが存在する可能性があるので、treeprint(p.left)の引数に左部分木を指定します。次に、各ノードpが保持する、単語p.wordとその出現頻度p.countを出力します。さらに、右部分木p.rightが存在する可能性があるので、treeprint(p.right)の引数に右部分木を指定します。

ためしてごらん

　これで、二分木が保持する情報を出力する準備が整いました。では、実際にその動作を確認してみましょう。最初に、ノードを一つも持たない場合から始めます。

>>> p = Tnode()
>>> treeprint(p)
   0

　生成した空ノードTnode()が保持する情報を、関数treeprint()を使って出力します。すると、単語を含まないので、出現頻度は0となるのが分かります。このように、要素を持たない二分木に対しても、関数の動作を確認するのは大切です。

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

　次に、関数addtree()を使って、指定した文字列sを構成する、各文字（長さ1の文字列）eとその出現頻度を出力します。すると、この文字列sは、5個の文字'E'を含むことが分かります。

>>> 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)
>>> treeprint(p)
   1 aid
   1 all
   1 come
   1 for
   1 good
   1 is
   1 men
   1 now
   1 of
   1 party
   2 the
   1 their
   1 time
   2 to

　最後に、関数addtree()を使って、K&R, p.139に紹介してある例文"now is the time ... of their party"を構成する、各単語とその出現頻度を出力します。すると、この例文には、2個の定冠詞'the'を含むことが分かります。

　ここでは、例文に含まれる各単語を抽出するのに、文字列に適用できるメソッドsplitを利用しています。すると、引数に指定した空白文字" "を区切り文字として、例文に含まれる各単語を列挙したリストが得られます。

二分木を出力する：リスト形式

　ここでは、単語とその出現頻度を、括弧で括ったリストとして表示します。

class Tnode:
    def __str__(self):
        return "%s(%d,%s,%s)"%(
            self.word, self.count,
            (self.left , "")[not self.left ],
            (self.right, "")[not self.right],
            )

　メソッド__str__は、組み込み関数str()の操作を規定します。二分木に固有の文字列表現を獲得します。ここでは、二分木を構成する各ノードを、括弧で括ったリスト形式「単語(出現頻度,左部分木,右部分木)」で表現します。このとき、左右の部分木を持たないなら、空の文字列""を出力します。つまり、何も出力しません。

補足

　これによって、三項演算子と等価な表現が可能となりますが、その詳細は後の連載で紹介する予定です。または、ブログの記事を参照してください。

class Tnode:
    def __len__(self):
        node = 1
        left = right = 0
        if self.left:
            left  = len(self.left)
        if self.right:
            right = len(self.right)
        return left + node + right

　メソッド__len__は、組み込み関数len()の操作を規定します。二分木を構成するノードの個数を獲得します。変数nodeには、自身のノード数を表わす値1を設定します。変数left/rightには、左右の部分木のノード数を表わす初期値0を設定します。ifに続く条件式self.leftを満たすときには、左部分木を持つので、len(self.left)によって、左部分木のノードの個数を得ます。右部分木も同様です。

ためしてごらん

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

>>> p = Tnode()
>>> p
(0,,)
>>> len(p)
1

　空ノードTnode()を生成して、結果を出力します。このとき、二分木pの文字列表現が使われます。すると、単語を含まないので、その出現頻度は0となることが分かります。このとき、左右の部分木を持たないので、カンマ「,」だけを出力します。また、左右の部分木を持たないので、ノードの個数len(p)は1となります。

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

　二分木pの「リスト形式」による文字列表現を使って、指定した文字列sを構成する、各文字とその出現頻度を出力します。すると、リスト形式の表現E(5,,)から、文字'E'を5個含むと共に、その傘下には左右の部分木を持たないことが分かります。また、ノードの個数len(p)は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
now(1,is(1,for(1,all(1,aid(1,,),come(1,,)),good(1,,)),men(1,,)),
the(2,of(1,,party(1,,)),time(1,their(1,,),to(2,,))))
>>> len(p)
14

　二分木pの文字列表現を使って、先の例文を構成する、各単語とその出現頻度を出力します。すると、リスト形式の表現the(2,of(...),time(...))から、定冠詞'the'を2個含むと共に、左右の部分木を持つことが分かります。また、ノードの個数len(p)は14となります。