如何制作树状结构，其中节点是 Rust 中的特征对象？

Question

我有一个 rust-playground link here，我的基本示例的完整代码是：

trait Obj {
    fn hit(&self, t0: f64, t1: f64) -> bool;
}

struct Leaf {
    data: f64,
}

impl Obj for Leaf {
    fn hit(&self, t0: f64, t1: f64) -> bool { return t0 < self.data && self.data < t1 }
}

struct Node<'a> {
    data: f64,
    left: &'a Box<dyn Obj>,
    right: &'a Box<dyn Obj>,
}

impl<'a> Obj for Node<'a> {
    fn hit(&self, t0: f64, t1: f64) -> bool {
        self.left.hit(t0, t1) || self.right.hit(t0, t1)
    }
}

impl<'a> Node<'a> {
    fn new(tmin: f64, tmax: f64) -> Self {
        let mid = (tmin + tmax) / 2.;
        if tmax - tmin < 1. {
            return Self { data: tmin, left: &Box::new(Leaf {data: tmin }), right: &Box::new(Leaf {data :tmax} ) };
        }
        let left = Node::new(tmin, mid);
        let right = Node::new(mid, tmax);
        Self {data: tmin, left: &Box::new(left), right: &Box::new(right) }
    }
}

fn main() {
    let node = Node::new(0., 100.);
    ()
}

这是一个人为的例子，但它给出了与我在真实版本中遇到的相同的编译器错误。在 Node 的构造函数中，出现以下错误：

error[E0308]: mismatched types
  --> src/main.rs:29:83
   |
29 |             return Self { data: tmin, left: &Box::new(Leaf {data: tmin }), right: &Box::new(Leaf {data :tmax} ) };
   |                                                                                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected trait object `dyn Obj`, found struct `Leaf`
   |
   = note: expected reference `&'a std::boxed::Box<(dyn Obj + 'static)>`
              found reference `&std::boxed::Box<Leaf>`

error[E0308]: mismatched types
  --> src/main.rs:33:33
   |
33 |         Self {data: tmin, left: &Box::new(left), right: &Box::new(right) }
   |                                 ^^^^^^^^^^^^^^^ expected trait object `dyn Obj`, found struct `Node`
   |
   = note: expected reference `&'a std::boxed::Box<(dyn Obj + 'static)>`
              found reference `&std::boxed::Box<Node<'_>>`

为什么会出现这些错误？ Leaf 和 Node 都实现了 Obj，我的理解是它们都可以是 dyn Obj 类型。我认为它与生命周期有关，但我想不出如何解决这个问题。在 Rust 中制作这种二叉树结构的正确方法是什么？

Answer 1

Box<..> 是一个拥有的类型，所以它可以独立存在，被移动而没有生命周期轨迹。在您的示例中，您只需删除所有引用和生命周期，因此结构定义变为：

struct Node {
    data: f64,
    left: Box<dyn Obj>,
    right: Box<dyn Obj>,
}

Here一个完整的例子。

如何制作树状结构，其中节点是 Rust 中的特征对象？

How can I make tree-like structure where the nodes are trait objects in Rust?

recursion

traits

rust