如何使用 Rust 创建 Tree Zipper？

Question

我正在尝试使用 Rust 创建一个 Tree Zipper。它的灵感来自于这个答案，但我为孩子们使用结构字段而不是

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

当移回父级时，root 的 left child 丢失的输出：

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 }

Answer 1

我的意思是明显的错误是没有放回您获取的节点。您必须存储它们并在返回时将它们放回去。

是的，这是正确的。我也对 Zippers 应该如何工作缺乏了解。但我现在有了更多的见解。

我最终得到了如下的

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,
}