Kanonische Implementierung von veränderbaren Bäumen

Question

Ich habe vor kurzem begonnen, ein kleines Grafikprogramm von C++ nach Rust zu portieren. In diesem nutze ich einen Quad-Tree-Store dynamisch erstelltes Terrain. Je nach LOD und Position werden Knoten hinzugefügt und aus dem Baum entfernt. Angenommen, ich verwende ein Enum zur Darstellung des Baumes, was ist der beste Ansatz zum Hinzufügen und Entfernen von Knoten?

Answer 1

Würde etwas in dieser Richtung für Sie arbeiten? Dies ist ein generischer Baum, den ich gerade als Beispiel gemacht habe, aber Sie können den dynamischen Vektor (Vec) durch einen festen ersetzen, wenn das Ihr Domain-Problem ist (Quad-Tree).

use std::slice::Items; 

enum Node<V> { 
    Parent(Vec<Node<V>>), 
    Leaf(V), 
} 

struct NodeIter<'a, V> { 
    stack: Vec<Items<'a,Node<V>>>, 
} 

impl<'a, V> NodeIter<'a, V> { 
    fn from(node: &'a Node<V>) -> NodeIter<'a, V> { 
     let mut stack = Vec::new(); 
     match node { 
      &Parent(ref children) => stack.push(children.iter()), 
      &Leaf(_) =>() 
     } 
     NodeIter { 
      stack: stack 
     } 
    } 
} 

impl<'a, V> Iterator<&'a V> for NodeIter<'a, V> { 
    fn next(&mut self) -> Option<&'a V> { 
     while !self.stack.is_empty() { 
      match self.stack.mut_last().unwrap().next() { 
       Some(&Parent(ref vec)) => { 
        self.stack.push(vec.iter()); 
       }, 
       Some(&Leaf(ref v)) => { 
        return Some(v) 
       }, 
       None => { 
        self.stack.pop(); 
       } 
      } 
     } 
     None 
    } 
} 

impl<V> Node<V> { 
    fn append<'a>(&'a mut self, n: Node<V>) -> Option<&'a mut Node<V>> { 
     match self { 
      &Parent(ref mut children) => { 
       let len = children.len(); 
       children.push(n); 
       Some(children.get_mut(len)) 
      }, 
      &Leaf(_) => None, 
     } 
    } 

    fn retain_leafs(&mut self, f: |&V|->bool) { 
     match self { 
      &Parent(ref mut children) => { 
       children.retain(|node| match node { 
        &Parent(_) => true, 
        &Leaf(ref v) => f(v), 
       }) 
      }, 
      &Leaf(_) =>(), 
     } 
    } 

    fn iter<'a>(&'a self) -> NodeIter<'a, V> { 
     NodeIter::from(self) 
    } 
} 


fn main() { 
    let mut tree: Node<int> = Parent(Vec::new()); 
    { 
     let b1 = tree.append(Parent(Vec::new())).unwrap(); 
     b1.append(Leaf(1)); 
     b1.append(Leaf(2)); 
     b1.retain_leafs(|v| *v>1); 
    } 
    { 
     let b2 = tree.append(Parent(Vec::new())).unwrap(); 
     b2.append(Leaf(5)); 
     b2.append(Leaf(6)); 
    } 

    for val in tree.iter() { 
     println!("Leaf {}", *val); 
    } 
}