Rust 中的基本树和指针

我拥有一些 C 语言背景，尝试“学习”Rust 让我对自己的能力产生了质疑。我正在尝试找出如何更改拥有的指针，并且正在努力做到这一点。

除了从额外的库中复制之外，我无法弄清楚二叉树上所需的递归。特别是，我不知道如何交换指针分支。虽然使用链表我可以作弊并使用临时向量返回一个新列表，或者在列表头添加一个新的 Cons(value, ~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 指针实现一棵树没问题。

我想做的是就地更新指针——这是我使用它们的部分原因，对吗？——而不是每次我想要进行更改时都复制整个树。但我什至不知道如何联系他们。

我不确定如何使用结构而不是枚举来完成此操作。我查看了 Treemap 库，但它似乎给我现在想要完成的任务带来了太多的复杂性，这是概念证明——不过，当我应该爬行时，我可能会尝试运行！

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

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

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

您不需要实施您的eq方法;它可以导出，一个实现Eq特质，通过把#[deriving(Eq)]紧接在结构之前。

Of your 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),
        }

如果这段代码中有任何不明白的地方，请留言，我会解释的。