二分木 - Rustではじめるデータ構造とアルゴリズム（第1回）

Rustの特徴のひとつは、所有権(ownership)・移動(move)・借用(borrow)の概念です。これらがコンパイル時に厳格にチェックされることにより、古くから未定義挙動でプログラマを悩ませてきたダングリングポインタなどの問題がなくなり、メモリ安全性がもたらされます。

しかし一方で、自分で多少複雑なデータ構造を定義しようとする場合にはコンパイルを通すだけでもかなりの知識・力量が要求されます。

この（不定期）連載では、 Rustではじめるデータ構造とアルゴリズム と題し、プログラミングコンテストなどでよく見かける基礎的なデータ構造とアルゴリズムを、できるだけシンプルにRustで実装していきます。 &, &mut, Box, Rc, Cell, RefCell などの使い分けや、なぜそれを使う必要があるかの解説を、実例を通して行います。

第1回は、最もシンプルな木構造である 二分木 を取り扱います。基礎的な木構造なので、再帰・深さ優先探索・幅優先探索のエッセンスを集中的に理解することが期待できます。

各回共通し、以下のような構成を予定しています。

データ構造の説明と、Rustでの定義
関連するアルゴリズムの説明と、（汎用的に実装できる場合は）Rustでの実装
定義したデータ構造とアルゴリズムを使って、プログラミングコンテストの問題を解いてみる

連載記事一覧

二分木 （この記事）
二分探索木
平衡二分探索木 （未執筆）
ヒープ （未執筆）
有向グラフ（ポインタ表現） （未執筆）
有向グラフ（行列表現） （未執筆）
無向グラフ（ポインタ表現） （未執筆）
無向グラフ（行列表現） （未執筆）

更新履歴

2020/01/01
- typo修正と、 BinaryTree::Nil への参照解決できずに構築のコードがコンパイル不可な問題を修正。Fix trivial mistakes in the 12-22 post で @magurotuna さんからPRいただきました🌅
2019/12/31
- bin_tree! マクロがケツカンマの重複を許す問題を修正。Fix the trailing-comma patterns in macros で更に @__gfx__氏からPRいただきました🙏
2019/12/29
- 二分木の構築コードをシンプルにするために bin_tree! マクロを使ったものに差し替え。Add bin_tree! to create a new Node with less letters で @__gfx__氏からPRいただきました😂

二分木の説明

二分木は木構造の一種で、1つのノード（節点）が、0~2個の子ノードを持つものを指します。

バランスの良い二分木

       2
    __/ \__
   /       \
  7         5
 / \         \
2   6         9
   / \       /
  5  11     4

上の図のように、ルート（根: 親ノードを持たないノード）からリーフ（葉: 子ノードを持たないノード）までの深さがどこをとってもだいたい同じものを平衡二分木と言いますが、下のように深さがバラバラなものも二分木です。

バランスの悪い二分木

この記事では平衡二分木ではなく、一般の二分木について扱います。

Rustで定義する二分木

二分木の定義はどのように行うのが良いでしょうか？

木構造の定義の方法は、大まかに

子が親への参照（1つ）を持つ
親が子への参照（複数）を持つ

と分けられるかと思います。

前者の「子が親への参照を持つ」は二分木の定義に適していません。

間違った二分木の定義（擬似コード）

1
2
3

struct BinaryTree {
    parent: Option<BinaryTree>  // None はルートノード
}

この定義では、「親は子を2つ以下しか持たない」という制約が表現できていません。「子が親を参照するタイミングで、親がこの個数をカウントして、2個までしか認めないようにする」というような実装は可能ですが、あまり自然でもないしランタイムでのチェックが必要になってしまいます。

「親が子への参照を持つ」形式だと、「親は子を2つ以下しか持たない」制約を型レベルで（コンパイルタイムに）強制することができます。

二分木の定義（Optionを使う, 擬似コード）

struct BinaryTree {
    left: Option<BinaryTree>,  // None は、左側の子ノードがないことを表す
    right: Option<BinaryTree>,
}

だいぶ良くなってきました。ここで Option は、子の有無を表現するために使用しています。この定義でも十分実用に耐えますが、この有無を組み込みの型で表現するのではなく自前で定義すると、次のように定義できます。

二分木の定義（enumを使う, 擬似コード）

enum BinaryTree {
    Nil,  // 終端。子ノードが Nil ならば、子ノードを持たないことを表す。
    Node { left: BinaryTree, right: BinaryTree }
}

