最近，我嘗試在 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 或 &。這些是 Rust 中不同的「指標型別」。它們都指向記憶體中的某個位置。所以，我們不需要知道整個樹狀結構的總大小，只需要知道樹在記憶體中的位置就好。但這樣就足以定義樹的結構了。這些指標型別讓我們能夠安全地做到這一點，而且不需要手動管理記憶體。它們各自提供不同的保證，你應該選擇最符合你需求的那一個。

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

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

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

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

• Rc 是另一種智慧指標，全名是「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——一種參照計數的智慧指標。

Rust 在這方面則明確得多。它給了我們更多彈性來表達需求，但我們也需要了解所有可能的選項，才能好好運用它們。我的建議是，如果簡單的借用就能解決，就盡量別用智慧指標。

然而，如果生命週期造成了阻礙，或是你需要執行緒安全這類額外的保證，智慧指標就是你工具箱中一個很棒的利器。Rust 官方文件是深入了解智慧指標的一個很好的起點。另外，如果你的樹需要在執行時期可變，也可以閱讀 「Idiomatic tree and graph-like structures in Rust」，裡面介紹了一些巧妙運用配置器（allocator）的方法。