древесное

[amarao]

И оказалось, что обойти без рекурсии дерево - это не так уж просто. Обход в ширину (мне показался) проще.

Я попробовал написать 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-версию, пытаясь воспроизвести рекурсию на доморощенном стеке данных.

Пожалуй, я пока займусь идеей итератора из рекурсии. Может быть, это не самая дурная идея?

Comments

[permeakra]

Явный стек рекурсии в составе итератора или лямбды..

[amarao]

Да, это понятно, но оказалось, что на стеке сохраняется не только значение, но и положение внутри кода. Его явно надо кодировать, и тут-то у меня оно и не получилось. В целом, если положить стек в структуру итератора, то получится идиоматический код.

Тут ещё момент, что я теоретически знаю, как итераторы пишутся в rust, но все мелкие детальки ещё не прожевал. Ща буду "жевать".