さて、これで二分木の外形は定義できましたが、各ノードが値を持てるようになっていません。各ノードが任意の型 T の値を持てるようにした完全な定義が下記になります。

二分木の定義

#[derive(Debug, PartialEq, Eq)]
pub enum BinaryTree<T> {
    Nil,
    Node {
        val: T,
        left: Box<BinaryTree<T>>,
        right: Box<BinaryTree<T>>,
    },
}

いくつか飛躍があるので説明しておきます。

#[derive(Debug, PartialEq, Eq)]
- assert_eq!(BinaryTree { ... }, BinaryTree { ... }) のように比較したいので、いくつかのTraitの実装を使う。
pub
- BinaryTree を定義したモジュールの外でも使いたいので公開する。
Box<BinaryTree<T>> （重要）
- left: BinaryTree<T> のように書きたくなるが、これでは再帰的な型定義となってしまい、 BinaryTree 型のサイズが確定できない（「 BinaryTree のサイズは… val のバイト数と、 left の BinaryTree のサイズを足して… ってそれを今計算してるのに😫」）。これを回避するために、”BinaryTree 型へのポインタ型” としてサイズが確定できるよう Box に包む。

これで二分木の型定義ができました。これからこの二分木に対する構築・追加・削除の操作や、深さ優先探索・幅優先探索のアルゴリズムを記述していきます。その後、実応用（？）として、いくつか LeetCode の問題を解いていきます。

データ構造への基本的な操作とアルゴリズム

構築

二分木の構築は、定義したenumを使って素直に初期化をするだけです。

構築

// 二分木の構築。
//
//       5
//      / \
//     4   8
//    /
//   11
//
let root = BinaryTree::<i32>::Node {
    val: 5,
    left: Box::new(BinaryTree::<i32>::Node {
        val: 4,
        left: Box::new(BinaryTree::<i32>::Node {
            val: 11,
            left: Box::new(BinaryTree::Nil),
            right: Box::new(BinaryTree::Nil),
        }),
        right: Box::new(BinaryTree::Nil),
    }),
    right: Box::new(BinaryTree::<i32>::Node {
        val: 8,
        left: Box::new(BinaryTree::Nil),
        right: Box::new(BinaryTree::Nil),
    }),
};

このように見た目が煩雑になってしまうので、構築用の new マクロを用意します。マクロ定義の方法は本記事の範疇を超えるので読み飛ばして良いですが、 bin_tree! マクロはこれ以降出てくるので、使い方だけでも把握してください。

構築用のマクロ定義

#[macro_export]
macro_rules! bin_tree {
    ( val: $val:expr, left: $left:expr, right: $right:expr $(,)? ) => {
        BinaryTree::Node {
            val: $val,
            left: Box::new($left),
            right: Box::new($right),
        }
    };

    ( val: $val:expr, right: $right:expr $(,)? ) => {
        bin_tree! {
            val: $val,
            left: bin_tree!(),
            right: $right,
        }
    };

    ( val: $val:expr, left: $left:expr $(,)? ) => {
        bin_tree! {
            val: $val,
            left: $left,
            right: bin_tree!(),
        }
    };

    ( val: $val:expr $(,)? ) => {
        bin_tree!(val: $val, left: bin_tree!(), right: bin_tree!(),)
    };

    () => {
        BinaryTree::Nil
    };
}

bin_tree! マクロの使い方

// 二分木の構築。
//
//       5
//      / \
//     4   8
//    /
//   11
//
let root = bin_tree! {
    val: 5,
    left: bin_tree! {
        val: 4,
        left: bin_tree! { val: 11 },
    },
    right: bin_tree! { val: 8 },
};

追加（置き換え）

子ノードの追加を考えます。これは、「左または右の子ノードが Nil であるときに、それを Node に置き換える」操作として記述できます。
Node が1つのノードでなくサブツリーのルートであれば、二分木に二分木を追加することになります。

汎用性の高い操作なので、メソッドとして定義しましょう。

追加（置き換え）

impl<T> BinaryTree<T> {
    /// self の Node または Nil を、 to に置き換える。
    /// to は self に組み込まれる形で move される。
    pub fn replace(&mut self, to: Self) {
        *self = to;
    }
}

テストしてみます。

replace() のテスト

