So erstellen Sie einen neuen leeren Baum

Question

Ich habe eine Tree und ich möchte einen neuen leeren Baum erstellen. Mein erster Gedanke ist:

struct Tree<T> { 
    key: T, 
    l: Option<Box<Tree<T>>>, 
    r: Option<Box<Tree<T>>>, 
} 

impl<T: Ord> Tree<T> { 
    /// Creates an empty tree 
    pub fn new() -> Self { 
     Tree { 
      key: None, // error of mismatch type 
      l: None, 
      r: None, 
     } 
    } 
} 

Ich erhalte eine Fehlermeldung von Error: mismatched types [E0308]

Ist es ein Problem vom Typ T nicht Typ passenden None?

Answer 1

ich würde so etwas tun zu geben:

type Tree<T> = Option<Box<TreeNode<T>>>; 

struct TreeNode<T> { 
    key: T, 
    l: Tree<T>, 
    r: Tree<T>, 
} 

Jetzt Erstellen einer leeren Tree ist einfach (nur None), wie es ist, zwei Tree s zu einem neuen größeren zu binden. Bewegen Sie den Option von links:

Wenn Sie die None -as-leer oder das Feld im Stammbaum nicht mögen, können Sie einen Wrapper-Typ anstelle des Alias ​​Tree, aber die Grundidee ist die gleiche hinzufügen/rechts verzweigt in den Knotentyp.

Answer 2

Mit key: T fragen Sie explizit nach einem Wert vom Typ T. Was Sie bei der Initialisierung gab (key: None) ist ein Option<U>, Sie müssen es einen gewissen Wert geben, zum Beispiel durch new zu

pub fn new(t: T) -> Self { 
    Tree { 
     key: t, 
     l: None, 
     r: None, 
    } 
} 

Alternativ zu ändern, wenn Sie auch die Möglichkeit, manchmal haben Schlüssel möchten, und manchmal nicht können Sie das key Feld ändern Option<T>

Answer 3

Warum machen Sie nicht Ihre Tree eine enum anstelle einer Struktur?

würde ich eine binäre Tree wie folgt erstellen:

enum Tree<T> { 
    Empty, 
    Node { 
     val: T, 
     l: Box<Tree<T>>, 
     r: Box<Tree<T>>, 
    }, 
} 

Sie dann es wie folgt implementieren könnte:

impl<T: Ord> Tree<T> { 
    fn empty() -> Self { 
     Tree::Empty 
    } 
    fn singleton(val: T) -> Self { 
     Tree::Node { 
      val: val, 
      l: Box::new(Tree::Empty), 
      r: Box::new(Tree::Empty), 
     } 
    } 
}