二分木を出力する:K&R形式
K&Rでは、単語とその出現頻度を、各行に一つずつ表示しています。
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となります。