Rust 二叉树插入实现难度

Question

我看了很多主题，但我找不到任何关于为什么我的代码无法编译的线索(当然除了所有权问题)，希望这里有人可以帮助我。

我正在研究二叉树实现，它的功能之一是插入 功能。这是我第一次用 Rust 编写代码，虽然我已经多次查看文档，但我无法弄清楚以下代码中的所有权有什么问题(我希望只发布所有相关代码):

#[derive(Debug)]
struct Data {
    name: String,
    age: i32,
}

#[derive(Debug)]
struct Node {
    value: Data,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

pub struct SortedContainer {
    root: Option<Box<Node>>,
}

impl SortedContainer {
    pub fn insert(&mut self, name: String, age: i32) {
        let d = Data {
            name: name,
            age: age,
        };
        let n = Node {
            value: d,
            left: None,
            right: None,
        };
        match self.root {
            Some(ref rootnode) => SortedContainer::node_insert(n, *rootnode),
            None => self.root = Some(Box::new(n)),
        }
    }
    fn node_insert(n: Node, mut n2: Box<Node>) {
        let i = SortedContainer::data_compare(&n.value, &n2.value);
        if i < 0 {
            match n2.right {
                Some(ref rightnode) => SortedContainer::node_insert(n, *rightnode),
                None => n2.right = Some(Box::new(n)),
            }
        } else if i > 0 {
            match n2.left {
                Some(ref leftnode) => SortedContainer::node_insert(n, *leftnode),
                None => n2.left = Some(Box::new(n)),
            }
        }
    }
    fn data_compare(d: &Data, d2: &Data) -> i32 {
        if d.age < d2.age {
            return -1;
        } else if d.age > d2.age {
            return 1;
        } else if d.name == d2.name {
            return 0;
        } else if d.name > d2.name {
            return 1;
        } else if d.name < d2.name {
            return -1;
        } else {
            return 0;
        }
    }
}

终端提供的错误是:

error[E0507]: cannot move out of borrowed content
  --> src/main.rs:31:67
   |
31 |             Some(ref rootnode) => SortedContainer::node_insert(n, *rootnode),
   |                                                                   ^^^^^^^^^ cannot move out of borrowed content

error[E0507]: cannot move out of borrowed content
  --> src/main.rs:39:72
   |
39 |                 Some(ref rightnode) => SortedContainer::node_insert(n, *rightnode),
   |                                                                        ^^^^^^^^^^ cannot move out of borrowed content

error[E0507]: cannot move out of borrowed content
  --> src/main.rs:44:71
   |
44 |                 Some(ref leftnode) => SortedContainer::node_insert(n, *leftnode),
   |                                                                       ^^^^^^^^^ cannot move out of borrowed content

它是否与 Box 或左/右分配有关？

Answer 1

您正在尝试将您的盒装节点移出它们的封闭选项。这是不允许的，因为之后选项仍然属于相应的父节点。理论上，您可以调用 take 选项来移动节点。 take 将值移出选项并将其替换为 None 而不是将其保留为“空”(不允许)。

但是，这会有效地将子节点从它们各自的父节点中分离出来。从插入新节点返回后，您必须重新附加它们:

fn node_insert(n: Node, mut n2: Box<Node>) -> Box<Node>{
    let i = SortedContainer::data_compare(&n.value, &n2.value);
    if i < 0 {
        n2.right = match n2.right.take() {
            Some(rightnode) => Some(SortedContainer::node_insert(n, rightnode)),
            None => Some(Box::new(n)),
        }
    } else if i > 0 {
        n2.left = match n2.left.take() {
            Some(leftnode) => Some(SortedContainer::node_insert(n, leftnode)),
            None => Some(Box::new(n)),
        }
    }
    n2
}

根节点相同:

self.root = match self.root.take() {
    Some(rootnode) => Some(SortedContainer::node_insert(n, rootnode)),
    None => Some(Box::new(n)),
}

另一种解决方案涉及将可变引用传递给节点而不是移动它们。这是有效的，因为您实际上只需要改变从根节点到应该插入新节点的叶节点路径上的节点:

fn node_insert(n: Node, n2: &mut Node) {
    let i = SortedContainer::data_compare(&n.value, &n2.value);
    if i < 0 {
        match n2.right {
            Some(ref mut rightnode) => SortedContainer::node_insert(n, rightnode),
            None => n2.right = Some(Box::new(n)),
        }
    } else if i > 0 {
        match n2.left {
            Some(ref mut leftnode) => SortedContainer::node_insert(n, leftnode),
            None => n2.left = Some(Box::new(n)),
        }
    }
}

根节点相同:

match self.root {
    Some(ref mut rootnode) => SortedContainer::node_insert(n, rootnode),
    None => self.root = Some(Box::new(n)),
}