Превращение рекурсивного обхода узла в итеративный обход узла

Question

У меня есть рекурсивный алгоритм обхода узлов в дереве документа в порядке дерева

Как бы это сделать итеративным? Моя попытка сделать его итеративным полностью провалилась

function recursivelyWalk(nodes, cb) {
    for (var i = 0, len = nodes.length; i < len; i++) {
        var node = nodes[i],
            ret = cb(node)

        if (ret) {
            return ret
        }

        if (node.childNodes.length) {
            var ret = recursivelyWalk(node.childNodes, cb)
            if (ret) {
                return ret
            }
        }
    }
}

Answer 1

Эта статья (ссылка на статью Статья Википедии о обходе дерева ) предоставляет алгоритм на JavaScript для итеративного обхода предзаказа дерева DOM.Цитата:

function preorderTraversal(root) {
  var n = root;
  while(n) {
  // If node have already been visited
    if (n.v) {
      // Remove mark for visited nodes
      n.v = false;
      // Once we reach the root element again traversal
      // is done and we can break
      if (n == root)
        break;
      if (n.nextSibling)
        n = n.nextSibling;
      else
        n = n.parentNode;
    }
    // else this is the first visit to the node
    else {
      //
      // Do something with node here...
      //
      // If node has childnodes then we mark this node as
      // visited as we are sure to be back later
      if (n.firstChild) {
        n.v = true;
        n = n.firstChild;
      }
      else if (n.nextSibling)
        n = n.nextSibling;
      else
        n = n.parentNode;
    }
  }
}

Обратите внимание на строку "// Do something with node here...", где вы можете вызвать функцию обратного вызова.

Подробнее читайте в полной статьеинформация.

Answer 2

Как насчет объединения дочерних узлов, если они есть, и использования цикла while(nodes.length)?По сути, продолжайте добавлять новые узлы в стек и продолжайте цикл (каждый раз проверяя один узел), пока стек не станет пустым: http://jsfiddle.net/gEm77/1/.

var z = 0; // my precaution for a while(true) loop

function iterativelyWalk(nodes, cb) {
    nodes = [].slice.call(nodes);

    while(++z < 100 && nodes.length) {
        var node = nodes.shift(),
            ret = cb(node);

        if (ret) {
            return ret;
        }

        if (node.childNodes.length) {
            nodes = [].slice.call(node.childNodes).concat(nodes);
        }
    }
}