![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
amaraoИ оказалось, что обойти без рекурсии дерево - это не так уж просто. Обход в ширину (мне показался) проще.
Я попробовал написать 80-строчного монстра, он дерево обходил, но закцикливался (уходил в лево после обхода в право, уходил вправо, после обхода в лево).
... Я сделал шаг назад и написал рекурсивную реализацию. 6 строк.
напоминаю, что:
И да, я устал от всех этих Ref'ов и as_ref'ов, но таковы условия задачи.
Честный pre_order. Если подвинуть println! в начало (над первым вызовом rec_pre_order), то получится in-order. Если сдвинуть в конец - будет post-order.
А теперь задача, взять этот изящный рекурсивный код и превратить его в итератор. Я понимаю, что это возможно, но с ходу не могу придумать как. Альтернативно: штурмовать loop-версию, пытаясь воспроизвести рекурсию на доморощенном стеке данных.
Пожалуй, я пока займусь идеей итератора из рекурсии. Может быть, это не самая дурная идея?
Я попробовал написать 80-строчного монстра, он дерево обходил, но закцикливался (уходил в лево после обхода в право, уходил вправо, после обхода в лево).
... Я сделал шаг назад и написал рекурсивную реализацию. 6 строк.
fn rec_pre_order(t: &Tree) {
if let Some(node) = t.as_ref().cloned() {
rec_pre_order(&node.borrow().left.as_ref().cloned());
println!("{}", node.borrow().val);
rec_pre_order(&node.borrow().right.as_ref().cloned());
}
}
напоминаю, что:
pub struct TreeNode {
pub val: i32,
pub left: Option<Rc<RefCell<TreeNode>>>,
pub right: Option<Rc<RefCell<TreeNode>>>,
}
type Tree = Option<Rc<RefCell<TreeNode>>>;
И да, я устал от всех этих Ref'ов и as_ref'ов, но таковы условия задачи.
Честный pre_order. Если подвинуть println! в начало (над первым вызовом rec_pre_order), то получится in-order. Если сдвинуть в конец - будет post-order.
А теперь задача, взять этот изящный рекурсивный код и превратить его в итератор. Я понимаю, что это возможно, но с ходу не могу придумать как. Альтернативно: штурмовать loop-версию, пытаясь воспроизвести рекурсию на доморощенном стеке данных.
Пожалуй, я пока займусь идеей итератора из рекурсии. Может быть, это не самая дурная идея?
no subject
Date: 2022-12-28 12:28 pm (UTC)Да, это понятно, но оказалось, что на стеке сохраняется не только значение, но и положение внутри кода. Его явно надо кодировать, и тут-то у меня оно и не получилось. В целом, если положить стек в структуру итератора, то получится идиоматический код.
Тут ещё момент, что я теоретически знаю, как итераторы пишутся в rust, но все мелкие детальки ещё не прожевал. Ща буду "жевать".