Как создать новое пустое дерево

Question

У меня есть Tree, и я хочу создать новое пустое дерево. Моя первая мысль:

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, 
     } 
    } 
} 

Я получаю ошибку Error: mismatched types [E0308]

это проблема типа T, не соответствующего типа None?

Answer 1

Я хотел бы сделать что-то вроде:

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

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

Теперь создание пустой Tree легко (просто None), так как он связывает два Tree s с новым большим.

Если вы не любите None -по пустым или поле в корневом дереве, вы можете добавить тип обертки вместо псевдонима Tree, но основная идея та же: переместить Option слева/right в тип узла.

Answer 2

С key: T вы явно запрашиваете значение типа T. То, что вы дали в инициализации (key: None) является Option<U>, вы должны дать ему некоторое значение, например, путем изменения new к

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

В качестве альтернативы, если вы хотите иметь возможность иногда имеют ключи, а иногда нет , вы можете изменить key поле для ввода Option<T>

Answer 3

Почему вы не делаете свой Tree перечислением вместо структуры?

Я бы создать двоичный Tree так:

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

Вы могли бы реализовать это следующим образом:

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), 
     } 
    } 
}