#[test]
fn test_replace() {
    // tree1:
    //       5
    //      /
    //     4
    //    /
    //   11
    //  /  \
    // 7    2
    //
    // tree2:
    //         8
    //        / \
    //       13  4
    //            \
    //             1
    //
    // tree3 = tree1.root.right + tree2:
    //       5
    //      / \
    //     4   8
    //    /   / \
    //   11  13  4
    //  /  \      \
    // 7    2      1
    //

    // tree1 は後ほどルートの右のNilを置き換えるので、 mut でつくる。
    let mut tree1 = bin_tree! {
        val: 5,
        left: bin_tree! {
            val: 4,
            left: bin_tree! {
                val: 11,
                left: bin_tree! { val: 7 },
                right: bin_tree! { val: 2 },
            },
        },
    };

    let tree2 = bin_tree! {
        val: 8,
        left: bin_tree! { val: 13 },
        right: bin_tree! {
            val: 4,
            right: bin_tree! { val: 1 },
        },
    };

    let tree3 = bin_tree! {
        val: 5,
        left: bin_tree! {
            val: 4,
            left: bin_tree! {
                val: 11,
                left: bin_tree! { val: 7 },
                right: bin_tree! { val: 2 },
            },
        },
        right: bin_tree! {
            val: 8,
            left: bin_tree! { val: 13 },
            right: bin_tree! {
                val: 4,
                right: bin_tree!{ val: 1 },
            },
        },
    };

    if let BinaryTree::Node { right, .. } = &mut tree1 {
        // tree1のルートの右を、Nilからtree2のルートに置き換える。
        //
        // 型の解説:
        //   right: &mut Box<BinaryTree>
        //   *right: mut Box<BinaryTree>
        //   **right: mut BinaryTree
        //
        // replaceは &mut BinaryTree をセルフとして受け取るので (&mut **right).replace と書くのが明示的だが、
        // `.` 演算子が暗黙的に借用への変換を行ってくれる。
        (**right).replace(tree2);
    }
    assert_eq!(&tree1, &tree3);
}

削除

先程の replace() 関数を使って素直に実装できますね。

削除

impl<T> BinaryTree<T> {
    /// self の Node (または Nil) を Nil に置き換える。
    pub fn remove(&mut self) {
        self.replace(BinaryTree::Nil);
    }
}

深さ優先探索

深さ優先探索は、再帰関数を使うことで簡潔に実装することができます。1回1回の関数呼び出しであるノードを探索し、その中で左右の子ノードについても同じ関数を呼び出して探索します。

以下、二分木の中から 13 という値を探す再帰関数を擬似コードで記載します（コンパイルできるコードは下記の応用編で出てきます）。

13 を深さ優先探索で探す再帰関数（擬似コード）

fn find_13(cur_node: BinaryTree) -> bool {
    if cur_node.val == 13 { return true; }

    // 左の子ノードから再帰的に 13 を探索
    if cur_node.left != Nil {
        if find_13(cur_node.left) { return true; }  // left 以下に13があった場合
    }

    // 右の子ノードから再帰的に 13 を探索
    if cur_node.right != Nil {
        if find_13(cur_node.right) { return true; }  // right 以下に13があった場合
    }

    false  // cur_node 以下には 13 が見つからなかった
}

// 以下の二分木を構築。
//       5
//      / \
//     4   8
//    /   / \
//   11  13  4
//  /  \      \
// 7    2      1
//
let root = ...;

// 以下の順番で探索されて、最終的にtrueが返る。
//   5, 4, 11, 7, 2, 8, 13
assert!(find_13(root));

幅優先探索

幅優先探索は、FIFOなキューに左右の子ノードを順にpushしていき、それをpopしていくループによって実現できます。再帰を使った深さ優先探索のほうが直感的に記述できることが多いですが、以下のような場合は幅優先探索の利用を検討してみましょう。

二分木の中に答えを持つノードがいくつかあるが、深さが最も小さいノードを選択するのが重要なとき（最短経路問題）。
再帰関数を使うとスタック領域を多く使ってしまい、プロセスや言語のランタイムが持つスタック領域の上限を超えてしまう場合。
- この場合は、再帰を使わずに（データ構造としての）スタックとループを使う手もあります。

さて、深さ優先探索で見たのと同じ問題を幅優先探索で解いてみましょう。こちらも擬似コードですが、下記の応用編にコンパイルが通るコードがあります。

13 を幅優先探索で探す関数（擬似コード）

