实现可变的树结构

Question

我正在尝试动态建立一棵树，并在下降，叶子和备份期间修改树的某些部分。我相信我对在Rust中如何做这样的事情有根本的误解。这是我的代码：

struct Node {
    children: Vec<Node>,
    data: usize,
}

impl Node {
    pub fn new() -> Node {
        Node {
            children: vec![],
            data: 0,
        }
    }

    pub fn expand(&mut self) {
        self.children = vec![Node::new(), Node::new()];
    }

    pub fn is_leaf(&self) -> bool {
        self.children.len() == 0
    }
}

pub fn main() {
    let mut root = Node::new();
    for _ in 0..10 {
        let mut node = &mut root;
        let mut path = vec![];
        // Descend and potential modify the node in the process
        while !node.is_leaf() {
            let index = 0;
            path.push(index);
            node = &mut node.children[index];
        }
        // Do something to the leaf node
        node.expand();
        // Do something during "backup" (in my case it doesn't matter
        // in which order the modification is happening).
        node = &mut root;
        for &i in path.iter() {
            node.data += 1;
            node = &mut node.children[i];
        }
    }
}

这是来自编译器的错误消息：

struct Node {
    children: Vec<Node>,
    data: usize,
}

impl Node {
    pub fn new() -> Node {
        Node {
            children: vec![],
            data: 0,
        }
    }

    pub fn expand(&mut self) {
        self.children = vec![Node::new(), Node::new()];
    }

    pub fn is_leaf(&self) -> bool {
        self.children.len() == 0
    }
}

pub fn main() {
    let mut root = Node::new();
    for _ in 0..10 {
        let mut node = &mut root;
        let mut path = vec![];
        // Descend and potential modify the node in the process
        while !node.is_leaf() {
            let index = 0;
            path.push(index);
            node = &mut node.children[index];
        }
        // Do something to the leaf node
        node.expand();
        // Do something during "backup" (in my case it doesn't matter
        // in which order the modification is happening).
        node = &mut root;
        for &i in path.iter() {
            node.data += 1;
            node = &mut node.children[i];
        }
    }
}

Answer 1

同时发生了一些事情。简单的答案是：您正在尝试为同一项目创建多个可变借项。即使您不尝试修改它们，Rust也禁止您创建多个借用文件（因为这比尝试正式证明程序正确是容易的）。

由于您基本上试图以命令式方式实现递归函数，因此建议您使用一种更具功能性的方法来解决问题。我将逻辑从您的循环中移出，直接在上实现了递归函数Node。

struct Node {
    children: Vec<Node>,
    data: usize,
}

impl Node {

    pub fn new() -> Node {
        Node {
            children: vec!(),
            data: 0
        }
    }

    pub fn expand(&mut self) {
        self.children = vec!(Node::new(), Node::new());
    }

    pub fn is_leaf(&self) -> bool {
        self.children.len() == 0
    }

    fn expand_leaf_and_inc(&mut self) {
        if self.is_leaf() {
            self.expand();
        } else {
            let index = 0;
            self.children[index].expand_leaf_and_inc();
        }
        self.data += 1
    }
}

pub fn main() {
    let mut root = Node::new();
    for _ in 0..10 {
        root.expand_leaf_and_inc();
    }
}

如果您想保持当务之急，可以使用{node}.children技巧来摆脱&mut借贷，而不必重新借贷：

let mut root = Node::new();
for _ in 0..10 {
    let mut path = vec![];
    {
        let mut node = &mut root;
        // Descend and potential modify the node in the process
        while !node.is_leaf() {
            let index = 0;
            path.push(index);
            node = &mut {node}.children[index];
        }
        // Do something to the leaf node
        node.expand();
    }
    // Do something during "backup" (in my case it doesn't matter
    // in which order the modification is happening).
    let mut node = &mut root;
    for &i in path.iter() {
        node.data += 1;
        node = &mut {node}.children[i];
    }
}