广度优先搜索二叉搜索树javascript实现

Question

我有以下代码在 JavaScript 中实现了 BST 树。

function Node(value) {
  this.left = null;
  this.right = null;
  this.value = value;
}

function BinarySearchTree() {
  this.root = null;
  return;
}

BinarySearchTree.prototype.push = function(value) {

  if (!this.root) {
    this.root = new Node(value);
    return;
  }

  var currentRoot = this.root;
  var newNode = new Node(value);
  while (currentRoot) {
    if (value < currentRoot.value) {
      if (!currentRoot.left) {
        currentRoot.left = newNode;
        break;
      } else {
        currentRoot = currentRoot.left;
      }
    } else {

      if (!currentRoot.right) {
        currentRoot.right = newNode;
        break;
      } else {
        currentRoot = currentRoot.right;
      }

    }

  }

}

var a = new BinarySearchTree();
a.push(27);
a.push(14);
a.push(35);
a.push(10);
a.push(19);
a.push(31);
a.push(42);

我正在尝试实现一个可以对树进行广度优先遍历的函数。到目前为止，这是我尝试过的。

console.log(a.root.value);
traverse(a.root);

//function to traverse 
function traverse(node) {

  currentNode = node;
  while (currentNode.left) {
    displayNodes(currentNode);
    parent = currentNode;
    currentNode = currentNode.left;
    displayNodes(currentNode);
    if(parent.right!=null){
    displayNodes(parent.right);
    }
  }
}

//function that displays the left and right node of a node 
function displayNodes(node) {


  if (node.left != null) {
    console.log(node.left.value);
  }
  if (node.right != null) {
    console.log(node.right.value);
  }
}

我无法实现可以扩展大量数据的功能。我不确定遍历递归方法会更好还是使用 while 循环。我怎样才能实现这个功能？我知道该函数给出了意想不到的行为？我应该做什么更正？

Answer 1

您当前遍历从根节点到最左边叶子的路径。

在每个遍历节点上调用回调的简单非递归广度优先遍历函数如下所示：

// Breadth-first traversal:
function traverse(node, cb) {
  var current = [node];
  while (current.length > 0) {
    var next = [];
    for (var node of current) {
      cb(node);
      if (node.left) next.push(node.left);
      if (node.right) next.push(node.right);
    }
    current = next;
  }
}

// Example:
traverse(root, function(node) {
  console.log(node.value);
});

它的工作原理是保留一个已发现或遍历的节点数组 current，该数组最初仅包含您的根节点。现在，您迭代地用它的子节点替换该列表中的每个节点。在上面的函数中，子项存储在 next 数组中。在每次迭代结束时，current 中当前级别的所有节点都被替换为 next 中下一个更深级别的所有子节点。另见 .

给出的第一个建议

非递归方法的优点是不受调用堆栈大小限制。这在理论上允许您在 call stack size is limited.

时处理更大的数据结构

Answer 2

如果您正在寻找一种使用 O(1) 内存进行 BFS 的方法，我认为没有好的方法可以做到。（不过 DFS 是另一回事。你确定它必须是 BFS 吗？）

我认为有两种方法可以做到这一点。您可以从数组 [this.root] 开始，编写一个函数来遍历节点数组，然后 returns 这些节点的子节点数组。然后在子数组上调用该函数，并继续沿着树向下走，直到得到一个空数组。

如果内存有问题，还有另一种方法可以解决。您可以只记住深度，然后每次都重新进行迭代，而不是记住给定级别的节点数组。所以你会有一个函数，它接受一个自然数 n 并遍历树，但不会比 n 更深，并且在 [=11] 处做你想做的任何事情=]仅第级；然后为 n 的所有值调用此函数，直到没有更多节点剩余。

最后一个听起来很浪费，但如果树的最后几层包含大部分节点，那可能还不算太糟糕。这取决于您的数据集和计算能力。

广度优先搜索二叉搜索树javascript实现

Breadth first search binary search tree javascript implementation

javascript

data-structures

binary-search-tree

traversal

recursive-datastructures