我正在学习Rust,并尝试实现一个简单的二叉搜索树(实际上是重写了下面的Java实现)。
use std::cmp::Ordering;
// Node of this BST, the two generic types are key and value
struct Node<K:Ord, V> {
key: K,
value: V,
left: Option<Box<Node<K, V>>>,
right: Option<Box<Node<K, V>>>,
number_of_nodes: i32,
}
impl<K: Ord, V> Node<K, V> {
// Create a new node
fn new(key: K, value: V, number_of_nodes: i32) -> Node<K, V>{
Node {
key,
value,
left: None,
right: None,
number_of_nodes,
}
}
}
struct BST<K: Ord ,V> {
root: Option<Box<Node<K, V>>>,
}
impl<K: Ord, V> BST<K, V> {
// Get the size of this BST
fn size(&self) -> i32 {
size(&self.root)
}
// Search for key. Update value if found, otherwise insert the new node
fn put(&self, key: K, value: V) {
self.root = put(&self.root, key, value)
}
}
// Function for recursively get the size of a sub BST
fn size<K: Ord, V>(node: &Option<Box<Node<K, V>>>) -> i32 {
match node {
Some(real_node) => real_node.number_of_nodes,
None => 0,
}
}
// Function for recursively put a new node to this BST
fn put<K: Ord, V>(node: &Option<Box<Node<K, V>>>, key: K, value: V) -> &Option<Box<Node<K, V>>>{
match node {
None => {
let new_node = Some(Box::new(Node::new(key, value, 1)));
return &new_node;
},
Some(real_node) => {
match key.cmp(&real_node.key) {
Ordering::Less => real_node.left = *put(&real_node.left, key, value),
Ordering::Greater => real_node.right = *put(&real_node.right, key, value),
Ordering::Equal => real_node.value = value,
}
real_node.number_of_nodes = size(&real_node.right) + size(&real_node.left) + 1;
node
},
}
}
但是这段代码无法编译,在self.root = put(&self.root, key, value)
行,我得到一个错误:
不匹配的类型
需要枚举'选项框节点',但找到引用'&选项框节点'
我不知道如何修正这个问题,我试着将&self
参数改为self
,或者将self.root
改为*self.root
,但是我得到了更多的错误。我对Rust中的引用感到很困惑,我所要做的就是在Rust中重写下面的Java代码。
public class BST<Key extends Comparable<Key>, Value>
{
private Node root; //root of BST
private class Node
{
private Key key; // key
private Value val; // associated value
private Node right, left; // left and right subtrees
private int N; // number of nodes in subtree
public Node(Key key, Value val, int N)
{
this.key = key;
this.val = val;
this.N = N;
}
}
// Returns the number of key-value pairs in this symbol table.
public int size()
{
return size(root);
}
// Return number of key-value pairs in BST rooted at x
private int size(Node x)
{
if (x == null) return 0;
else return x.N;
}
public void put(Key key, Value val)
{
root = put(root, key, val);
}
private Node put(Node x, Key key, Value val)
{
if (x == null) return new Node(key, val, 1);
int cmp = key.compareTo(x.key);
if (cmp < 0) x.left = put(x.left, key, val);
else if (cmp > 0) x.right = put(x.right, key, val);
else x.val = val;
x.N = size(x.left) + size(x.right) + 1;
return x;
}
}
在Java
中非常简单,因为我不需要处理引用。
1.如何修复不匹配的错误?
1.递归函数put
,&Option<Box<Node<K, V>>>
或Option<Box<Node<K, V>>>
的正确返回类型是什么?有什么区别?
1.我重写Java
代码的方法正确吗?rust-analyzer只报告了这个不匹配的错误,但我不知道它是否会像我期望的那样工作。老实说,我不完全理解我在rust-analyzer中处理引用时在做什么,尤其是当它是struct或enum的引用时
这是很难学习 rust ,因为我没有太多的经验,在系统编程语言,我感谢你们的帮助:)
1条答案
按热度按时间toiithl61#
最简单的方法是使用一个对节点的可变引用:
注我更改了键相等时的插入行为,因为在原始Rust和Java代码中,即使没有插入新节点,存储节点数的变量也会递增。
或者,您可以通过值获取节点并返回修改后的节点:
如果你还没有读过这本书的话,我建议你阅读一读。