Как создать Tree Zipper с помощью Rust?
Я пытаюсь создать Tree Zipper , используя Rust. Он вдохновлен этим ответом, но я использую поля структуры вместо Vec для детей.
Я хочу иметь дерево узлов, например:
7
/ \
4 11
/
2
Смысл использования Zipper в том, что «текущий» узел должен быть изменчивым. И что это должно быть реализовано без unsafe блоков.
Я объявил свои Node и NodeZipper, как показано ниже:
#[derive(Debug)]
struct Node {
value: i32,
left: Option<Box<Node>>,
right: Option<Box<Node>>,
}
impl Node {
fn navigate(self) -> NodeZipper {
NodeZipper {
node: self,
parent: None,
}
}
}
#[derive(Debug)]
struct NodeZipper {
node: Node,
parent: Option<Box<NodeZipper>>,
}
impl NodeZipper {
fn left(mut self) -> Self {
let left_child = self.node.left.take().unwrap(); // take() mutates the node
Self {
node: *left_child,
parent: Some(Box::new(self)),
}
}
fn parent(mut self) -> Self {
let parent = self.parent.take().unwrap();
Self {
node: parent.node,
parent: parent.parent,
}
}
}
Проблема с приведенным выше кодом заключается в том, что я использую .take(), а он изменяет Node, поэтому некоторые данные теряются. Есть ли альтернативный способ решить эту проблему без использования, например. клонировать и хотя бы без использования unsafe?
Вот пример запуска, в котором я перемещаюсь от корня вниз к левому дочернему элементу, а затем обратно к родительскому элементу (но теперь левый дочерний элемент потерян).
fn main() {
let tree = Node {
value: 7,
left: Some(Box::new(Node {
value: 4,
left: Some(Box::new(Node {
value: 2,
left: None,
right: None,
})),
right: None,
})),
right: Some(Box::new(Node {
value: 11,
left: None,
right: None,
})),
};
let nav = tree.navigate();
println!("t: {:?}", nav);
let nav = nav.left();
println!("t: {:?}", nav);
let nav = nav.parent();
println!("t: {:?}", nav);
}
И вывод, в котором левый дочерний элемент корня теряется при возврате к родительскому элементу:
t: NodeZipper { node: Node { value: 7, left: Some(Node { value: 4, left: Some(Node { value: 2, left: None, right: None }), right: None }), right: Some(Node { value: 11, left: None, right: None }) }, parent: None }
t: NodeZipper { node: Node { value: 4, left: Some(Node { value: 2, left: None, right: None }), right: None }, parent: Some(NodeZipper { node: Node { value: 7, left: None, right: Some(Node { value: 11, left: None, right: None }) }, parent: None }) }
t: NodeZipper { node: Node { value: 7, left: None, right: Some(Node { value: 11, left: None, right: None }) }, parent: None }
Ответы 1
Я имею в виду, что очевидная ошибка заключается в том, что вы не возвращаете взятые вами узлы. Вам придется сохранить их и вернуть обратно, когда вы вернетесь назад.
Да, это правильно. Мне также не хватало понимания того, как должны работать Молнии. Но теперь у меня появилось больше понимания.
В итоге у меня появился метод parent(), показанный ниже, который также возвращает дочерний узел при движении вверх.
fn parent(mut self) -> Option<Self> {
match self.parent.take() {
None => None,
Some(parent_ref) => {
let (mut parent, side) = *parent_ref;
match side {
ChildSide::Left => {
// put back what we took using `take()` while traversing down
parent.node.left = Some(Box::new(self.node));
Some(Self {
node: parent.node,
parent: parent.parent,
})
}
ChildSide::Right => {
// put back what we took using `take()` while traversing down
parent.node.right = Some(Box::new(self.node));
Some(Self {
node: parent.node,
parent: parent.parent,
})
}
}
}
}
}
Теперь NodeZipper объявлен как:
#[derive(Debug)]
struct NodeZipper {
node: Node,
parent: Option<Box<(NodeZipper, ChildSide)>>,
}
#[derive(Debug)]
enum ChildSide {
Left,
Right,
}
Я имею в виду, что очевидная ошибка заключается в том, что вы не возвращаете взятые вами узлы. Вам придется сохранить их и вернуть обратно, когда вы вернетесь назад. Возможно,
nodeдолжен быть стек узлов с текущим на самом верху.