我正在研究二叉搜索树实现中的插入函数。这是我的代码:
pub struct Node {
data: i32,
left: Option<Box<Node>>,
right: Option<Box<Node>>
}
fn insert_at_root(mut root_node: Node, new_node: Node) -> Node { //not reference because root_node will be mutated
if root_node.data > new_node.data { // value less than root
if let Some(left) = root_node.left {
insert_node(*left, new_node); // *left is a way to downcast box, i.e. *left = T from Box<T>
}
else {
root_node.set_left(Some(Box::new(new_node)));
}
}
else if root_node.data < new_node.data {
if let Some(right) = root_node.right {
insert_node(*right, new_node);
}
else {
root_node.set_right(Some(Box::new(new_node)));
}
}
root_node
}
fn insert_node(mut exist_node: Node, new_node: Node) -> () {
if exist_node.data > new_node.data {
if let Some(left) = exist_node.left {
insert_node(*left, new_node);
}
else {
exist_node.set_left(Some(Box::new(new_node)));
}
}
else if exist_node.data < new_node.data {
if let Some(right) = exist_node.right {
insert_node(*right, new_node);
}
else {
exist_node.set_right(Some(Box::new(new_node)));
}
}
}
我有两个插入函数,因此当我调用 insert_at_node 时,我可以将变量与根节点一起保存。
我目前的问题是行
if let Some(left) = root_node.left {
(和行 if let Some(right) = root_node.right {
)在 insert_at_root
显然会导致移动的功能。结果无法返回root_node
在 insert_at_node
结尾:error[E0382]: use of moved value: `root_node`
--> src/lib.rs:34:5
|
19 | if let Some(left) = root_node.left {
| ---- value moved here
...
34 | root_node
| ^^^^^^^^^ value used here after partial move
|
= note: move occurs because value has type `std::boxed::Box<Node>`, which does not implement the `Copy` trait
error: aborting due to previous error
这些行的目的是检查
left
(或 right
)子节点不是 None
, 基本上 root_node.left != None
.有什么方法可以在不引起移动的情况下实现这一目标?也许有
!=
或 ==
符号。
最佳答案
你的问题不在于你测试是否left
/right
是 Some
或 None
.顺便说一句,可以通过测试来完成 .is_some()
和 .is_none()
.
您遇到的问题是您绑定(bind)了变量 left
到Node
那是在Option
.这样您就可以移动 Option
内容的所有权。到left
多变的。
通常,如果您不想移动所有权,则必须使用引用。当变量在 Option
中时并且您需要查看它作为引用,您必须将它的类型从 Option<T>
转换至Option<&T>
.当您查看选项时,它只是一个引用,因此不会移动所有权。Option
上有两个功能可用进行此转换:.as_ref()
转换为不可变引用,.as_mut()
转换为可变引用。因为要修改left
的内容你需要一个可变引用,所以 .as_mut()
如你所愿。
通过使用 .as_mut()
left
你得到的是一个引用而不是变量本身,所以没有所有权被转移。
您遇到的下一个问题是您无法将引用传递给 insert_node
。因为这个函数的类型签名需要获取变量而不是引用。那样的话,它需要你在这个辅助函数中传递所有权,所以它也不起作用。所以我们转换insert_node
的签名采取&mut Box<Node>
而不是 Node
.因此,我们再次仅获取引用而不是所有权。
pub fn insert_at_root(mut root_node: Node, new_node: Node) -> Node {
//not reference because root_node will be mutated
if root_node.data > new_node.data {
// value less than root
if let Some(left) = root_node.left.as_mut() {
insert_node(&mut *left, new_node);
} else {
root_node.set_left(Some(Box::new(new_node)));
}
} else if root_node.data < new_node.data {
if let Some(right) = root_node.right.as_mut() {
insert_node(&mut *right, new_node);
} else {
root_node.set_right(Some(Box::new(new_node)));
}
}
root_node
}
pub fn insert_node(exist_node: &mut Box<Node>, new_node: Node) -> () {
if exist_node.data > new_node.data {
if let Some(left) = exist_node.left.as_mut() {
insert_node(&mut *left, new_node);
} else {
exist_node.set_left(Some(Box::new(new_node)));
}
} else if exist_node.data < new_node.data {
if let Some(right) = exist_node.right.as_mut() {
insert_node(&mut *right, new_node);
} else {
exist_node.set_right(Some(Box::new(new_node)));
}
}
}
关于rust - 如何在 Option<T> 中访问 T 而不会导致移动?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/61291359/