fn find_13(root: BinaryTree) -> bool {
    let mut queue = VecDeque::<BinaryTree>::new();  // ノードを入れるキューを用意
    queue.push_back(root);  // ルートをpushしてループ開始

    while let Some(cur_node) = queue.pop_front() {  // キューが空の場合は pop_front() は None を返すので、ループから抜ける
        if cur_node.val == 13 { return true; }

        if cur_node.left != Nil { queue.push_back(cur_node.left); }  // 左の子ノードがあればキューにpush
        if cur_node.right != Nil { queue.push_back(cur_node.right); }
    }

    false  // 13はどこにもなかった
}

// 以下の二分木を構築。
//       5
//      / \
//     4   8
//    /   / \
//   11  13  4
//  /  \      \
// 7    2      1
//
let root = ...;

// 以下の順番で探索されて、最終的にtrueが返る。
//   5, 4, 8, 11, 13
assert!(find_13(root));

応用編: LeetCode の問題を解いてみる

説明した操作やアルゴリズムで実際の問題が解決できることを例示するために、 LeetCode から以下の問題を取り上げます。

112. Path Sum
- 整数値をノード値に持つ二分木について、ルートからリーフまで値を足し算しながら辿っていき、その和が特定の数になるような辿り方があるかどうかを回答。構築と 深さ優先探索 または 幅優先探索 を使う。
814. Binary Tree Pruning
- 0 または 1 をノード値に持つ二分木について、すべてのノードが 0 であるようなサブツリーを切り落とす (prune) 操作をする。 構築・削除・深さ優先探索 を使う。

さて、LeetCode の問題のページにアクセスすればわかると思いますが、LeetCode ではRustを使って回答をすることもできます。LeetCode の二分木関連の問題では、二分木として以下の構造を使うことが求められます。

LeetCode で使う二分木

#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
  pub val: i32,
  pub left: Option<Rc<RefCell<TreeNode>>>,
  pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
  #[inline]
  pub fn new(val: i32) -> Self {
    TreeNode {
      val,
      left: None,
      right: None
    }
  }
}

Option<Rc<RefCell<TreeNode>>> といういかつい型が出てきました。

一番外側のOptionは、冒頭でも触れたように、子ノードの有無を表します。

（本記事の範疇を超えるので、この段落は読み飛ばしても良いです📝）
Rc<RefCell<...>> は、イディオムのように頻出する型です。Rustにおいて所有権は、通常たった一つの変数（や仮引数など）が持つものですが、Rc (Reference counting の略) を使えば複数の変数が所有権を持つことができるようになります。RefCell は内部可変性を導入するために利用する型です。 mut ではない struct であっても、 RefCell なフィールドだけは可変にできます。Rustにメモリ安全性を導入する「可変参照はたったひとつしか作れない」というコンパイルタイムの原則に対する抜け穴として RefCell があります。これを使うとコンパイルタイムでのメモリ安全性は保証されず、可変参照を2個以上作ったときにランタイムエラーが発生するようになるので、本当にどうしても必要で、かつ制御しきれる程度の仕事しかしない箇所で利用することをお勧めします。
二分木の各ノードを読むだけなら、共有参照で事足りるので、Rc<RefCell> は不要です。二分木をサブツリーに分けて扱い、同じノードに対する可変参照が複数個必要となるケースでは、 Rc<RefCell> が必要になるかもしれません。とはいえ、 Rc<RefCell> を導入する前に制御フローを工夫して、可変参照を1個以内に保てないかをまず検討するべきだと思います。

というわけで、今回は Option<Rc<RefCell<TreeNode>>> は使わず、最初に定義した

二分木の定義

#[derive(Debug, PartialEq, Eq)]
pub enum BinaryTree<T> {
    Nil,
    Node {
        val: T,
        left: Box<BinaryTree<T>>,
        right: Box<BinaryTree<T>>,
    },
}

を使います。LeetCodeで求められる型ではないのでSubmitはできませんが、代わりに簡単なテストコードを書いていきます。

112. Path Sum

整数値をノード値に持つ二分木について、ルートからリーフまで値を足し算しながら辿っていき、その和が特定の数になるような辿り方があるかどうかを回答する問題です。

解き方としては、愚直にルートからリーフまで足し算しながら辿っていって、リーフにたどり着いた時点で目指す総和になっていれば true を返せばよいです。

まずは深さ優先探索で回答してみます。テスト実行可能な形式で書いていきます。解説はコード内コメントで。

112. Path Sum - 深さ優先探索

