algorithm - 广度优先搜索和生命周期

Question

我想写一个函数，在二叉树上使用广度优先搜索来按顺序打印节点值:

use std::collections::VecDeque;
use std::ops::Deref;

struct BinarySearchNode<'a> {
    value: &'a str,
    key: i32,
    left: Option<Box<BinarySearchNode<'a>>>,
    right: Option<Box<BinarySearchNode<'a>>>,
}

impl<'a> BinarySearchNode<'a> {
    pub fn print(&self) -> String {
        let mut queue = VecDeque::new();
        let mut output = String::new();
        queue.push_back(&self);

        while let Some(ref current) = queue.pop_front() {
            if let Some(left_node) = current.left {
                queue.push_back(&left_node.deref());
            }
            if let Some(right_node) = current.right {
                queue.push_back(&right_node.deref());
            }

            output = output + current.value + "\n";
        }

        output
    }
}

fn main() {}

我得到了错误

error: borrowed value does not live long enough
  --> src/main.rs:19:34
   |
19 |                 queue.push_back(&left_node.deref());
   |                                  ^^^^^^^^^^^^^^^^^ does not live long enough
   |
note: reference must be valid for the block suffix following statement 0 at 13:40...
  --> src/main.rs:13:41
   |
13 |         let mut queue = VecDeque::new();
   |                                         ^
note: ...but borrowed value is only valid for the statement at 19:16
  --> src/main.rs:19:17
   |
19 |                 queue.push_back(&left_node.deref());
   |                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
help: consider using a `let` binding to increase its lifetime
  --> src/main.rs:19:17
   |
19 |                 queue.push_back(&left_node.deref());
   |                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

error: `left_node` does not live long enough
  --> src/main.rs:19:34
   |
19 |                 queue.push_back(&left_node.deref());
   |                                  ^^^^^^^^^
   |
note: reference must be valid for the block suffix following statement 0 at 13:40...
  --> src/main.rs:13:41
   |
13 |         let mut queue = VecDeque::new();
   |                                         ^
note: ...but borrowed value is only valid for the if let at 18:12
  --> src/main.rs:18:13
   |
18 |             if let Some(left_node) = current.left {
   |             ^

error: borrowed value does not live long enough
  --> src/main.rs:22:34
   |
22 |                 queue.push_back(&right_node.deref());
   |                                  ^^^^^^^^^^^^^^^^^^ does not live long enough
   |
note: reference must be valid for the block suffix following statement 0 at 13:40...
  --> src/main.rs:13:41
   |
13 |         let mut queue = VecDeque::new();
   |                                         ^
note: ...but borrowed value is only valid for the statement at 22:16
  --> src/main.rs:22:17
   |
22 |                 queue.push_back(&right_node.deref());
   |                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
help: consider using a `let` binding to increase its lifetime
  --> src/main.rs:22:17
   |
22 |                 queue.push_back(&right_node.deref());
   |                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

error: `right_node` does not live long enough
  --> src/main.rs:22:34
   |
22 |                 queue.push_back(&right_node.deref());
   |                                  ^^^^^^^^^^
   |
note: reference must be valid for the block suffix following statement 0 at 13:40...
  --> src/main.rs:13:41
   |
13 |         let mut queue = VecDeque::new();
   |                                         ^
note: ...but borrowed value is only valid for the if let at 21:12
  --> src/main.rs:21:13
   |
21 |             if let Some(right_node) = current.right {
   |             ^

error[E0507]: cannot move out of borrowed content
  --> src/main.rs:18:38
   |
18 |             if let Some(left_node) = current.left {
   |                         ---------    ^^^^^^^ cannot move out of borrowed content
   |                         |
   |                         hint: to prevent move, use `ref left_node` or `ref mut left_node`

error[E0507]: cannot move out of borrowed content
  --> src/main.rs:21:39
   |
21 |             if let Some(right_node) = current.right {
   |                         ----------    ^^^^^^^ cannot move out of borrowed content
   |                         |
   |                         hint: to prevent move, use `ref right_node` or `ref mut right_node`

我需要 deref() 因为简单地使用运算符 * 会导致类型不匹配，因为它需要一个引用而不是一个框。似乎那些取消引用略有不同，至少在稳定的情况下我也不能解构它。

我知道这个值在 while 循环中的范围内并且没有足够长的时间存在于 VecDeque 中(如果这是正确的数据结构工作)，但我不确定延长生命周期的最佳方法是什么，或者是否有更好的方法来编写整个内容，因为它感觉有点复杂。

我的主要问题是我不确定从哪里开始重构这段代码，令人惊讶的是我很难找到在 Rust 中的二叉树上执行广度优先搜索以从中获取模式的示例。

Answer 1

你的主要问题在于这一行(和 right 版本):

if let Some(left_node) = current.left

这试图移动 current.left 中包含的值进入右侧的图案。问题是 current.left是一个 Option<Box<BinarySearchNode<'a>>> .当你移动 Box来自 current , 那会留下 current left 没有有效值!将来访问该值会导致不良行为。

相反，您需要将值保留在原处，取而代之的是引用。两种主要方法是使用 ref模式修饰符:

if let Some(ref left_node) = current.left

或调用 as_ref :

if let Some(left_node) = current.left.as_ref()

完整代码如下:

use std::collections::VecDeque;

struct BinarySearchNode<'a> {
    value: &'a str,
    key: i32,
    left: Option<Box<BinarySearchNode<'a>>>,
    right: Option<Box<BinarySearchNode<'a>>>,
}

impl<'a> BinarySearchNode<'a> {
    pub fn print(&self) -> String {
        let mut queue = VecDeque::new();
        let mut output = String::new();
        queue.push_back(self);

        while let Some(current) = queue.pop_front() {
            if let Some(left_node) = current.left.as_ref() {
                queue.push_back(left_node);
            }
            if let Some(right_node) = current.right.as_ref() {
                queue.push_back(right_node);
            }

            output = output + current.value + "\n";
        }

        output
    }
}

fn main() {
    let root = BinarySearchNode {
        value: "a",
        key: 0,
        left: Some(Box::new(BinarySearchNode {
            value: "b",
            key: 1,
            left: None,
            right: None,
        })),
        right: Some(Box::new(BinarySearchNode {
            value: "c",
            key: 2,
            left: None,
            right: None,
        })),
    };
    println!("{}", root.print());
}