recursion - Rust 中的基本树和指针

Question

来自具有一些 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 库，但它似乎为我现在想要完成的事情引入了太多的复杂性，这是概念证明——尽管我可能会在应该爬行的时候尝试运行!

Answer 1

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

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

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

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

你的add_branch方法，你必须明白 self.add_branch是绑定(bind)到 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),
        }

如果您在这段代码中有任何不明白的地方，请大声疾呼，我会解释。