二叉搜索树的递归中序遍历 [英] Recursive inorder traversal of a binary search tree

问题描述

我想在二叉搜索树 (BST) 中实现递归中序.我使用两个结构构建了一棵树:Node 和 Tree.我的代码到目前为止还没有工作，主要是因为 Node::inorder 中的类型不匹配.

I want to implement a recursive inorder in a binary search tree (BST). I built a tree using two structs: Node and Tree. My code has not worked so far, mainly because of a type mismatch in 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 之间不起作用，但我不知道如何在它们之间建立桥接.

In Node::inorder, I want to return a empty vector if a node does not exist; if the node does exist, I want to grow the vector inorder and recur. The match doesn't work between a Node and Option, but I am not sure how to bridge between them.

推荐答案

问题在于选项在哪里存在混淆:

The problem is that there's confusion about where the options are:

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

这里，self 是一个 Node，而不是一个选项.相反，self.left 和 self.right 是选项.

Here, self is a Node<T>, not an option. Instead, self.left and self.right are options.

编译(直到缺少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 引用.

I also added the return, and fixed result.extend(self.value) to instead push a reference.

游乐场

这篇关于二叉搜索树的递归中序遍历的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！