Welcome to your new gem! In this directory, you'll find the files you need to be able to package up your Ruby library into a gem. Put your Ruby code in the file lib/binary_tree_builder. To experiment with that code, run bin/console for an interactive prompt.
TODO: Delete this and the text above, and describe your gem
二分木が取りうる構造を整数値として表現したものを出力するスクリプトおよびその出力結果。
以下の手順で生成されるビット列で表される整数値によって、二分木の構造を表す。
- 二分木のノードを0、葉を1とする
- 深さ優先でノード・葉を訪ねた順に上位からビット列を並べる
便宜上、リストの上に書かれているものが左の子とする。
- 0
- 1
- 1
この木からは 110 というビット列が得られ、整数値は 6 となる。
ノードが1個のとき、この値が唯一の整数値である（これ以外の構造がない）。
- 0
- 1
- 0
- 1
- 1
この木からは 11010 というビット列が得られ、整数値は 26 となる。
- 0
- 0
- 1
- 1
- 1
この木からは 11100 というビット列が得られ、整数値は 28 となる。
- 整数値はすべて偶数となる。なぜなら、木の根（最も上位）はノード（0）となるため。
- 最上位ビットは1となる。なぜなら、深さ優先で探索するため最初に訪問するのが葉（1）となるため。
- ビット列として表したとき、ビット列の長さは
2*ノードの個数 + 1となる。- 0 の個数がノードの個数と等しく、 1 の個数が葉の個数と等しい。
- 葉の個数はノードの個数に1加えた数に等しい。
- 以上から、
ビット列の長さ = ノードの個数 + 葉の個数 = ノードの個数 + ノードの個数 + 1 = 2*ノードの個数 + 1
- あるノードの個数に対して、得られる整数値の個数（二分木の構造の総数）はカタラン数に等しい。