#[test]
fn leetcode_112_path_sum_dfs() {
    use BinaryTree::{Nil, Node};

    // この関数を書き上げることが問題に対する回答。
    // 二分木のルートと、目指す総和を入力に取り、総和を実現する path が存在するかどうかを返却。
    pub fn has_path_sum(root: &BinaryTree<i32>, sum: i32) -> bool {

        // 再帰のヘルパー関数。「ルートから cur_node までたどってきました。今までの総和は cur_sum です。」という情報を引数に持つ。
        fn rec(cur_node: &BinaryTree<i32>, cur_sum: i32, sum: i32) -> bool {
            match cur_node {
                Nil => panic!("cur_node が Nil のときは呼び出さないでください"),

                // パターンマッチで、 cur_node の値、左右の子ノードを一気に束縛できる。
                Node { val, left, right } => {
                    let cur_sum = cur_sum + val;

                    // left の型は &Box<BinaryTree> となっている。& は cur_node が参照なので、 `match cur_node` で付いた。
                    // *left で Box<BinaryTree> となる。このままだと Box が邪魔で取り回しづらいので、
                    // **left で BinaryTree 型とする。ただしこれをそのまま使うと所有権が移動してしまうので、
                    // &(**left) として &BinaryTree 型を得る。
                    //
                    // ここは boxキーワード (https://doc.rust-jp.rs/the-rust-programming-language-ja/1.9/book/box-syntax-and-patterns.html) を使えばもっときれいに書ける。
                    match (&(**left), &(**right)) {
                        (Nil, Nil) => cur_sum == sum,  // Leafに到達しpathが完成したので、sumと比較
                        (_, Nil) => rec(&(*left), cur_sum, sum),  // 左の子があるので path 未完成。左の子も辿る。
                        (Nil, _) => rec(&(*right), cur_sum, sum),
                        (_, _) => rec(&(*left), cur_sum, sum) || rec(&(*right), cur_sum, sum),  // 左右の子どちらかが総和を満たす path を持っていれば十分。
                    }
                }
            }
        }

        // 探索開始
        rec(root, 0, sum)
    }

    // 二分木の構築。
    //
    //       5
    //      / \
    //     4   8
    //    /   / \
    //   11  13  4
    //  /  \      \
    // 7    2      1
    //
    let root = bin_tree! {
        val: 5,
        left: bin_tree! {
            val: 4,
            left: bin_tree! {
                val: 11,
                left: bin_tree! { val: 7 },
                right: bin_tree! { val: 2 },
            },
        },
        right: bin_tree! {
            val: 8,
            left: bin_tree! { val: 13 },
            right: bin_tree! {
                val: 4,
                right: bin_tree! { val: 1 },
            },
        },
    };

    // 総和が22になるpathは存在する。
    //
    //      *5*
    //      / \
    //    *4*   8
    //    /   / \
    //  *11*  13  4
    //  /  \      \
    // 7   *2*      1
    //
    assert_eq!(has_path_sum(&root, 22), true);
}

幅優先探索での回答は以下のように書けます。二分木の構築とassertion部分は省略。

112. Path Sum - 幅優先探索

#[test]
fn leetcode_112_path_sum_bfs() {
    use std::collections::VecDeque;
    use BinaryTree::{Nil, Node};

    pub fn has_path_sum(root: &BinaryTree<i32>, sum: i32) -> bool {
        // (今探索中のノード, 親ノードの値のここまでの総和) を格納するキュー
        let mut queue = VecDeque::<(&BinaryTree<i32>, i32)>::new();
        queue.push_back((root, 0));

        while let Some((cur_node, cur_sum)) = queue.pop_front() {
            match cur_node {
                Nil => {
                    panic!("Nil を queue に詰めないでください");
                }
                Node { val, left, right } => {
                    let cur_sum = cur_sum + val;

                    match (&(**left), &(**right)) {
                        // Leafに到達しpathが完成したので、sumと比較
                        (Nil, Nil) => {
                            if cur_sum == sum {
                                return true;
                            }
                        }

                        (_, Nil) => queue.push_back((&(*left), cur_sum)),
                        (Nil, _) => queue.push_back((&(*right), cur_sum)),
                        (_, _) => {
                            queue.push_back((&(*left), cur_sum));
                            queue.push_back((&(*right), cur_sum));
                        }
                    }
                }
            }
        }

        false // キューは空になったが、目指す総和のpathは見つからなかった
    }

    // 以下省略...
}

814. Binary Tree Pruning

0 または 1 をノード値に持つ二分木について、すべてのノードが 0 であるようなサブツリーを切り落とす (prune) 操作をする問題です。

