Существует ли какой-либо нерекурсивный/стек-потребляющий, восходящий двоичный древовидный поперечный алгоритм?

Question

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

((add ((add 2) 3)) ((add 4) 2)) -> 11 

Простой алгоритм может быть (например, в JavaScript):

function r(a){ 
    if (typeof(a)!=="object") return a; 
    var a = [r(a[0]), r(a[1])]; 
    return a[0][0]==="add" ? a[0][1] + a[1] : a; 
} 
console.assert(r([["add",[["add",2],3]],[["add",4],2]]) === 11); 

Можно ли решить ту же проблему с постоянным стеком?

Answer 1

Любой рекурсивный алгоритм может быть эмулирован с использованием стека в куче и петле. Итак, да, это можно сделать в одном вызове функции.

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

Answer 2

Если вы преобразуете свою древовидную структуру в zipper, чтобы ее можно было перемещать с помощью конечного автомата. Это уже не простое дерево, но позволяет сделать его нерекурсивным или хвостовым рекурсивным.

Answer 3

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

Результирующий алгоритм требует O (1) дополнительного пространства и времени O (n^2).