2026-09-13
tree_sum.rs
struct Tree {
value: i32,
left: Option<Tree>,
right: Option<Tree>,
}
fn sum(t: &Tree) -> i32 {
let mut total = t.value;
if let Some(left) = &t.left {
total += sum(left);
}
if let Some(right) = &t.right {
total += sum(right);
}
total
}
子がいないことをNoneで表す二分木を書きましたが、sumを使う前にTreeの定義でコンパイルエラーになります。何が問題で、どう直せばよいでしょうか?
Answer
Option<T>はTを別の場所に置くのではなく、自分の中にそのまま埋め込みます。するとTreeの中にTreeが2つ、その中にさらに2つ……と入れ子になり、サイズが無限大になるので型として成り立ちません(E0072)。再帰する部分をBoxでヒープに置けば、Treeの中に持つのはポインタ1個分の大きさだけになります:
left: Option<Box<Tree>>,
right: Option<Box<Tree>>,
sumは1文字も変える必要がありません。leftは&Box<Tree>になりますが、sum(left)で参照外し型強制により&Treeとして渡されます。なおchildren: Vec<Tree>のような定義が最初から通るのは、Vecが要素をヒープに置く間接参照を内蔵しているからです。