Ржавчина модифицированного дерева DFS без рекурсии (изменяемый регистр) - PullRequest
Новая
       24

Ржавчина модифицированного дерева DFS без рекурсии (изменяемый регистр)

1 голос
/ 03 марта 2020

Я пытаюсь реализовать модифицированную версию дерева DFS без рекурсии и пытаюсь проверить заемщик. Мое требование состоит в том, чтобы я хотел, чтобы дочерние узлы обрабатывались перед их родителями, и я хотел бы, чтобы все это было изменяемым (без проблем в неизменяемом случае).

У меня есть простая древовидная структура, как показано ниже: 

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

Обычная итеративная DFS может выглядеть следующим образом (обратите внимание, что мы изменяем дерево, поскольку go): 

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\main.rs:28:28
   |
28 |         let current_node = node_stack.get_mut(stack_index).unwrap();
   |                            ^^^^^^^^^^ mutable borrow starts here in previous iteration of loop

Мне кажется, я понимаю причину ошибки: я заимствовал node_stack в итерации, и заимствование не "освобождено" в конце итерации, потому что дочерние узлы были положить в стек (он компилируется, если вы не используете sh дочерние узлы).

Но я изо всех сил пытаюсь найти итеративный алгоритм, который помог бы мне сделать это, какие-нибудь указатели? Спасибо!

...