  |
はてなキーワード: 木構造とは
いや、ごめん。再帰というのは、木構造による再帰、でも、Switchによる再帰でも同じ。そのアルゴリズムで Call命令を使うのか？って事。
あとCでもswitchが嫌で かつ 再帰によるCall命令が許容されるなら、Treeに関数ポインタ持たせて、関数ポインタで評価関数呼び出せばいいじゃん。
単純に要素だけ書けば
struct leaf{
int (*eval)(leaf *);
};
でよかろ 値を入れるときにAddなら eval_add sub なら eval_sub を呼び出せばいい （データー構造と アルゴリズムの分離はCでもできる。）
どっちみち C++でも、子どものevalを親が呼ぶ 時点で call が呼ばれているから、それ再帰。
というかC++自体が こういう vtableのC実装から 生まれている実装なので C++でできて、Cで実装できないって、テンプレとかそういうのぐらいだから。
究極的にはvtalbe実装すればCでもできる。つか、昔のCのコードなんてVtableを第１引数として渡すようなものばっかだろ。
何が言いたいかというと、別に データー構造と アルゴリズムの分離は関数ポインタとVtableの実装によりCでもできる。
switchテーブルが巨大化するのも 小さいクラスが無数にあるのも どっちも同じ事だよ。
Swithならよい Classならよいってことはない。
「Cならswitchテーブルを使った再帰関数で実現する必要がある」に対するレスなんだろうけど、飽くまでも「C以外の、継承とオーバーライドの機能がある言語では例題とほぼ同じ形で実装できるのに対してその機能がない言語では『関数内でswitchをして値ごとにdispatch、その後更に再帰』という原始的かつ全てのロジックを詰め込むせいでひとつの関数の行数が膨大になる問題を孕んでいる」という意味しか持たない。
確かにTopCoderで再帰を使ったら撃墜される可能性がある事には同意だけど、今回の例ではプロコンの外側での事であってスタックがオーバーフローしたなら例外をキャッチして後処理を行えば良い。
更に
バイナリツリーを自前で構築して式を表現する例題（expression tree）と、set and mapは用途が違う。
setとmapは本来、順序が定義できる要素をキーにしてそれそのものを保持するか、或いはそれに伴う値を結びつけて保持しておくもの。
例題のexpression treeの構造は「（必ずしもオペランドがふたつとは限らない）式の木を表現して、オーバーライドされたevalで式全体の評価を行う」もの。
は成り立たない主張であるし、
（C言語等のOOPが導入される前の言語で）綺麗に書く事ができないと問題を提供する側がそもそも「綺麗な解を前提とした問題」を出せない。
いや、再帰は使わんと思うぞ・・・Stack Over Flow対策があるから自前で再帰は展開するぞ。
それに 問題を解くためにバイナリーツリーを使うことはあっても、バイナリーツリーを使う問題は出てこないわなぁ。
あとは、分岐点が値を持ってないので、右に追加するか左に追加するかの判定ロジックも出来ないわなぁ。その構造だと。
あと 加算するか減産するかはアルゴリズムが持つものであって、木そのものが持つわけじゃない。
全般的にその木構造なんかへんやろ。例題なのはわかるけど、それにしても、なんか変。
縦横高さと tree からいきぺぢる。
「縦横高さ」が意図するものは次元だった。二次元の時は行列とも云えるのかな？
tree これははっきりしていた。所謂木構造。でも色々種類あるのね。
789 456 123
木構造は特に制約を定めなければ幾らでも伸びしろがある。次元は先に作っておいた次元が精一杯。次元の最小単位の中に別の次元を放り込むのは親の次元とは赤の他人だし……
n を選んで、次に m を選ぶ、これを繰り返して行くような作業をするとき、木構造でも幹線部分は密なので一見して次元に見える？
