广度优先搜索二叉搜索树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中的所有子级的下一个更深级别的子级所替换。另见@DavidKnipe's answer给出的第一个建议。

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

Answer 2

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

有两种方法可以看到要做到这一点。您可以从数组[this.root]开始，然后编写一个迭代节点数组的函数，然后返回这些节点的子数组。然后在子数组上调用该函数，然后继续向下，直到获得一个空数组。

如果内存问题，还有另一种方法可以做到这一点。不要记住给定级别的节点数组，而只需记住深度，然后每次重做迭代。所以你会有一个函数，它需要一个自然数n并迭代树，但不会超过n，并且只做你想要在n th级别上做的任何事情;然后调用此函数获取所有值n，直到没有更多节点离开。

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