素直に思いつくのは、「あるノードをルートとするサブツリーを考え、その全要素を探索し、全て0ならばそのサブツリーを切り落とす」という解法ですが、この方法ではリーフ近くのノードが何回も「0かどうか」チェックされて無駄があります。
“上から下に” ではなく、 “下から上に” 考えてみると、「あるノードがリーフのとき、自分が0ならば、自分自身をNilに置き換える」という解法がとれます。これだと0との比較の回数は、多くても全ノードの数だけになります。

この方針に従って、深さ優先探索で回答します。幅優先探索を使うと “下から上” な処理が書きづらいので、難儀するかと思います。

814. Binary Tree Pruning

#[test]
fn leetcode_814_binary_tree_pruning() {
    use BinaryTree::{Nil, Node};

    // この関数を書き上げることが問題に対する回答。
    // 二分木（サブツリー）のルートを入力に取り、左右の子ノードを再帰的に prune_tree() していく。
    // 自分自身が（左右の子を prune した結果、または最初から）リーフであった場合には、自分の値が0ならば、自分自身をNilに置き換える。
    // in-place で二分木を書き換えていく。
    pub fn prune_tree(root: &mut Box<BinaryTree<i32>>) {
        // 型の解説:
        //   root: &mut Box<BinaryTree>
        //   *root: mut Box<BinaryTree>
        //   **root: mut BinaryTree
        //   &mut **root: &mut BinaryTree
        match &mut **root {
            Nil => {}
            Node { val, left, right } => match (&mut **left, &mut **right) {
                (Nil, Nil) => {  // root 自身がリーフ
                    if *val == 0 {
                        root.remove();  // root を Nil に書き換える
                    }
                }
                (_, Nil) => {
                    prune_tree(left);
                    if let Nil = &mut **left {  // 左の子ノードを prune した結果、rootがリーフになった
                        if *val == 0 {
                            root.remove();
                        }
                    }
                }
                (Nil, _) => {
                    prune_tree(right);
                    if let Nil = &mut **right {
                        if *val == 0 {
                            root.remove();
                        }
                    }
                }
                (_, _) => {
                    prune_tree(left);
                    prune_tree(right);
                    if let (Nil, Nil) = (&mut **left, &mut **right) {
                        if *val == 0 {
                            root.remove();
                        }
                    }
                }
            },
        }
    }

    // 二分木の構築。
    //
    //       1
    //      / \
    //     /   \
    //    0     1
    //   / \   / \
    //  /   | |   \
    // 0    0 0    1
    //
    let mut tree = Box::new(bin_tree! {
        val: 1,
        left: bin_tree! {
            val: 0,
            left: bin_tree! { val: 0 },
            right: bin_tree! { val: 0 },
        },
        right: bin_tree! {
            val: 1,
            left: bin_tree! { val: 0 },
            right: bin_tree! { val: 1 },
        },
    });

    // prune_tree(tree) した結果の期待値。
    //
    //  1
    //   \
    //    1
    //     \
    //      1
    //
    let pruned = bin_tree! {
        val: 1,
        right: bin_tree! {
            val: 1,
            right: bin_tree! { val: 1 },
        },
    };

    assert_eq!(
        {
            prune_tree(&mut tree);
            *tree
        },
        pruned
    );
}

終わりに

この記事ではRustで二分木をシンプルに定義する方法と、二分木の構築・追加・削除、そして深さ優先探索と幅優先探索を紹介しました。

ただ、実用上ただの二分木はそんなに登場しません😂
しかし二分木は、二分探索木やヒープという、シンプルでありながら適用範囲の広いデータ構造のための基礎です。次回第2回では、二分探索木を紹介していきます。

この記事は FOLIO Advent Calendar 2019 の8日目の記事です。
12/23に8日目、開始は12/16でしょうか？（原稿落とした同僚の代打投稿です）

この遡及穴埋めもあり、どうやらFOLIOは今年もアドベントカレンダーを完走できそうです🎅🎄

俺とお前とlaysakura

二分木 - Rustではじめるデータ構造とアルゴリズム（第1回）

連載記事一覧

目次

更新履歴

二分木の説明

Rustで定義する二分木

データ構造への基本的な操作とアルゴリズム

構築

追加（置き換え）

削除

深さ優先探索

幅優先探索

応用編: LeetCode の問題を解いてみる

112. Path Sum

814. Binary Tree Pruning

終わりに