最近，我嘗試在 Rust 中實作二元樹資料結構。每棵二元樹都有一個根值，以及左、右子樹。我從這個相當直觀的 Python 實作開始。

class Tree:
  def __init__(self, val, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right

這讓我們可以像這樣宣告一個精巧的樹狀物件：

t = Tree(15,
      Tree(12,
           None,
           Tree(13)),
      Tree(22,
           Tree(18),
           Tree(100)))

結果可以用很漂亮的方式視覺化。
（對，這是我自己畫的。）

把那段程式碼移植到 Rust 卻有點……具有挑戰性。我的第一次嘗試看起來相當無害。

struct Tree {
  root: i64,
  left: Tree,
  right: Tree,
}

這幾乎就是 Python 定義的一對一翻譯——但rustc 說不行。

error[E0072]: recursive type `Tree` has infinite size
 --> src/main.rs:1:1
  |
1 | struct Tree {
  | ^^^^^^^^^^^ recursive type has infinite size
  |
  = help: insert indirection (e.g., a `Box`, `Rc`, or `&`) at some point to make `Tree` representable

對於來自記憶體代管語言（如 Python、PHP 或 Ruby）的人來說，我對此感到困惑。不過，這個問題其實很容易理解。電腦的記憶體是有限的。編譯器的工作就是要算出每個項目需要配置多少記憶體。

以我們的情況來說，它推斷如下：

一棵樹是一個包含一個 i64 和兩棵樹的結構。這兩棵樹中的每一棵，又是包含一個 i64 和兩棵樹的結構。每一棵……
你懂我的意思。

Tree { i64, Tree, Tree }
Tree { i64, Tree { ... }, Tree { ... } }
// The next expansion won't fit on the page anymore

既然我們不知道樹會有多少子樹，就無法事先判斷需要配置多少記憶體。我們要到執行時期才會知道！

Rust 告訴我們如何修正這個問題：插入像 Box、Rc 或 & 這樣的 indirection(間接層)。這些是 Rust 中不同的「pointer types(指標型別)」。它們都指向記憶體中的位置。因此，我們不需要知道樹狀結構的總大小，只需要知道樹在記憶體中的位置就好。但這就足以定義樹狀結構了。這些 pointer types 讓我們能夠安全地做到這一點，而無需手動進行記憶體管理。它們各自提供不同的保證，你應該選擇最符合你需求的那一個。

• & 在 Rust 的說法中稱為 borrow。它是三者中最常見的。它是對記憶體中某個位置的參照，但它並不擁有所指向的資料。因此，borrow 的生命週期取決於其擁有者。所以我們在這裡需要加入 lifetime parameters(生命週期參數)。這會讓使用上變得有點繁瑣。

  struct Tree<'a> {
    root: i64,
    left: &'a Tree<'a>,
    right: &'a Tree<'a>,
  }

• Box 是一種零執行時期開銷的 smart pointer(智慧指標)。它擁有其指向的資料，並將其儲存在 heap(堆積) 上。我們稱它為智慧的，是因為當它離開作用域時，會先釋放其指向的資料，然後再釋放自己。不需要手動進行記憶體管理，這很棒。✨

  struct Tree {
    root: i64,
    left: Box<Tree>,
    right: Box<Tree>,
  }

• Rc 是另一種 smart pointer。它是「reference-counting(參考計數)」的縮寫。它會在內部追蹤指向該資料結構的參照數量。一旦參照數量降為零，它就會自行清理。如果你需要在同一個執行緒中讓同一份資料擁有多個擁有者，請選擇 Rc。若需多執行緒，則還有 Arc（atomic reference count(原子參考計數)）。

  struct Tree {
    root: i64,
    left: Rc<Tree>,
    right: Rc<Tree>,
  }

把樹放進盒子裡

三種選項都完全可行。你該選擇哪一種，取決於你的使用情境。經驗法則是保持簡單。就我的情況而言，我選擇使用 Box，因為我不需要任何特殊的保證。

讓子樹成為可選的

接下來我遇到的問題是無法實例化樹狀結構。左、右子樹的型別是 Box<Tree>，但在某些時候我會需要一個空的子樹。

在 Python 的範例中，我使用 None 來標示資料結構的結尾。多虧了 Rust 的 Option 型別，我們也能做到同樣的事：

struct Tree {
  root: i64,
  left: Option<Box<Tree>>,
  right: Option<Box<Tree>>,
}

經過這些步驟後，我們就能建立第一棵樹：

Tree {
    root: 15,
    left: Some(Box::new(Tree {
            root: 12,
            left: None,
            right: Some(Box::new(Tree {
                    root: 13,
                    left: None,
                    right: None,
            })),
    })),
    right: Some(Box::new(Tree {
            root: 22,
            left: Some(Box::new(Tree {
                    root: 18,
                    left: None,
                    right: None,
            })),
            right: Some(Box::new(Tree {
                    root: 100,
                    left: None,
                    right: None,
            })),
    })),
};

取決於你的觀點，你可能會說這要麼是冗長，要麼是明確。相較於 Python 版本，以我的品味來說，它看起來有點太雜亂了。

我們能做得更好嗎？Chris McDonald（克里斯·麥克唐納） 幫我想出了以下的呈現方式：

Tree::new(15)
  .left(
    Tree::new(12)
      .right(Tree::new(13))
  )
  .right(
    Tree::new(22)
      .left(Tree::new(18))
      .right(Tree::new(100))
  );

對我來說，這樣看起來順眼多了。
以下是實現此效果的完整樹狀結構實作：

#[derive(Default)]
struct Tree {
  root: i64,
  left: Option<Box<Tree>>,
  right: Option<Box<Tree>>,
}

impl Tree {
  fn new(root: i64) -> Tree {
    Tree {
      root: root,
      ..Default::default()
    }
  }

  fn left(mut self, leaf: Tree) -> Self {
    self.left = Some(Box::new(leaf));
    self
  }

  fn right(mut self, leaf: Tree) -> Self {
    self.right = Some(Box::new(leaf));
    self
  }
}

更新： Danny Grein（丹尼·葛萊恩） 在 Twitter 上提到，透過實作 From<i64> for Tree，我們就能支援以下的語法：

root(15)
  .left(
    root(12)
      .right(13)
   )
  .right(
    root(22)
      .left(18)
      .right(100)
  );

為什麼在 Python 中就能直接運作？

現在你可能會好奇，為什麼我們的樹狀結構實作在 Python 中能如此完美地運作。原因是 Python 會在執行時期動態地為樹狀物件配置記憶體。此外，它會把所有東西都包裝在一個 PyObject 裡面，而它有點類似於上面提到的 Rc——一種 reference-counted smart pointer。

Rust 在這方面就明確多了。它讓我們在表達需求時更有彈性，但我們也需要了解所有可能的選項，才能善加利用。我的建議是，如果簡單的 borrow 就能滿足需求，就盡量別用 smart pointer。

然而，如果 lifetimes(生命週期)造成阻礙，或是你需要像是 thread-safety(執行緒安全性)這類額外的保證，smart pointer 就會是你的工具箱中很棒的補充。Rust 文件是進一步了解 smart pointer 的好起點。另外，也請閱讀 Idiomatic tree and graph-like structures in Rust（《Rust 中慣用的樹狀與圖狀結構》），了解在你的樹需要在執行時期可變的情況下，如何巧妙地運用 allocators(配置器)。