Первое, что нам нужно решить, это структура нашего дерева. Вместо того, чтобы иметь отдельный корневой узел, было бы целесообразно, чтобы первый элемент списка был корневым. Следовательно, наша древовидная структура данных может быть определена следующим образом:
// A Tree(a) is one of:
// - null
// - tree(a, Tree(a), Tree(a))
const tree = (value, left, right) => ({ value, left, right });
Следовательно, наше дерево вывода будет выглядеть так:
1
|
+------------+------------+
| |
10 100
| |
+---------+---------+ +-----+-----+
| | | |
20 2 3 30
| | | |
+-----+-----+ +-+-+ +--+--+ +--+--+
| | | | | | | |
300 40 4 null null null null null
| | |
+--+--+ +--+--+ +--+--+
| | | | | |
null null null null null null
Если бы мы использовали рекурсию, то код прост, потому что деревья - это рекурсивные структуры данных:
const buildTree = (xs, i = 0) => i >= xs.length ? null :
tree(xs[i], buildTree(xs, 2 * i + 1), buildTree(xs, 2 * i + 2));
Собираем все вместе:
// A Tree(a) is one of:
// - null
// - tree(a, Tree(a), Tree(a))
const tree = (value, left, right) => ({ value, left, right });
const buildTree = (xs, i = 0) => i >= xs.length ? null :
tree(xs[i], buildTree(xs, 2 * i + 1), buildTree(xs, 2 * i + 2));
console.log(buildTree([1, 10, 100, 20, 2, 3, 30, 300, 40, 4]));
.as-console-wrapper { max-height: 100% !important; top: 0; }
Я оставлю это в качестве упражнения для вас, чтобы преобразовать эту рекурсивную программу в итеративную программу.
Вот алгоритмический метод преобразования любой рекурсивной функции в итерационную функцию. Сначала преобразуйте функцию в стиль продолжения:
const buildTree = (xs, i = 0, k = x => x) => i >= xs.length ? k(null) :
buildTree(xs, 2 * i + 1, left =>
buildTree(xs, 2 * i + 2, right =>
k(tree(xs[i], left, right))));
Затем замените продолжения структурой данных, которая содержит все необходимые свободные переменные продолжения. Также замените вызовы продолжения приложением к функции applyCont, которая содержит логику продолжения:
const buildTree = (xs, i, k = null) => i >= xs.length ? applyCont(k, null) :
buildTree(xs, 2 * i + 1, { xs, i, k });
const applyCont = (k, x) => k === null ? x :
!k.hasOwnProperty("x") ? buildTree(k.xs, 2 * k.i + 2, { x, xs: k.xs, i: k.i, k: k.k }) :
applyCont(k.k, tree(k.xs[k.i], k.x, x));
Если вы заметили, структура продолжений теперь похожа на связанный список. Фактически, вы можете думать о продолжениях как о стеке кадров (то есть о программном стеке). Теперь этот рекурсивный код легко преобразовать в итеративный код следующим образом:
const buildTree = xs => {
var i = 0, stack = null;
loop: do {
while (i < xs.length) {
i = 2 * i + 1;
k = { i, k };
}
var x = null;
while (k) {
if (!k.hasOwnProperty("x")) {
i = 2 * k.i + 2;
k.x = x;
continue loop;
}
k = k.k;
x = tree(k.xs[k.i], k.x, x);
}
return x;
} while (true);
};
Надеюсь, это поможет.