皆さんは木
を標準出力してますか？この木なんの木気になる木1。木構造を扱うことは多くても出力するとなると適当にすませているのではないでしょうか？
木構造を書く機会が多かったので今回備忘録として投稿します!
最近はRustばかり書いていますが、他の言語でも同じ考え方で実装できるよう、Pythonでも書きました。色々な出力様式が考えられますが、bashで用いられている tree コマンド2の出力形式が一番楽そうなので、このフォーマットでの出力を本記事では目指すことにします。
tree コマンドの出力はこんな感じです。このディレクトリは表示用に適当に作ったものです。
$ tree
.
├── a1.txt
├── hoge_dir
│ ├── a2.txt
│ ├── a3.txt
│ ├── a4.txt
│ └── fuga_dir
│ └── a5.txt
├── src
│ └── main.rs
└── sub_dir
├── a_dir
│ ├── a_dir
│ │ └── b7.txt
│ ├── hoge_dir
│ │ └── b6.txt
│ └── tmp
│ ├── b4.txt
│ └── b5.txt
├── b1.txt
├── b2.txt
└── b3.txt
8 directories, 13 files
親が左上に来て、子供が右下に連なっていますね。この出力方法なら再帰関数を使うことで簡単に出力することができます。
木構造を扱う構造体
出力部分だけその時々でハードコードすることにしても良い(ハードコードの場合でも本記事は参考になるはずです。)ですが、とりあえず一般的な木の構造を表すための構造体を作り、それを利用して出力するようにすれば、使い回せて便利そうです。世の中には色々な木がありますが、出力のことだけを考えれば
- 葉っぱ (
leaf node) - 途中 (
internal node)
の２つがあれば目的を達成できそうです。Rust、Python両言語で書いてみます。
まずRust
pub enum Node<T> {
Leaf {
item: T,
},
Internal {
item: T,
children: Vec<Box<Node<T>>>,
},
}
Rustの列挙型はこのように構造体のようにも使えます！まさに今回のためにあるような機能でしょう。ノードそのものの情報となる item と、途中のノードが持つ子ノードを格納する children が設けられています。 Vec は配列型の意味で、 Box はとりあえずおまじないだと思ってください3。
2022/10/17 追記
記事執筆時に筆者の知識不足よりBox型を使用していましたが、今回の場合不要でした。(Twitterでご指摘いただきました。ありがとうございます。)
Rustではデータ構造はデフォルトではなんでもスタックに保存するようになっており(そのためコンパイル時にメモリ上サイズが分かるSizedトレイト実装型をしばしば要求されがちです)、その中でBox型やVec型はヒープに保存するために用意された型になっています。その他にはスマートポインタに該当するRcなども同じくヒープに保存する仕組みになっています(確か)。
話が戻りますが、ヒープに保存する目的でBoxを使用していましたがVec型で包んでいる時点で不要です。記事全体を直すのは面倒&Box型に対する理解が深まる良いケースというわけで、当時のままとしておきます。
その代わり、最後のソースコード全体をまとめている箇所にBox型を使わないバージョンも置いておきます。
つぎにPython
class Node:
def __init__(self, item, childlen = None):
self.item = item
self.childlen = childlen if childlen is not None else []
Rust書きすぎてPythonをしばらく書いてなかったのですが、僕の記憶が正しければPythonにRustのような列挙型はなかった気がします。少々不安ではありますが、 self.children の要素数で両者を区別することとします。
再帰関数を利用して木を出力する
さくっと今回のメインディッシュです。再帰関数は
- すでに完成したものと考えながら、その関数の中で使用する
- 終了条件を決めておく
というポイントを抑えながら実装します。また今回は「最初から最後の一つ手前までの子ノード」と「最後のノード」では、インデントの様子と枝の様子が異なっているので、そのことに注意して実装する必要があります。先にコードを載せます。
まずRustの場合
impl<T: Display> Node<T> {
pub fn get_tree(&self) -> String {
let mut res = String::new();
self.tree_rec(&mut res, "");
res
}
fn tree_rec(&self, tree: &mut String, indent: &str) {
match self {
Self::Leaf { item } => {
let s = format!("{}\n", item);
tree.push_str(s.as_str());
}
Self::Internal { item, children } => {
let s = format!("{}\n", item);
tree.push_str(s.as_str());
let mut ch_iter = children.iter().peekable();
while let Some(c) = ch_iter.next() {
let is_last = ch_iter.peek().is_some();
tree.push_str(
format!("{}{}", indent, if is_last { "├── " } else { "└── " }).as_str(),
);
c.tree_rec(
tree,
format!("{}{} ", indent, if is_last { "|" } else { " " }).as_str(),
);
}
}
}
}
}
get_tree 関数は再帰関数のラッパーとなります。結果を格納する文字列を用意し、再帰関数を開始させています。
tree_rec 関数がミソとなる再帰関数です。 今回、再帰の終了条件ははっきりしています。それは「葉っぱにたどり着いた時」です4。Rustの match 式によってこの終了条件は Self::Leaf { item } で拾われ、再帰は終了していることがわかります。出力が目的なので葉の中身を文字列に出力しています。出力のために、 item の型 T には Display トレイトを指定しています。
再帰を内包する Self::Internal { item, children } が本記事で一番気をつけるべき場所でしょう。最後の要素であるか判別するため、Rustのほうではトリッキーな書き方になってしまいました5。まずは葉の場合と同じく item を文字列に出力し、そのあとに子ノードを再帰的に出力することを試みています。
再帰部分の解説は後ほど詳しくするとして、先にPythonの場合も見ましょう。
class Node:
def __init__(self, item, childlen = None):
self.item = item
self.childlen = childlen if childlen is not None else []
def get_tree(self):
tree = [""]
indent = ""
self.tree_rec(tree, indent)
return tree[0]
def tree_rec(self, tree, indent):
tree[0] += f"{self.item}\n"
if len(self.childlen) == 0:
return
for c in self.childlen[:-1]:
tree[0] += f"{indent}├── "
c.tree_rec(tree, f"{indent}| ")
tree[0] += f"{indent}└── "
self.childlen[-1].tree_rec(tree, f"{indent} ")
Rustで実装後にそのまま同じ考えで実装したので tree の部分を副作用で変化させるためにリストに入れたりなど少し無理やりな書き方になってしまっていますが、Rustよりも短く実装することができたのでこちらのほうが読みやすそうです。
再帰部分はソースコードだけではわかりにくいので頑張って解説します。RustコードかPythonコードと照らし合わせてみてください。なお、この再帰部分は人によって書き方が変わってくる部分だと思います。一つの考え方として捉えていただけると幸いです。
再帰が深くなるにつれてインデントが積み重なっていく
積み重なること自体は直感的にわかると思います。ある時点でインデントの中身を決定する必要があります。インデントの中身が決定するタイミングごとに色分けすると、僕の実装では次のようになっています。(図で使ったディレクトリは最初に tree コマンドで示したディレクトリの途中です。)
積み重ねるインデントは2種類です。まだ子ノードが最後の一つではない場合 |@@@ 、つまり縦棒とスペース3つ(@で代用)であり、最後の一つの場合は @@@@ 、つまりスペース4つとなります。これは望む表示がそれぞれ
├── <- すでに出力
| <- インデント部分
└── <- すでに出力
<- インデント部分
となることからわかります。
再帰呼出しにおける indent 引数部分がこの積み重ねる処理に該当します。Pythonでは f"{indent}| " のようになっているのが確認できると思います。
出力の分担
親は子のために枝を出力し、子は自分自身と改行を出力する義務を持つものとします。子が改行を担当するとうまくいくのは、葉の数と改行の数が必ず等しいことからわかります。子が以降必要な改行を全て出力することはわかっているので、親は改行を出力する必要はありません。
tree 変数への出力について再帰の階層ごとに色分けすると、次のようになります。インデントが決定するタイミングとは異なることに気をつけてください。
つまり各呼び出しでは自分自身の情報&一つの改行と、子ノードのための枝を出力しているというのが確認できます。
全体の完成と活用
ここまでで重要な木の実装方法は述べました。しかしこれでちゃんと木として出力されるのかは確認していません。というわけで tree コマンドを作成することで確認します。
記事の本筋ではないので、解説は軽めで済ませます。
Rust版自作treeコマンド
まずはライブラリ部分の完成です。 Display トレイトの実装とかマクロ機能とかおまけが色々ついていますがそのままにしておいています。
use std::fmt;
use std::fmt::Display;
pub enum Node<T> {
Leaf {
item: T,
},
Internal {
item: T,
children: Vec<Box<Node<T>>>,
},
}
impl<T: Display> Display for Node<T> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Node::Internal { item, children } => write!(
f,
"{} {{{}}}",
item,
children
.iter()
.map(|i| i.to_string())
.collect::<Vec<_>>()
.join(", ")
),
Node::Leaf { item } => write!(f, "{}", item),
}
}
}
impl<T> Node<T> {
pub fn leaf(item: T) -> Self {
Node::Leaf { item }
}
pub fn internal(item: T, children_list: Vec<Self>) -> Self {
Node::Internal {
item,
children: children_list
.into_iter()
.map(|item| Box::new(item))
.collect::<Vec<_>>(),
}
}
}
impl<T: Display> Node<T> {
pub fn get_tree(&self) -> String {
let mut res = String::new();
self.tree_rec(&mut res, "");
res
}
fn tree_rec(&self, tree: &mut String, indent: &str) {
match self {
Self::Leaf { item } => {
let s = format!("{}\n", item);
tree.push_str(s.as_str());
}
Self::Internal { item, children } => {
let s = format!("{}\n", item);
tree.push_str(s.as_str());
let mut ch_iter = children.iter().peekable();
while let Some(c) = ch_iter.next() {
let is_last = ch_iter.peek().is_some();
tree.push_str(
format!("{}{}", indent, if is_last { "├── " } else { "└── " }).as_str(),
);
c.tree_rec(
tree,
format!("{}{} ", indent, if is_last { "|" } else { " " }).as_str(),
);
}
}
}
}
}
#[macro_export]
macro_rules! node {
( $item:expr ) => {
Node::Leaf { item: $item }
};
( $item:expr, $( $c:expr ),* ) => {
Node::Internal {
item: $item,
children: vec![
$(
Box::new($c),
)*
],
}
};
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test1() {
let top = Node::Internal {
item: "hoge/",
children: vec![
Box::new(Node::Leaf { item: "fuga" }),
Box::new(Node::Internal {
item: "pipi/",
children: vec![
Box::new(Node::Internal {
item: "beep/",
children: vec![Box::new(Node::Leaf { item: "p" })],
}),
Box::new(Node::Leaf { item: "peeb" }),
],
}),
Box::new(Node::Leaf { item: "bar" }),
Box::new(Node::Internal {
item: "baz/",
children: vec![
Box::new(Node::Internal {
item: "apple/",
children: vec![
Box::new(Node::Internal {
item: "a/",
children: vec![Box::new(Node::Leaf { item: "aa" })],
}),
Box::new(Node::Leaf { item: "b" }),
Box::new(Node::Internal {
item: "c/",
children: vec![Box::new(Node::Leaf { item: "cc" })],
}),
],
}),
Box::new(Node::Leaf { item: "banana" }),
],
}),
],
};
let res = top.get_tree();
println!("{}", res);
assert_eq!(
res,
String::from(
"\
hoge/
├── fuga
├── pipi/
| ├── beep/
| | └── p
| └── peeb
├── bar
└── baz/
├── apple/
| ├── a/
| | └── aa
| ├── b
| └── c/
| └── cc
└── banana
"
)
);
}
#[test]
fn test2() {
let top = Node::internal(
"hoge/",
vec![
Node::leaf("fuga"),
Node::internal(
"pipi/",
vec![
Node::internal("beep/", vec![Node::leaf("p")]),
Node::leaf("peeb"),
],
),
Node::leaf("bar"),
Node::internal(
"baz/",
vec![
Node::internal(
"apple/",
vec![
Node::internal("a/", vec![Node::leaf("aa")]),
Node::leaf("b"),
Node::internal("c/", vec![Node::leaf("cc")]),
],
),
Node::leaf("banana"),
],
),
],
);
let res = top.get_tree();
println!("{}", res);
assert_eq!(
res,
String::from(
"\
hoge/
├── fuga
├── pipi/
| ├── beep/
| | └── p
| └── peeb
├── bar
└── baz/
├── apple/
| ├── a/
| | └── aa
| ├── b
| └── c/
| └── cc
└── banana
"
)
);
}
#[test]
fn test3() {
let top = node! {
"hoge/",
node! {
"fuga/",
node! {
"bar"
},
node! {
"baz"
}
},
node! {
"tmp"
},
node! {
"aaa",
node! { "bbb" }
}
};
let res = top.get_tree();
println!("{}", res);
assert_eq!(
res,
String::from(
"\
hoge/
├── fuga/
| ├── bar
| └── baz
├── tmp
└── aaa
└── bbb
"
)
);
}
}
2022/10/17 追記Box除去バージョン internalメソッドがあんまり意味なくなってる...
use std::fmt;
use std::fmt::Display;
pub enum Node<T> {
Leaf {
item: T,
},
Internal {
item: T,
children: Vec<Node<T>>,
},
}
impl<T: Display> Display for Node<T> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Node::Internal { item, children } => write!(
f,
"{} {{{}}}",
item,
children
.iter()
.map(|i| i.to_string())
.collect::<Vec<_>>()
.join(", ")
),
Node::Leaf { item } => write!(f, "{}", item),
}
}
}
impl<T> Node<T> {
pub fn leaf(item: T) -> Self {
Node::Leaf { item }
}
pub fn internal(item: T, children_list: Vec<Self>) -> Self {
Node::Internal {
item,
children: children_list
.into_iter()
.map(|item| item)
.collect::<Vec<_>>(),
}
}
}
impl<T: Display> Node<T> {
pub fn get_tree(&self) -> String {
let mut res = String::new();
self.tree_rec(&mut res, "");
res
}
fn tree_rec(&self, tree: &mut String, indent: &str) {
match self {
Self::Leaf { item } => {
let s = format!("{}\n", item);
tree.push_str(s.as_str());
}
Self::Internal { item, children } => {
let s = format!("{}\n", item);
tree.push_str(s.as_str());
let mut ch_iter = children.iter().peekable();
while let Some(c) = ch_iter.next() {
let is_last = ch_iter.peek().is_some();
tree.push_str(
format!("{}{}", indent, if is_last { "├── " } else { "└── " }).as_str(),
);
c.tree_rec(
tree,
format!("{}{} ", indent, if is_last { "|" } else { " " }).as_str(),
);
}
}
}
}
}
#[macro_export]
macro_rules! node {
( $item:expr ) => {
Node::Leaf { item: $item }
};
( $item:expr, $( $c:expr ),* ) => {
Node::Internal {
item: $item,
children: vec![
$(
$c,
)*
],
}
};
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test1() {
let top = Node::Internal {
item: "hoge/",
children: vec![
Node::Leaf { item: "fuga" },
Node::Internal {
item: "pipi/",
children: vec![
Node::Internal {
item: "beep/",
children: vec![Node::Leaf { item: "p" }],
},
Node::Leaf { item: "peeb" },
],
},
Node::Leaf { item: "bar" },
Node::Internal {
item: "baz/",
children: vec![
Node::Internal {
item: "apple/",
children: vec![
Node::Internal {
item: "a/",
children: vec![Node::Leaf { item: "aa" }],
},
Node::Leaf { item: "b" },
Node::Internal {
item: "c/",
children: vec![Node::Leaf { item: "cc" }],
},
],
},
Node::Leaf { item: "banana" },
],
},
],
};
let res = top.get_tree();
println!("{}", res);
assert_eq!(
res,
String::from(
"\
hoge/
├── fuga
├── pipi/
| ├── beep/
| | └── p
| └── peeb
├── bar
└── baz/
├── apple/
| ├── a/
| | └── aa
| ├── b
| └── c/
| └── cc
└── banana
"
)
);
}
#[test]
fn test2() {
let top = Node::internal(
"hoge/",
vec![
Node::leaf("fuga"),
Node::internal(
"pipi/",
vec![
Node::internal("beep/", vec![Node::leaf("p")]),
Node::leaf("peeb"),
],
),
Node::leaf("bar"),
Node::internal(
"baz/",
vec![
Node::internal(
"apple/",
vec![
Node::internal("a/", vec![Node::leaf("aa")]),
Node::leaf("b"),
Node::internal("c/", vec![Node::leaf("cc")]),
],
),
Node::leaf("banana"),
],
),
],
);
let res = top.get_tree();
println!("{}", res);
assert_eq!(
res,
String::from(
"\
hoge/
├── fuga
├── pipi/
| ├── beep/
| | └── p
| └── peeb
├── bar
└── baz/
├── apple/
| ├── a/
| | └── aa
| ├── b
| └── c/
| └── cc
└── banana
"
)
);
}
#[test]
fn test3() {
let top = node! {
"hoge/",
node! {
"fuga/",
node! {
"bar"
},
node! {
"baz"
}
},
node! {
"tmp"
},
node! {
"aaa",
node! { "bbb" }
}
};
let res = top.get_tree();
println!("{}", res);
assert_eq!(
res,
String::from(
"\
hoge/
├── fuga/
| ├── bar
| └── baz
├── tmp
└── aaa
└── bbb
"
)
);
}
}
次に実際にこのライブラリを使用してみます。ワークスペースを作成しそこにバイナリプロジェクトとライブラリをまとめます。(主要ファイルのみ表示)
.
├── Cargo.toml
├── target/
| └── debug/
| └── tree
├── tree/
| ├── Cargo.toml
| └── src/
| └── main.rs
└── tree_disp/
├── Cargo.toml
└── src/
└── lib.rs
[workspace]
members = [
"tree",
"tree_disp",
]
～～ 省略 ～～
[dependencies]
tree_disp = { path = "../tree_disp" }
walkdir = "2"
getopts = "*"
tree コマンドの実装部分です。記述を少し楽にする目的で walkdir を導入しましたがあまり意味がなかったかもしれません。
extern crate getopts;
extern crate tree_disp;
extern crate walkdir;
use getopts::Options;
use std::path::Path;
use tree_disp::Node;
use walkdir::WalkDir;
fn dir_rec(dir_path: &Path, level: usize) -> Node<String> {
let dir_name = if dir_path.to_str() != Some(".") {
dir_path
.file_name()
.map(|s| s.to_string_lossy().to_string())
.unwrap_or(String::new())
} else {
".".to_string()
};
let dir_name = format!("{}/", dir_name);
if level == 0 {
return Node::leaf(dir_name);
}
let children = WalkDir::new(dir_path)
.max_depth(1)
.into_iter()
.filter_map(|e| {
if e.is_err() {
return None;
}
let entry = e.unwrap();
if entry.path() == dir_path {
return None;
}
Some(if entry.file_type().is_dir() {
dir_rec(&entry.path(), level - 1)
} else {
let entry_name = entry.file_name().to_string_lossy();
Node::leaf(entry_name.to_string())
})
})
.collect::<Vec<_>>();
Node::internal(dir_name, children)
}
fn print_usage(program: &str, opts: Options) {
let brief = format!("Usage: {} FILE [options]", program);
print!("{}", opts.usage(&brief));
}
fn main() {
let args = std::env::args().collect::<Vec<_>>();
let program = args[0].clone();
let mut opts = Options::new();
opts.optopt("L", "", "Descend only level directories deep.", "level");
opts.optflag("h", "help", "print this help menu");
let matches = match opts.parse(&args[1..]) {
Ok(m) => m,
Err(f) => panic!(f.to_string()),
};
if matches.opt_present("h") {
print_usage(&program, opts);
return;
}
let level = matches
.opt_str("L")
.map_or(10, |l| l.parse::<usize>().unwrap_or(10));
let dir_name = if !matches.free.is_empty() {
matches.free[0].clone()
} else {
".".to_string()
};
let top = dir_rec(&Path::new(&dir_name), level);
println!("{}", top.get_tree());
}
ライブラリを作った時同様、こちらも再帰関数を利用して木を構成しています。
実行すると、以下のように出力を確認できました。(実行ファイルを適当な場所に移して実行しています。)
$ ./tree test_dir/
test_dir/
├── a1.txt
├── hoge_dir/
| ├── a2.txt
| ├── a3.txt
| ├── a4.txt
| └── fuga_dir/
| └── a5.txt
├── src/
| └── main.rs
└── sub_dir/
├── a_dir/
| ├── a_dir/
| | └── b7.txt
| ├── hoge_dir/
| | └── b6.txt
| └── tmp/
| ├── b4.txt
| └── b5.txt
├── b1.txt
├── b2.txt
└── b3.txt
Python版自作treeコマンド
Python版もRust版と似たような感じでライブラリ部分とコマンド部分を分割します。やはり全体的にRustより少ない行数で済みました。
まずライブラリ部分
class Node:
def __init__(self, item, childlen = None):
self.item = item
self.childlen = childlen if childlen is not None else []
def __str__(self):
tmp = f" {{ {self.children} }}" if len(self.childlen) else ""
return f"{self.item}{tmp}"
def get_tree(self):
tree = [""]
indent = ""
self.tree_rec(tree, indent)
return tree[0]
def tree_rec(self, tree, indent):
tree[0] += f"{self.item}\n"
if len(self.childlen) == 0:
return
for c in self.childlen[:-1]:
tree[0] += f"{indent}├── "
c.tree_rec(tree, f"{indent}| ")
tree[0] += f"{indent}└── "
self.childlen[-1].tree_rec(tree, f"{indent} ")
if __name__ == "__main__":
top = Node("hoge/", [
Node("fuga"),
Node("pipi/", [
Node("beep/", [Node("p")]),
Node("peeb"),
]),
Node("bar"),
Node("baz/", [
Node("apple/", [
Node("a/", [Node("aa")]),
Node("b"),
Node("c/", [Node("cc")]),
]),
Node("banana"),
]),
])
res = top.get_tree()
correct_ans = """\
hoge/
├── fuga
├── pipi/
| ├── beep/
| | └── p
| └── peeb
├── bar
└── baz/
├── apple/
| ├── a/
| | └── aa
| ├── b
| └── c/
| └── cc
└── banana
"""
print(res)
assert res == correct_ans
次に tree コマンドに相当する部分
import os
import sys
from tree_disp import Node
def dir_rec(dir_name, dir_path, level):
if level == 0:
return Node(f"{dir_name}/")
def func(f):
p = os.path.join(dir_path, f)
if os.path.isdir(p):
return dir_rec(f, p, level-1)
else:
return Node(f)
childlen = list(map(func, [f for f in os.listdir(dir_path)]))
return Node(f"{dir_name}/", childlen)
def main():
dir_name = sys.argv[1] if len(sys.argv) >= 2 else "."
level = int(sys.argv[2]) if len(sys.argv) >= 3 else 10
top = dir_rec(os.path.basename(dir_name), dir_name, level)
print(top.get_tree())
main()
やっていることはRustと変わらないのにやはり短いなぁと思います。(ただしPython版はオプション機能が簡略化されています。)
実行結果はRust版と変わりません。
$ python3 tree.py test_dir
test_dir/
├── a1.txt
├── hoge_dir/
| ├── a2.txt
| ├── a3.txt
| ├── a4.txt
| └── fuga_dir/
| └── a5.txt
├── src/
| └── main.rs
└── sub_dir/
├── a_dir/
| ├── a_dir/
| | └── b7.txt
| ├── hoge_dir/
| | └── b6.txt
| └── tmp/
| ├── b4.txt
| └── b5.txt
├── b1.txt
├── b2.txt
└── b3.txt
最後に 
自分が気をつけておきたいポイントを中心に木構造の標準出力の実装方法を解説しました。人によってはわかりにくい部分があったかもしれません。また(特に実際に tree コマンドを自作した部分などについて)書き方がおかしかったり、間違っていたりするかもしれません。もしそういった点があれば、コメントや編集リクエストをくださると幸いです。
ここまで読んでいただきありがとうございました！
-
この木NaNの木気にnull木というツイートをこの前見かけ笑いました。注釈に書くことじゃないですね。ごめんなさい。 ↩
-
treeコマンドはbash標準のコマンドではないのでパッケージマネージャで導入する必要があります。 ↩ -
おまじないって言葉よくないですよね。型がマトリョーシカみたいになっちゃう時、型のサイズが未定になってしまうので、それを防止するために使います。詳しくは Boxはヒープのデータを指し、既知のサイズである - The Rust Programming Language を読んでください。
2020/10/11追記: 実は追記部分を読んでください。 ↩Vecの時点でサイズは定まる(ヒープに保存される)のでBoxで囲む必要はないです。記事の修正が面倒なのでそのままにします。(いつか直す) -
親の持っている子要素の個数が0のときも当然終了します。また今回についてもこの場合があり得ます。考えてみれば、
Node::Leafは不要かもしれません。 ↩ -
所有権の都合上分割したりといった書き方は面倒な感じになってしまいます(できないわけではない)。できれば一緒に処理したかったので今回はこう書きました。 ↩