Рудиментарное дерево и указатели в ржавчине

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-указателей.

То, что я пытаюсь сделать, это обновить указатели на месте - это часть причины, по которой я их использую, правильно? Вместо того, чтобы копировать все дерево каждый раз, когда я хочу внести изменения , Но я даже не знаю, как добраться до них.

Я не уверен, как бы я сделал это с помощью структур, а не перечислений. Я просмотрел библиотеку 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 - это метод, связанный с 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), 
     } 

Если есть что-то вы не понимаете, в этом коде, просто кричите, и я объясню это.