最近，我尝试在 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 是一个智能指针，零运行时开销。它拥有其指向的数据，并将其存储在堆上。我们称它为智能的，是因为当它离开作用域时，会先释放它指向的数据，然后再释放自身。无需手动管理内存，非常方便。✨

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

• Rc 是另一种智能指针，是 “reference-counting”（引用计数）的缩写。它在内部记录着指向该数据结构的引用数量。一旦引用数为零，它就会自行清理。如果你需要在同一个线程内让同一份数据拥有多个所有者，就选择 Rc。如果是多线程场景，还有 Arc（原子引用计数）可用。

  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”，里面有一些关于分配器的巧妙用法，适用于你的树需要在运行时可变的情况。