无法对 Rust 中的二叉树进行广度优先搜索

Question

作为一个学习项目，我已经在 Rust 中实现了一个二叉树，但未能横穿它以以广度优先搜索方式打印树。

问题是我无法重新分配搜索队列 (children)，因为它是借用的，而且寿命不够长。

https://gist.github.com/varshard/3874803cd035e27facb67c59e89c3c1c#file-binary_tree-rs-L39

我该如何纠正？

use std::fmt::Display;

type Branch<'a, T> = Option<Box<Node<'a, T>>>;

struct Node<'a, T: PartialOrd + Display> {
    value: &'a T,
    left: Branch<'a, T>,
    right: Branch<'a, T>
}

impl<'a, T: PartialOrd + Display> Node<'a, T> {
    fn insert(&mut self, value: &'a T) {
        let target_node = if value > self.value { &mut self.right } else { &mut self.left };
        match target_node {
            Some(ref mut node) => node.insert(value),
            None => {
                let new_node = Node{ value: value, left: None, right: None};
                *target_node = Some(Box::new(new_node))
            }
        }
    }
    fn display(&'a self) {
        let mut children: Vec<Option<&Node<'a, T>>> = Vec::new();
        children.push(Some(self));

        while children.len() > 0 {
            for child in &children {
                match child {
                    Some(node) => {
                        print!("{} ", node.value);
                    },
                    None => {
                        print!(" ")
                    }
                }
            }
            println!("");
            // Error: children doesn't live long enough;
            children = self.to_vec(&children);
        }
    }
    fn to_vec(&self, nodes: &'a Vec<Option<&Node<'a, T>>>) -> Vec<Option<&Node<'a, T>>> {
        let mut children: Vec<Option<&Node<'a, T>>> = Vec::new();
        for node_option in nodes {
            match node_option {
                Some(node) => {
                    match &node.left {
                        Some(left) => {
                            children.push(Some(left));
                            match &node.right {
                                Some(right) => {
                                    children.push(Some(right));
                                },
                                None => {
                                    children.push(None);
                                }
                            }
                        },
                        None => {
                            children.push(None);
                            match &node.right {
                                Some(right) => {
                                    children.push(Some(right));
                                },
                                None => {
                                    children.push(None);
                                }
                            }
                        }
                    }
                },
                None => {}
            }
        }

        children
    }
}

fn main() {
    let root_val = 5;
    let mut root = Node{ value: &root_val, left: None, right: None };
    root.insert(&3);
    root.insert(&4);
    root.insert(&1);
    root.insert(&6);

    root.display();
}

Answer 1

正在从 this reddit comment 复制我的答案：

有一种方法可以直接解决您的问题，但我认为还有更好的选择可以使代码更易于编写和理解。对于直接修复，您可以进行一些生命周期调整。而不是

fn to_vec(&self, nodes: &'a Vec<Option<&Node<'a, T>>>) -> Vec<Option<&Node<'a, T>>> {

你需要：

fn to_vec<'b>(&self, nodes: &Vec<Option<&'b Node<'a, T>>>) -> Vec<Option<&'b Node<'a, T>>>

有什么区别？在第一种情况下，我们说 nodes 是 &'a Vec。也就是说，借用 Vec 与树中的 value 引用一样长。那是很长的时间，这也是编译器生气的原因。

现在，如果您只是从 &Vec 中删除 'a，编译器会抱怨其他事情：

   |
42 |     fn to_vec(&self, nodes: &Vec<Option<&Node<'a, T>>>) -> Vec<Option<&Node<'a, T>>> {
   |                                         ------------       -------------------------
   |                                         |
   |                                         this parameter and the return type are declared with different lifetimes...
...
76 |         children
   |         ^^^^^^^^ ...but data from `nodes` is returned here

也许这是促使您首先将 'a 放在 &Vec 上的错误。我们需要以不同的方式解决它。这里要理解的重要一点是 return 值不包含直接指向 nodes 向量的引用，但它确实包含 nodes 向量内容的副本，&Node 参考。我们需要告诉编译器即使 nodes 引用不会存活很长时间，它的内容 do 会存活更长时间。这就是我们在上面的修复中创建新生命周期 'b 的原因。

这在客观上非常令人困惑。就个人而言，我更愿意避免解决这些棘手的问题，只是让事物存活得更久，而不是推理它们究竟能活多久。困难的根源在于我们正在破坏第 39 行的 children 向量。如果我们能够保留它，并且只是不断地清空它并重新填充它，Rust 会给我们一个更容易的时间。您是否考虑过在此处使用 std::collections::VecDeque 而不是 Vec？您可以在 while-loop 之外构建它一次，然后您可以传递 &mut children，而不用太担心它的生命周期。我认为队列通常是 breadth-first 遍历的 go-to 数据结构，新的 children 添加到后面，遍历本身从前面读取。

无法对 Rust 中的二叉树进行广度优先搜索

Can't do breadth-first search on a binary tree in Rust

binary-tree

rust