Подтвердить что ты не робот

Пересечение дерева в javascript

Я пытаюсь хорошо изучить структуры данных и реализовал следующий код для первого хода/применения обратного вызова на регулярном дереве:

Tree.prototype.traverse = function (callback) {
  callback(this.value);

  if (!this.children) {
    return;
  }
  for (var i = 0; i < this.children.length; i++) {
    var child = this.children[i];
    child.traverse(callback);
  }
};

Как я могу изменить это, чтобы вместо этого сделать его шириной? Это выглядит класс дерева:

var Tree = function (value) {
  var newTree = {};

  newTree.value = value;
  newTree.children = [];
  extend(newTree, treeMethods);

  return newTree;
};

Ответ 1

В сущности, разница между DFS и BFS заключается в том, что с помощью DFS вы выталкиваете дочерние элементы текущего node в стек, поэтому они будут выгружаться и обрабатываться до всего остального, тогда как для BFS вы нажимаете дочерние элементы на конец очереди, поэтому они будут выгружаться и обрабатываться после всего остального.

DFS легко реализовать рекурсивно, потому что вы можете использовать стек вызовов как стек. Вы не можете сделать это с помощью BFS, потому что вам нужна очередь. Чтобы упростить сходство, давайте сначала конвертируем вашу DFS в итеративную реализацию:

//DFS
Tree.prototype.traverse = function (callback) {
  var stack=[this];
  var n;

  while(stack.length>0) {

    n = stack.pop();
    callback(n.value);

    if (!n.children) {
      continue;
    }

    for (var i = n.children.length-1; i>=0; i--) {
       stack.push(n.children[i]);
    }
  }
};

И теперь BFS

//BFS
Tree.prototype.traverse = function (callback) {
  var queue=[this];
  var n;

  while(queue.length>0) {

    n = queue.shift();
    callback(n.value);

    if (!n.children) {
      continue;
    }

    for (var i = 0; i< n.children.length; i++) {
       queue.push(n.children[i]);
    }
  }
};