从格式化输入构建树

Question

我在尝试提出一种解决方案以从格式化输入中读取二叉树并在 Rust 中构建所述树时遇到了问题。借款检查员一直在发疯，因此决定带到社区。

基本上，输入是这样的：

1 2 3 4 5 6 N N 7 8

它代表一棵看起来像这样的树：

            1
         /     \
        2       3
      /   \   /   \
     4     5 6     N
    / \   /
   N   7 8

N 表示 NULL。

为了阅读这篇文章，在 CPP 中，我通常会按级别阅读这棵树，使用队列进行树的广度优先构建。我在 Rust 中尝试了相同的方法，但那是我失败的地方。我是Rust的初学者，当然被借用检查员骂了。

我正在使用以下 TreeNode 结构：

#[derive(Debug, PartialEq, Eq)]
 pub struct TreeNode {
   pub val: i32,
   pub left: Option<Rc<RefCell<TreeNode>>>,
   pub right: Option<Rc<RefCell<TreeNode>>>,
 }

 impl TreeNode {
   #[inline]
   pub fn new(val: i32) -> Self {
     TreeNode {
       val,
       left: None,
       right: None
     }
   }
}

下面是从 STDIN 读取树的代码片段：

fn read_b_tree<T: io::BufRead>(scan: &mut Scanner<T>, size: usize)
                               -> Result<Option<Rc<RefCell<TreeNode>>>, Box<dyn Error>> {
    if size == 0 {
        Ok(None)
    } else {

        let r = scan.token::<String>();
        if r == "N" {
            Ok(None)
        } else {
            let mut q = VecDeque::new();
            let root = Rc::new(RefCell::new(TreeNode::new(r.parse::<i32>()?)));
            q.push_back(&root);

            let mut cnt: usize = 1;
            while cnt < size && !q.is_empty() {
                let node = match q.pop_front() {
                    Some(node) => Ok(node),
                    _ => Err("Queue should not be empty"),
                }?;

                let v = Rc::clone(node);

                let left = scan.token::<String>();
                let right = scan.token::<String>();

                if left != "N" {
                    let left_n = Rc::new(RefCell::new(TreeNode::new(left.parse::<i32>()?)));
                    v.borrow_mut().left = Some(Rc::clone(&left_n));
                    q.push_back(&left_n);
                }
                cnt += 1;

                if right != "N" {
                    let right_n = Rc::new(RefCell::new(TreeNode::new(right.parse::<i32>()?)));
                    v.borrow_mut().right = Some(Rc::clone(&right_n));
                    q.push_back(&right_n);
                }
                cnt += 1;
            }
            Ok(Some(root))
        }
    }
}

如您所想，我运行使用这种方法解决了生命周期问题，例如：

error[E0597]: `right_n` does not live long enough
   --> src/main.rs:146:33
    |
125 |             while cnt < size && !q.is_empty() {
    |                                  - borrow later used here
...
146 |                     q.push_back(&right_n);
    |                                 ^^^^^^^^ borrowed value does not live long enough
147 |                 }
    |                 - `right_n` dropped here while still borrowed

如果有人能就我如何解决这种情况提供一些建议，我将非常感谢。

此致，

Answer 1

以下代码更短并演示了您的问题：

fn read_b_tree() -> Result<Option<Rc<RefCell<TreeNode>>>, Box<dyn Error>> {
  let r = String::new();
  let mut q = VecDeque::new();
  let root = Rc::new(RefCell::new(TreeNode::new(r.parse::<i32>()?)));
  q.push_back(&root);
  while !q.is_empty() {
    if r != "N" {
      let left_n = Rc::new(RefCell::new(TreeNode::new(r.parse::<i32>()?)));
      q.push_back(&left_n);
    }
  }
  Ok(Some(root))
}

q的推断类型是VecDeque<&Rc<RefCell<TreeNode>>>，但是你没有理由选择这个而不是VecDeque<Rc<RefCell<TreeNode>>>（Rc而不是&Rc） - Rc已经是一个参考所以没有必要再做一次。

我认为您插入了 &，因为没有 & 就会出现错误 use of moved value ...。此错误是正确的：您在将 root 移动到 q 之后使用它。但这不是问题，因为您想将 Rc 移动到 q，只需克隆它 root.clone() 或 Rc::clone(&root).[=26 即可轻松获得一个新的=]

固定示例为：

fn read_b_tree() -> Result<Option<Rc<RefCell<TreeNode>>>, Box<dyn Error>> {
  let r = String::new();
  let mut q = VecDeque::new();
  let root = Rc::new(RefCell::new(TreeNode::new(r.parse::<i32>()?)));
  q.push_back(root.clone());
  while !q.is_empty() {
    if r != "N" {
      let left_n = Rc::new(RefCell::new(TreeNode::new(r.parse::<i32>()?)));
      q.push_back(left_n); //this works in the example, but you will have to clone here too
    }
  }
  Ok(Some(root))
}

从格式化输入构建树

Build tree from formatted input

queue

tree

rust

borrow-checker