rust - 如何创建一个新的空树

Question

我有一个树，我想创建一个新的空树。我的第一个想法是:

struct Tree<T> {
    key: T,
    l: Option<Box<Tree<T>>>,
    r: Option<Box<Tree<T>>>,
}

impl<T: Ord> Tree<T> {
    /// Creates an empty tree
    pub fn new() -> Self {
        Tree {
            key: None, // error of mismatch type
            l: None,
            r: None,
        }
    }
}

我得到一个错误 Error: mismatched types [E0308]

是不是类型T不匹配类型None的问题？

Answer 1

我会做类似的事情:

type Tree<T> = Option<Box<TreeNode<T>>>;

struct TreeNode<T> {
    key: T,
    l: Tree<T>,
    r: Tree<T>,
}

现在创建一个空的 Tree 很容易(只是 None)，因为它是将两个 Tree 绑定(bind)到一个新的更大的树中。

如果您不喜欢 None-as-empty 或根树中的框，您可以添加包装器类型而不是别名 Tree，但是主要思想是相同的:将 Option 从左/右分支移动到节点类型中。