древесное

[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, но все мелкие детальки ещё не прожевал. Ща буду "жевать".

[yurikhan]

В Python’е итератор для бинарного дерева тривиально пишется рекурсивно, а работает как положено итератору:

class TreeNode:
    val: int
    left: Optional["TreeNode"]
    right: Optional["TreeNode"]

    def iter_preorder(self) -> Iterator[int]:
        yield self.val
        if self.left:
            yield from self.left.iter_preorder()
        if self.right:
            yield from self.right.iter_preorder()

Внутри, естественно, преобразование корутины в примерно такой объект:

class TreeNodeIterator:
    state: int
    subiter: Optional["TreeNodeIterator"]

    def __init__(self, subject: TreeNode) -> None:
        self.subject = subject
        self.state = 0
        self.subiter = None

    def __iter__(self) -> Iterator[int]:
        return self

    def __next__(self) -> int:
        if self.state == 0:
            self.state = 1
            return self.subject.val
        if self.state == 1:
            if self.subject.left:
                self.subiter = TreeNodeIterator(self.subject.left)
                self.state = 2
            else:
                self.state = 3
        if self.state == 2:
            try:
                return self.subiter.__next__()
            except StopIteration:
                self.state = 3
        if self.state == 3:
            if self.subject.right:
                self.subiter = TreeNodeIterator(self.subject.right)
                self.state = 4
            else:
                self.state = 5
        if self.state == 4:
            try:
                return self.subiter.__next__()
            except StopIteration:
                self.state = 5
        raise StopIteration()

В Rust’е нет какого-нибудь аналогичного сахара для корутин?