rust - 在不递归的情况下执行修改后的 DFS 时改变树

Question

我正在尝试实现树 DFS 的修改版本无需递归，并且正在与借用检查器作斗争。我的要求是我想确保子节点在其父节点之前得到处理，并且我希望所有这些都是可变的(在不可变的情况下没有问题)。

我有一个简单的树结构如下:

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

正常的迭代 DFS 可能看起来像这样(注意我们正在改变树):

fn normal_dfs(node: &mut Node) {
    let mut node_stack = vec![node];
    while !node_stack.is_empty() {
        let current_node = node_stack.pop().unwrap();
        for child_node in &mut current_node.children {
            node_stack.push(child_node);
        }

        current_node.value += 1;
    }
}

在上面的函数中，父节点将在子节点之前被处理，我希望相反。我试图构建一个对所有树节点的引用堆栈，然后我计划向后迭代，确保子节点在其父节点之前得到处理:

fn modified_dfs(node: &mut Node) {
    //requirement: child nodes should be treated before parent nodes
    let mut node_stack = vec![node];
    let mut stack_index = 0usize;
    let mut stack_size = node_stack.len(); //not great but helps with borrow checker

    while stack_index < stack_size {
        let current_node = node_stack.get_mut(stack_index).unwrap();
        for child_node in &mut current_node.children {
            node_stack.push(child_node);
        }

        stack_size = node_stack.len();
        stack_index += 1;
    }

    //iterate stack in reverse to make sure child nodes are treated before parents
    for current_node in node_stack.iter_mut().rev() {
        current_node.value += 1;
    }
}

这不会编译错误:

error[E0499]: cannot borrow `node_stack` as mutable more than once at a time
  --> src/lib.rs:13:28
   |
13 |         let current_node = node_stack.get_mut(stack_index).unwrap();
   |                            ^^^^^^^^^^ `node_stack` was mutably borrowed here in the previous iteration of the loop

error[E0499]: cannot borrow `node_stack` as mutable more than once at a time
  --> src/lib.rs:15:13
   |
13 |         let current_node = node_stack.get_mut(stack_index).unwrap();
   |                            ---------- first mutable borrow occurs here
14 |         for child_node in &mut current_node.children {
   |                           -------------------------- first borrow later used here
15 |             node_stack.push(child_node);
   |             ^^^^^^^^^^ second mutable borrow occurs here

error[E0502]: cannot borrow `node_stack` as immutable because it is also borrowed as mutable
  --> src/lib.rs:18:22
   |
13 |         let current_node = node_stack.get_mut(stack_index).unwrap();
   |                            ---------- mutable borrow occurs here
...
18 |         stack_size = node_stack.len();
   |                      ^^^^^^^^^^
   |                      |
   |                      immutable borrow occurs here
   |                      mutable borrow later used here

error[E0499]: cannot borrow `node_stack` as mutable more than once at a time
  --> src/lib.rs:23:25
   |
13 |         let current_node = node_stack.get_mut(stack_index).unwrap();
   |                            ---------- first mutable borrow occurs here
...
23 |     for current_node in node_stack.iter_mut().rev() {
   |                         ^^^^^^^^^^
   |                         |
   |                         second mutable borrow occurs here
   |                         first borrow later used here

我想我明白了错误的原因:我在一次迭代中借用了node_stack，而在迭代结束时借用并没有“释放”，因为子节点已经被放上了堆栈(如果您不推送子节点，它会编译)。

执行此操作的迭代算法是什么？

Answer 1

如果您真的必须可变地执行此操作，您可以像这样使用 Rc 和 RefCell:

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

struct Node {
    value: usize,
    children: Vec<Rc<RefCell<Node>>>,
}

fn modified_dfs(node: Rc<RefCell<Node>>) {
    //requirement: child nodes should be treated before parent nodes
    let mut node_stack = vec![node];
    let mut stack_index = 0usize;
    let mut stack_size = node_stack.len(); //not great but helps with borrow checker

    while stack_index < stack_size {
        let current_node = node_stack[stack_index].clone();
        for child_node in &current_node.borrow().children {
            {
                // Do something mutable with child_node
                child_node.borrow_mut();
            }
            node_stack.push(child_node.clone());
        }

        stack_size = node_stack.len();
        stack_index += 1;
    }

    //iterate stack in reverse to make sure child nodes are treated before parents
    for current_node in node_stack.iter_mut().rev() {
        current_node.borrow_mut().value += 1;
    }
}