rust - 无法在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即可。那是一段很长的生存时间，这就是编译器正在生气的原因。

现在，如果仅从'a中删除&Vec，则编译器会提示其他问题:

   |
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上的错误。我们需要以不同的方式解决它。这里要了解的重要一点是，返回值不包含直接包含在nodes向量中的引用，但它确实包含nodes向量的内容(即&Node引用)的副本。我们需要告诉编译器，即使nodes引用的生命周期不是很长，但其内容的生命周期却更长。这就是我们在上面的修复程序中创建新的生命周期'b的原因。

从客观上来说，这是非常令人困惑的。就我个人而言，我宁愿避免解决这些棘手的问题，而只是让它们存活更长的时间，而不是确切地推测它们可以存活多长时间。困难的根源在于，我们在第39行上销毁了children向量。如果我们能够保留它，并保持清空并将其重新填充，Rust会给我们提供更轻松的时间。您是否考虑过在此处使用std::collections::VecDeque而不是Vec？您可以在while循环之外构造它一次，然后可以传递&mut children而不用担心它的生命周期。我认为队列通常是广度优先遍历的首选数据结构，后面添加了新的子级，遍历本身是从前端读取的。