struct Node {
value: Option<i32>, // data feild
left: Option<Box<Node>>, // left child
right: Option<Box<Node>>, // right child
}
impl Node {
// search for a Node with key, and return the value or None
// root_Node {
// value: None,
// left: None,
// right: None,
// }
pub fn search(&self, x: Option<i32>) -> Option<i32> {
if self.left == None && self.right == None && self.value == None {
return None;
} else {
if x < self.value {
return self.left.search(x); // Error: No method search for std::option::Option<std::boxed::Box<Node>
} else if x > self.value {
return self.right.search(x); // Error: Same as above
} else {
return self.value;
}
}
}
I am reimplementing my DataStructure learning codes with Rust, this piece of code is for searching in a binary tree. I am new to Rust, not familiar with Rust syntax, Could you give a hint to me to unwrap it ?
The origin Option::unwrap() method leads to borrow error (self.left.unwrap().search(key))
if let Some(ref left) = self.left { left.search(…) }
== None does not unwrap, so you still need to convert Option<Node> to Node. You could use self.left.unwrap() after checking == None, but that is more error prone than if let.
Isn't that going to try moving the Box out of the Option? Instead, it should probably be "let Some(ref left) = ...". Alternatively, can probably use things like "self.left.as_ref().map(...)" to recurse into the subtrees without moving anything out.
Firstly, @impltrait, I don't quite understand your types and signatures. As with @leonardo, I expected a straight up i32 in there instead of an Option<i32>. So I'm going to change the signatures around a lot and write an implementation that more closely resembles Java or C++ where you would pass in a nullable tree Node and use it's nullness as the stopping condition on a failed search. In Rust, the equivalent of a nullable Node pointer is an Option<&Node>, so we'll write a helper function that works on that.
Since you said you're new, I added a bunch of comments to help explain what's going on.
pub struct Node {
value: i32,
left: Option<Box<Node>>,
right: Option<Box<Node>>,
}
pub fn search(opt_node: Option<&Node>, x: i32) -> Option<&Node> {
// Using `and_then()` instead of `map()` to avoid ending up
// with `Option<Option<&Node>>`.
// Both methods return `None` if `opt_node` is `None`.
opt_node.and_then(|node| {
if x < node.value {
// The first parameter undergoes these type transitions:
// Option<Box<Node>> (node.left)
// --as_ref--> Option<&Box<Node>>
// --map--> Option<&Node>
search(node.left.as_ref().map(|bx| bx.as_ref()), x)
} else if x > node.value {
search(node.right.as_ref().map(|bx| bx.as_ref()), x)
} else {
Some(node)
}
})
}
impl Node {
// Returns the `Node`, if any, where the i32 was found.
// There's no point returning the i32 itself. If you
// just want to indicate that a node was found, just return
// a `bool` and rename this method to `contains` instead.
pub fn search(&self, x: i32) -> Option<&Node> {
search(Some(self), x)
}
}
@marcianx @leonardo
I wrote value: Option<i32>, because I didn't know how to set the root to be None (without value, left and right). With value: Option<i32>, the value field can be set to None, that's the reason I do this. @marcianx Thank for you great explaination, it helps me a lot.