Построить дерево из отформатированного ввода - PullRequest
Новая
       5

Построить дерево из отформатированного ввода

0 голосов
/ 13 марта 2020

У меня возникла проблема при попытке найти решение для чтения двоичного дерева из отформатированного ввода и построения указанного дерева в 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

Я был бы очень благодарен любой, кто мог бы дать некоторые указания относительно того, как я работаю в этой ситуации.

С уважением,

1 Ответ

1 голос
/ 14 марта 2020

Следующий код короче и демонстрирует вашу проблему: 

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).

Фиксированный пример: 

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))
}
...