Как преобразовать метод генератора в итератор
У меня есть этот метод рекурсивного генератора, который дает значения BST в порядке возрастания:
*inOrder(node){
if (node === null) {
return;
}
if (node.left){
yield * this.inOrder(node.left);
}
yield node.val;
if (node.right){
yield * this.inOrder(node.right);
}
}
Рекурсивный генератор довольно интенсивно использует ЦП. Я пытаюсь преобразовать его в итератор, чтобы лучше понять, что происходит, вот моя попытка, которая совершенно неполна, с использованием итеративного решения:
[Symbol.iterator]() {
// iterative solution?
const queue = [this.rootNode];
return {
next(){
return {
done: true,
value: // (last (right-most) value in tree)
}
}
}
}
У меня такое ощущение, что итеративное решение для поиска в глубину слева направо потребует очереди, но не уверен. В качестве альтернативы, рекурсивное решение может работать, когда мы сначала передаем корневой узел следующим образом:
[Symbol.iterator](node) {
// recursive solution
return {
next(){
return {
done: true,
value: // (last (right-most) value in tree)
}
}
}
}
Однако я не уверен, как реализовать с помощью итератора итеративное или рекурсивное решение. Итак, это мой вопрос, как взять код генератора и каким-то образом использовать итератор.
![Безумие обратных вызовов в javascript [JS]](https://i.imgur.com/WsjO6zJb.png)
Ответы 3
Используйте stack для хранения узлов, которые необходимо посетить
Выполните dfs дерева в порядке слева направо.
next метод вызывается до тех пор, пока не будут посещены все узлы в дереве и не будет выполнен итератор.
[Symbol.iterator]() {
const stack = [];
let currentNode = this.rootNode;
return {
next() {
while (currentNode !== null || stack.length > 0) {
if (currentNode !== null) {
stack.push(currentNode);
currentNode = currentNode.left;
} else {
const node = stack.pop();
currentNode = node.right;
return {
done: false,
value: node.val
};
}
}
return {
done: true,
value: undefined
};
}
};
}
Рекурсивный
[Symbol.iterator]() {
return {
next: function* (node = this.rootNode) {
if (node === null) {
return { done: true };
}
yield* this.next(node.left);
yield node.val;
yield* this.next(node.right);
}.bind(this)
};
}
Кроме того, если вы используете const stack = [this.rootNode];, можете ли вы избавиться от проверки для while(currentNode !== null) || ... и просто использовать while(stack.length >0?
в этом коде tmk есть баг, при использовании for..of проходит весь список, а потом начинается с 0.5 и снова идет вверх?
добавьте в итератор флаг, указывающий, были ли возвращены все значения. Вы можете установить этот флаг в true, когда метод next возвращает окончательное значение в дереве.
извините, я не понимаю, как этот флаг будет работать, можете ли вы обновить свой ответ?
Я добавил ответ, я отклонил ваш ответ, если бы вы могли проверить мой, это было бы круто!
проблема заключалась в том, что комбинированное условие while (currentNode !== null || stack.length > 0) { очень сложно понять, поэтому я написал условие без этого условия (надеюсь, оно сработает).
С вашей структурой данных {left, val, right} вы не можете избежать рекурсии (или стека), если хотите пройти все узлы в порядке (left, затем val, затем right, что вы называете возрастающим порядком). И функция генератора *inOrder отлично с этим справляется. Его также можно использовать, чтобы сделать класс BST итерируемым:
class BST {
constructor(root) {
this[Symbol.iterator] = function() {
return this.inOrder(root);
}
}
* inOrder(node) {...}
}
Обход без рекурсии возможен, если вы используете более богатую структуру данных, например «потоковое представление», описанное в Кнуте, Искусство компьютерного программирования taocp, раздел 2.3.1. В этом представлении у каждого узла есть левая ссылка и правая ссылка, а те, которые не указывают на дочерний элемент, называются «потоками», которые вместо этого указывают на узел-предшественник или последующий узел. Настройка этих дополнительных потоков в конструкторе (и обновление их всякий раз, когда узел вставляется или удаляется) требует дополнительной работы, но тогда итератор упрощается до:
*[Symbol.iterator]() {
var node = this.root;
while (node.left && !node.leftThread) node = node.left;
yield node.val;
while (node) {
var next = node.right;
if (!node.rightThread)
while (!next.leftThread) next = next.left;
if (next) yield next.val;
node = next;
}
}
(Это всего лишь один пример, для деревьев, несомненно, существует множество других структур данных.)
Окупается ли дополнительная работа с дополнительной структурой данных, зависит от того, что чаще происходит с деревом: обходы или обновления.
что не так с брекетами? :)
по этому поводу я не понимаю, почему node всегда будет определяться здесь yield node.val;, вы можете это исправить? не может ли узел быть там неопределенным?
Интересно, есть ли способ сделать рекурсивное решение, когда вы передаете узел в next(), например next(node)? Хотя итеративное решение, как правило, лучше.
Условие while гарантирует, что node !== undefined.
спасибо что вы думаете о моем ответе
Выглядит хорошо, если вы хотите использовать стек.
Я взял ответ @Sachin и немного развил его. Это не очень хорошо проверено, но, похоже, работает:
[Symbol.iterator]() {
const stack = [];
let currentNode = this.rootNode;
return {
next() {
while (currentNode !== null) {
stack.push(currentNode);
currentNode = currentNode.left || null;
}
if (stack.length < 1) {
return {done: true, value: null};
}
const node = stack.pop();
currentNode = node.right || null;
return {done: false, value: node.val};
}
};
}
спасибо, интересно, есть ли способ сделать рекурсивное решение, в котором вы передаете узел
next()какnext(node)? Хотя итеративное решение, как правило, лучше.