递归遍历二叉查找树

问题描述：

我想在二叉查找树（BST）中实现递归inorder。我用两个结构构建了一棵树：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); 
      } 
     } 
    } 
}

这是错误报告：

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<_>`

在Node::inorder，我想如果一个节点不存在返回一个空载体;如果节点确实存在，我想按顺序增长矢量并重复。 match在Node和Option之间不起作用，但我不确定如何在它们之间搭桥。

您应该升级您的Rust版本以获得改进的错误消息。我已经与他们编辑了这个问题，因为他们也更容易阅读。 – Shepmaster

答

的问题是，有关于那里的选项有困惑：

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 
}

我还增加的返回，并固定到result.extend(self.value)代替push的参考。

Playground

答

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。

递归遍历二叉查找树

相关推荐