обходы дерева

А вот я думал, что задачу symmetric tree я решу в пол-пинка. (Задача: по заданному дереву сказать, симметричное ли оно).

Теоретическое решение: pre_walk() == post_walk().

Практические проблемы: наивные методы обхода дерева используют рекурсию, а использовать рекурсию при параллельном обходе дерева двумя разными способами - себе дороже.

Выгрузка обоих деревьев в список и сравнение - уровень сложности алгоритма `o(позор)`.

Правильное решение: реализовать стеки из вектора и обходить в цикле. Но два обхода в одной функции уродливо, так что идиоматический подход должен реализовать итератор pre_walk(), итератор post_walk(), и потом просто сравнить их. (то есть решение будет `pre_walk(&tree) == post_walk(&tree)`).

А вот над реализацией нерекурсивного обхода дерева я сейчас буду думать. Теоретически, ничего сложного, но масса эргономических нюансиков (например, как хранить направление движения (влево или вправо)? Надо ли его хранить или оно само получится?).

Плюс rust'овая машинерия для итераторов, которая выглядит ясной и простой, пока туда lifetimes для захваченных ref не появятся.

Короче, задача сводится к pre_order walk через итератор. Решу её, дальше тривиально. Традиционно, сначала решаю, потом читаю умные тексты.

древесное

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

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

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

итераторы

!markdown

А вот я и дошёл до странной проблемы, которую я не могу понять.

#[derive (Debug)]

struct Count{

from: u32,

to: u32

}

#[derive (Debug)]

struct CountIterator<'a>{

params: &'a Count,

cur: u32

}

impl Count{

pub fn new(from: u32, to: u32) -> Self {

Count{from, to}

}

}

impl<'a> Iterator for CountIterator<'a>{

type Item = u32;

fn next(&mut self) -> Option<Self::Item> {

if self.cur < self.params.to{

self.cur += 1;

Some(self.cur)

}else{

None

}

}

}

impl<'a> IntoIterator for Count{

type Item = u32;

type IntoIter = CountIterator<'a>;

fn into_iter(&'a self) -> Self::IntoIter {

CountIterator{params: self, cur: self.from}

}

}

И этот код неправильный, потому что

    222 | impl<'a> IntoIterator for Count{
        |      ^^ unconstrained lifetime parameter

И я не понимаю, почему так. И оно неприятно щекочет где-то в районе type parameters, потому что редактор подсказывает, что на месте IntoIter = надо писать

type IntoIter: Iterator<Item = Self::Item> = .....;

И я ни черта не понимаю в написанном. Либо это RLS фигню пишет, либо я что-то глубоко не понимаю. Иду пересматривать про итераторы. Что-то я упускаю...