バイナリ検索ツリーの再帰的なinorderトラバーサル

Question

バイナリ検索ツリー（BST）で再帰的なinorderを実装したいと思います。私は2つの構造体：NodeとTreeを使ってツリーを構築しました。私のコードは、これまでのところ、Node::inorderの型の不一致のために働いていません。

pub struct Node<T> { 
    value: T, 
    left: Option<Box<Node<T>>>, 
    right: Option<Box<Node<T>>>, 
} 

pub struct Tree<T> { 
    root: Option<Box<Node<T>>>, 
} 

impl<T: Ord> Tree<T> { 
    /// Creates an empty tree 
    pub fn new() -> Self { 
     Tree { root: None } 
    } 

    pub fn inorder(&self) -> Vec<&T> { 
     self.root.as_ref().map(|n| n.inorder()).unwrap() // how to pass result ? 
    } 
} 

impl<T: Ord> Node<T> { 
    pub fn inorder(&self) -> Vec<&T> { 
     let mut result: Vec<&T> = Vec::new(); 

     match *self { 
      None => return result, 

      Some(ref node) => { 
       let left_vec = node.left.inorder(); 
       result.extend(left_vec); 
       result.extend(node.value); 
       let right_vec = node.right.inorder(); 
       result.extend(right_vec); 
      } 
     } 
    } 
} 

これは、エラーレポートです：Node::inorderで

error[E0308]: mismatched types 
    --> src/main.rs:27:13 
    | 
27 |    None => return result, 
    |    ^^^^ expected struct `Node`, found enum `std::option::Option` 
    | 
    = note: expected type `Node<T>` 
    = note: found type `std::option::Option<_>` 

error[E0308]: mismatched types 
    --> src/main.rs:29:13 
    | 
29 |    Some(ref node) => { 
    |    ^^^^^^^^^^^^^^ expected struct `Node`, found enum `std::option::Option` 
    | 
    = note: expected type `Node<T>` 
    = note: found type `std::option::Option<_>` 

、私は、ノードが存在しない場合は、空のベクトルを返すようにしたいです。ノードが存在するならば、私はベクトルをinorderで成長させて再帰させたいと思う。 matchはNodeとOptionの間では機能しませんが、それらの間のブリッジ方法はわかりません。

Answer 1

問題は選択肢がどこにあるかについて混乱があるということです。ここで

impl<T: Ord> Node<T> { 
    pub fn inorder(&self) -> Vec<&T> { 
    //... 
    match *self { 

、selfはNode<T>、オプションではありません。代わりに、self.leftとself.rightはオプションです。

このコンパイル（main()の欠如まで）：

pub fn inorder(&self) -> Vec<&T> { 

    let mut result: Vec<&T> = Vec::new(); 

    if let Some(ref left) = self.left { 
     let left_vec = left.inorder(); 
     result.extend(left_vec); 
    } 
    result.push(&self.value); 
    if let Some(ref right) = self.right { 
     let right_vec = right.inorder(); 
     result.extend(right_vec); 
    } 
    result 
} 

Iはまた、リターンを添加し、そして代わりにpush参照result.extend(self.value)固定しました。

Playground

Answer 2

Chris Emerson's answer正しいですが、私はいつも同じベクトルに追加し、より多くのメモリ効率的なバージョンを提唱したいです。これにより、値の過剰コピーが防止されます。

impl<T> Tree<T> { 
    pub fn inorder(&self) -> Vec<&T> { 
     let mut nodes = Vec::new(); 
     if let Some(ref root) = self.root { 
      root.inorder(&mut nodes); 
     } 
     nodes 
    } 
} 

impl<T: Ord> Node<T> { 
    pub fn inorder<'a>(&'a self, result: &mut Vec<&'a T>) { 
     if let Some(ref left) = self.left { 
      left.inorder(result); 
     } 
     result.push(&self.value); 
     if let Some(ref right) = self.right { 
      right.inorder(result); 
     } 
    } 
} 

トラバースには不要なので、私は: Ordの制限を削除しました。

inorderを横断するイテレーターを作成することがより良い場合は、collectを呼び出すことができます。