Как прочитать и изменить значение узла в связанном дереве?

Я борюсь с реализацией древовидной структуры в Rust. В частности, получение и изменение значения узла. Какой идиоматический способ работы с ценностью?

Примечание: реализация дана и не может быть изменена.

use std::rc::Rc;
use std::cell::RefCell;

// Definition for a binary tree node.
#[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
    }
  }
}

fn main() {
    let mut root = Some(Rc::new(RefCell::new(TreeNode::new(1))));
    println!("{:?}", root.unwrap().borrow().val); // cannot infer type for type parameter `Borrowed`
    root.unwrap().get_mut().val = 2; // cannot borrow data in an `Rc` as mutable
}

rust tree borrowing interior-mutability reference-counting
person Evgeni Nabokov    schedule 07.05.2020    source источник
comment
У вас есть две независимые проблемы. Первый описан здесь: root перемещается после вызова unwrap(). Вторая причина заключается в том, что вы должны использовать borrow_mut() вместо get_mut(). Последний использует типичную внутреннюю изменчивость вместо внутренней изменчивости.   -  person E_net4 the curator    schedule 07.05.2020
comment
Зачем оборачиваете рут в RefCell, Rc и Option? Просто let mut root = TreeNode::new(1), затем заполните ветки   -  person Alexey Larionov    schedule 07.05.2020
comment
Rc<RefCell<TreeNode>> означает, что узлы могут использоваться несколькими родителями. Так ли это? Я бы ожидал, что узлы в дереве будут владеть своими дочерними элементами, скажем, Box<TreeNode>.   -  person John Kugelman    schedule 07.05.2020
comment
Почему Rc ‹RefCell‹ ... ›› выходит за рамки вопроса. Реализация дана, и я не могу изменить ни одного ее байта.   -  person Evgeni Nabokov    schedule 07.05.2020
comment
@AlexLarionov, потому что он находится в сигнатуре функции. Я получаю Option ‹Rc‹ RefCell ‹TreeNode› ››, а не TreeNode.   -  person Evgeni Nabokov    schedule 07.05.2020

Ответы (1)


arrow_upward
1
arrow_downward

Вы можете спокойно unwrap это значение, если знаете, что оно Some(T). Rc<T> должен работать как прозрачный контейнер, который отменяет вызовы методов, поэтому вы можете обычно рассматривать Rc<T> как T или, в частности, RefCell<T> в вашем случае, а затем вы можете взаимодействовать со значением внутри RefCell, используя методы borrow и borrow_mut. Пример:

use std::rc::Rc;
use std::cell::RefCell;

// Definition for a binary tree node.
#[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
    }
  }
}


fn main() {
    let mut root = Some(Rc::new(RefCell::new(TreeNode::new(1))));
    let mut root = root.unwrap();
    println!("{:?}", root.borrow().val); // read access
    root.borrow_mut().val = 2; // write access
}

детская площадка

См. Также Распаковка и доступ к T из опции ‹Rc‹ RefCell ‹T› ››

person pretzelhammer    schedule 07.05.2020