《铁锈》中的Rudimentary Tree和Pointers

Question

来自脚本语言背景，有一些C语言，试图"学习"Rust让我质疑自己的能力。我正试图弄清楚如何更改拥有的指针，但很难做到

除了从额外的库中复制外，我还无法计算出二进制树上需要的递归。特别是，我不知道如何交换指针分支。而对于链表，我可以作弊并使用临时向量返回一个新列表，或者在列表头前加一个新的Cons(值，~Cons)，分支让我感到困惑。

enum NaiveTreeNode {
NNil,
NNode(~NaiveTreeNode, ~NaiveTreeNode, int, char) 
//         left            right          key   val
}
impl NaiveTreeNode {
fn eq(first_node: &NaiveTreeNode, second_node: &NaiveTreeNode) -> bool {
match (first_node, second_node) {
(&NNil, &NNil)              => true,
( &NNode( ~ref left_lval, ~ref left_rval, left_leafkey, left_leafval ),
&NNode( ~ref right_lval, ~ref right_rval, right_leafkey, right_leafval )
) if left_leafkey == right_leafkey && left_leafval == right_leafval => {
NaiveTreeNode::eq(left_lval, right_lval) && NaiveTreeNode::eq(left_rval, right_rval)
},
_                           => false
}
}
fn add_branch(&mut self, node_to_add: ~NaiveTreeNode) {
match (self, node_to_add) {
(&NaiveTreeNode(~NNil, ~ref r_branch, leaf_key, leaf_val), ~NaiveTreeNode(_, _, new_node_key, _)              )
if leaf_key > new_node_key   => self = &NaiveTreeNode(node_to_add, *r_branch, leaf_key, leaf_val),
(&NaiveTreeNode(~ref l_branch, ~NNil, leaf_key, leaf_val), ~NaiveTreeNode(_, _, new_node_key, _))
if leaf_key < new_node_key  => self = &NaiveTreeNode(*l_branch, node_to_add, leaf_key, leaf_val),
(&NaiveTreeNode(~ref l_branch, _, leaf_key, _), ~NaiveTreeNode(_, _, new_node_key, _)) 
if leaf_key > new_node_key  => self.add_branch(l_branch, node_to_add),
(&NaiveTreeNode(_, ~ref r_branch, leaf_key, _), ~NaiveTreeNode(_, _, new_node_key, _)) 
if leaf_key < new_node_key  => self.add_branch(l_branch, node_to_add),
(_, ~NNil)                       => fail!("NNil branch. failing"),
(&NNil, _)                       => fail!("NNil trunk. failing"),
_                                => fail!("something is wrong. failing.")
};
}
}

编译器在这上面抛出了11个错误，当我键入它时，感觉就像伪代码。我很沮丧，因为我觉得用C指针实现树是可以的。

我想做的是更新指针——这也是我使用它们的部分原因，对吧--而不是每次我想更改时都复制整棵树。但我甚至不知道如何找到他们。

我不确定如何使用structs而不是enum来实现这一点。我看过Treemap库，但它似乎给我现在想要完成的任务带来了太多的复杂性，这就是概念的证明——不过，我可能正在尝试在应该爬行的时候运行！

Answer 1

我相信使用不同的数据表示会做得更好：

struct NaiveTreeNode {
left: Option<~NaiveTreeNode>,
right: Option<~NaiveTreeNode>,
key: int,
val: char,
}

这将更容易使用，并且效率略高(Option<~T>可以表示为可为null的指针，而您当前的解决方案有一个叶节点，仍然需要查找指针来检查它是否为NNil)。

您不需要实现eq方法；它可以通过将#[deriving(Eq)]直接放在结构之前来派生，这是Eq特性的实现。

关于add_branch方法，您必须了解self.add_branch是绑定到self的方法。当您调用self.add_branch(l_branch, node_to_add)时，这是无效的，因为您将两个参数传递给一个，而不是一个。你的意思是l_branch.add_branch(node_to_add)。

我对add_branch方法进行了重大的重组；这是我要写的完整代码：

#[deriving(Eq)]
struct NaiveTreeNode {
left: Option<~NaiveTreeNode>,
right: Option<~NaiveTreeNode>,
key: int,
val: char,
}
impl NaiveTreeNode {
fn add_branch(&mut self, node: ~NaiveTreeNode) {
match (self.key.cmp(node.key), self.left, self.right) {
(Greater, None, _) => self.left = Some(node),
(Greater, Some(~ref mut left), _) => left.add_branch(node),
(Less, _, None) => self.right = Some(node),
(Less, _, Some(~ref mut right)) => right.add_branch(node),
(Equal, _, _) => fail!("this tree already has a node with key {} 
(value {}, attempted value {})", 
self.key, self.value, node.value),
}
}
}

如果你愿意，匹配也可以扩展到以下内容：

match self.key.cmp(node.key) {
Greater => match self.left {
None => self.left = Some(node),
Some(~ref mut left) => left.add_branch(node),
},
Less => match self.right {
None => self.right = Some(node),
Some(~ref mut right) => right.add_branch(node),
},
Equal => fail!("this tree already has a node with key {} 
(value {}, attempted value {})", 
self.key, self.value, node.value),
}

如果你在这段代码中有什么不明白的地方，只要喊一声，我就会解释。