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 lib，但它似乎爲我現在要完成的任務引入了太多的複雜性，這是概念證明 - 儘管我可能會在嘗試爬行時嘗試運行！

Answer 1

我相信，你會用不同的數據表示做得更好：

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

這將是更容易使用並且會更有效（Option<~T>可以表示爲一個可空指針，而當前解決方案有一個葉節點仍然需要指針查找來檢查它是否爲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), 
     } 

如果有什麼事，你不要在這個代碼明白，只是霍勒，我會解釋它。