Rust中的Rudimentary Tree和Pointers

Question

来自脚本语言背景和一些C,试图"学习"Rust让我质疑我的能力.我正在试图找出如何更改自有指针,并努力做到这一点.

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

我正在尝试做的是就地更新指针 - 这是我使用它们的部分原因,对吧？ - 而不是每次我想要进行更改时复制整个树.但我甚至不知道如何去找他们.

我不确定如何用结构而不是枚举来做这件事.我看过Treemap lib,但它似乎为我现在想要完成的事情引入了太多的复杂性,这是概念的证明 - 我可能会尝试在我应该爬行时运行!

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是一个绑定的方法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),
        }

如果你在这段代码中有任何你不理解的东西,那就大声说道,我会解释一下.