javascript二叉搜索树的实现

Question

任何人都知道Javascript中简单的BTree实现的任何好例子？我有一堆随机到达的“东西”，并且想要有效地插入每一个东西。

最终，每个新的将根据它在树中的最终位置插入到DOM中。

我可以从头开始编码，但宁愿不要重新发明任何车轮。

谢谢

Answer 1

这有帮助吗？ - Computer science in JavaScript: Binary search tree, Part 1

Answer 2

如果它的事项，我发现，存储这种数据作为文字树是不是把它作为一个已经排序的阵列和阵列上执行二进制搜索拼接/插入元素效率较低。显然，JavaScript对象的创建并不是免费的。

还有醇”编码-A-树功能于一个阵列特技：

[5, 3, 7, 1, null, 6, 9, null, null, null, null, null, null] 

相同

 5 
    /\ 
    3 7 
//\ 
    1 6 9 

即儿童（N [1]）= N [2i + 1]，N [2i + 2]。我不知道这是否真的让你赢得任何JavaScript的胜利。

如果您尝试了二叉树的一些替代方法，您可以在此发布您的发现吗？ :)

Answer 3

你可以试试buckets，一个JavaScript库，它拥有你需要的一切。

Answer 4

https://gist.github.com/alexhawkins/f993569424789f3be5db

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

BinarySearchTree.prototype.makeNode = function(value) { 
    var node = {}; 
    node.value = value; 
    node.left = null; 
    node.right = null; 
    return node; 
}; 

BinarySearchTree.prototype.add = function(value) { 
    var currentNode = this.makeNode(value); 
    if (!this.root) { 
     this.root = currentNode; 
    } else { 
     this.insert(currentNode); 
    } 
    return this; 
}; 

BinarySearchTree.prototype.insert = function(currentNode) { 
    var value = currentNode.value; 
    var traverse = function(node) { 
     //if value is equal to the value of the node, ignore 
     //and exit function since we don't want duplicates 
     if (value === node.value) { 
      return; 
     } else if (value > node.value) { 
      if (!node.right) { 
       node.right = currentNode; 
       return; 
      } else 
       traverse(node.right); 
     } else if (value < node.value) { 
      if (!node.left) { 
       node.left = currentNode; 
       return; 
      } else 
       traverse(node.left); 
     } 
    }; 
    traverse(this.root); 
}; 


BinarySearchTree.prototype.contains = function(value) { 
    var node = this.root; 
    var traverse = function(node) { 
     if (!node) return false; 
     if (value === node.value) { 
      return true; 
     } else if (value > node.value) { 
      return traverse(node.right); 
     } else if (value < node.value) { 
      return traverse(node.left); 
     } 
    }; 
    return traverse(node); 
}; 


/* BREADTH FIRST TREE TRAVERSAL */ 

/* Breadth First Search finds all the siblings at each level 
    in order from left to right or from right to left. */ 

BinarySearchTree.prototype.breadthFirstLTR = function() { 
    var node = this.root; 
    var queue = [node]; 
    var result = []; 
    while (node = queue.shift()) { 
     result.push(node.value); 
     node.left && queue.push(node.left); 
     node.right && queue.push(node.right); 
    } 
    return result; 
}; 


BinarySearchTree.prototype.breadthFirstRTL = function() { 
    var node = this.root; 
    var queue = [node]; 
    var result = []; 
    while (node = queue.shift()) { 
     result.push(node.value); 
     node.right && queue.push(node.right); 
     node.left && queue.push(node.left); 
    } 
    return result; 
}; 

/*DEPTH FIRST TRAVERSALS*/ 

/* preOrder is a type of depth-first traversal that tries 
    togo deeper in the tree before exploring siblings. It 
    returns the shallowest descendants first. 

    1) Display the data part of root element (or current element) 
    2) Traverse the left subtree by recursively calling the pre-order function. 
    3) Traverse the right subtree by recursively calling the pre-order function. */ 

BinarySearchTree.prototype.preOrder = function() { 
    var result = []; 
    var node = this.root; 
    var traverse = function(node) { 
     result.push(node.value); 
     node.left && traverse(node.left); 
     node.right && traverse(node.right); 
    }; 
    traverse(node); 
    return result; 
}; 

/* inOrder traversal is a type of depth-first traversal 
    that also tries to go deeper in the tree before exploring siblings. 
    however, it returns the deepest descendents first 

    1) Traverse the left subtree by recursively calling the pre-order function. 
    2) Display the data part of root element (or current element) 
    3) Traverse the right subtree by recursively calling the pre-order function. */ 

BinarySearchTree.prototype.inOrder = function() { 
    var result = []; 
    var node = this.root; 
    var traverse = function(node) { 
     node.left && traverse(node.left); 
     result.push(node.value); 
     node.right && traverse(node.right); 
    }; 
    traverse(node); 
    return result; 
}; 

/* postOrder traversal is a type of depth-first traversal 
    that also tries to go deeper in the tree before exploring siblings. 
    however, it returns the deepest descendents first 

    1) Traverse the left subtree by recursively calling the pre-order function. 
    2) Display the data part of root element (or current element) 
    3) Traverse the right subtree by recursively calling the pre-order function. */ 


BinarySearchTree.prototype.postOrder = function() { 
    var result = []; 
    var node = this.root; 
    var traverse = function(node) { 
     node.left && traverse(node.left); 
     node.right && traverse(node.right); 
     result.push(node.value); 
    }; 
    traverse(node); 
    return result; 
}; 

//find the left most node to find the min value of a binary tree; 
BinarySearchTree.prototype.findMin = function() { 
    var node = this.root; 
    var traverse = function(node) { 
     return !node.left ? node.value : traverse(node.left); 
    }; 
    return traverse(node); 
}; 

//find the right most node to find the max value of a binary tree; 
BinarySearchTree.prototype.findMax = function() { 
    var node = this.root; 
    var traverse = function(node) { 
     return !node.right ? node.value : traverse(node.right); 
    }; 
    return traverse(node); 
}; 


BinarySearchTree.prototype.getDepth = function() { 
    var node = this.root; 
    var maxDepth = 0; 
    var traverse = function(node, depth) { 
     if (!node) return null; 
     if (node) { 
      maxDepth = depth > maxDepth ? depth : maxDepth; 
      traverse(node.left, depth + 1); 
      traverse(node.right, depth + 1); 
     } 
    }; 
    traverse(node, 0); 
    return maxDepth; 
}; 


//Can you write me a function that returns all the averages of the nodes 
//at each level (or depth)?? with breadth-first traversal 


BinarySearchTree.prototype.nodeAverages = function() { 
    var node = this.root; 
    var result = {}; 
    var depthAverages = []; 

    var traverse = function(node, depth) { 
     if (!node) return null; 
     if (node) { 
      if (!result[depth]) 
       result[depth] = [node.value]; 
      else 
       result[depth].push(node.value); 
     } 
     //check to see if node is a leaf, depth stays the same if it is 
     //otherwise increment depth for possible right and left nodes 
     if (node.right || node.left) { 
      traverse(node.left, depth + 1); 
      traverse(node.right, depth + 1); 
     } 
    }; 
    traverse(node, 0); 

    //get averages and breadthFirst 
    for (var key in result) { 
     var len = result[key].length; 
     var depthAvg = 0; 
     for (var i = 0; i < len; i++) { 
      depthAvg += result[key][i]; 
     } 
     depthAverages.push(Number((depthAvg/len).toFixed(2))); 
    } 
    return depthAverages; 
}; 

//Convert a binary search tree to a linked-list in place. 
//In-order depth-first traversal. 
function LinkedList() { 
    this.head = null; 
} 

BinarySearchTree.prototype.convertToLinkedList = function() { 

    var result = []; 
    var node = this.root; 
    if (!node) return null; 

    var traverse = function(node) { 
     node.left && traverse(node.left); 
     result.push(node.value); 
     node.right && traverse(node.right); 
    }; 

    traverse(node); 

    var makeNode = function(value) { 
     var node = {}; 
     node.value = value; 
     node.next = null; 
     return node; 
    }; 

    var list = new LinkedList(); 
    list.head = makeNode(result[0]); 
    var current = list.head; 

    for (var i = 1; i < result.length; i++) { 
     var currentNode = makeNode(result[i]); 
     current.next = currentNode; 
     current = current.next; 
    } 
    return list; 
}; 

//TESTS 

var bst = new BinarySearchTree(); 
bst.add(40).add(25).add(78).add(10).add(32); 
console.log('BS1', bst); 

var bst2 = new BinarySearchTree(); 
bst2.add(10).add(20).add(30).add(5).add(8).add(3).add(9); 
console.log('BST2', bst2); 
console.log('BREADTHFIRST LTR', bst2.breadthFirstLTR()); 
console.log('BREADTHFIRST RTL', bst2.breadthFirstRTL()); 
console.log('PREORDER', bst2.preOrder()); 
console.log('INORDER', bst2.inOrder()); 
console.log('POSTORDER', bst2.postOrder()); 

/* 
BREADTHFIRST LTR [ 10, 5, 20, 3, 8, 30, 9 ] 
BREADTHFIRST RTL [ 10, 20, 5, 30, 8, 3, 9 ] 
PREORDER [ 10, 5, 3, 8, 9, 20, 30 ] 
INORDER [ 3, 5, 8, 9, 10, 20, 30 ] 
POSTORDER [ 3, 9, 8, 5, 30, 20, 10 ] 
*/ 

var bst3 = new BinarySearchTree(); 
bst3.add('j').add('f').add('k').add('z').add('a').add('h').add('d'); 
console.log(bst3); 
console.log('BREADTHFIRST LTR', bst3.breadthFirstLTR()); 
console.log('BREADTHFIRST RTL', bst3.breadthFirstRTL()); 
console.log('PREORDER', bst3.preOrder()); 
console.log('INORDER', bst3.inOrder()); 
console.log('POSTORDER', bst3.postOrder()); 

/* 
BREADTHFIRST LTR [ 'j', 'f', 'k', 'a', 'h', 'z', 'd' ] 
BREADTHFIRST RTL [ 'j', 'k', 'f', 'z', 'h', 'a', 'd' ] 
PREORDER [ 'j', 'f', 'a', 'd', 'h', 'k', 'z' ] 
INORDER [ 'a', 'd', 'f', 'h', 'j', 'k', 'z' ] 
POSTORDER [ 'd', 'a', 'h', 'f', 'z', 'k', 'j' ] 
*/ 


console.log(bst2.findMin()); // 3 
console.log(bst2.findMax()); // 30 
console.log(bst2.contains(15)); 
//bst2.add(55); 
//bst2.add(65); 
//bst3.add(75); 
console.log(bst2); 
console.log(bst2.getDepth()); // 3 
console.log(bst2.add(7).add(50).add(80).add(98)); 
console.log(bst2.getDepth()); // 5 
console.log(bst2.nodeAverages()); //[ 10, 12.5, 13.67, 22, 80, 98 ] 

console.log(bst2.convertToLinkedList()); 
//[ 3, 5, 7, 8, 9, 10, 20, 30, 50, 80, 98 ] 
//{ head: { value: 3, next: { value: 5, next: [Object] } } } 

Answer 5

二叉搜索树通常知道作为BST是一种特殊类型的在自然界中排序树。在二叉搜索树中，每个节点比其左侧的孩子大，而且小于其右侧的孩子。此功能可以轻松地从二叉搜索树中搜索，插入和删除节点。

ALGO

//检查根节点为空或不

//如果是，则分配新的节点根

//如果没有超过迭代。迭代方法将检查当前处理节点的左右子节点添加的节点值。

//如果节点值增加率比招寿左子节点较少

//如果离开孩子是空的不是新节点分配给该左子节点

//调用其他迭代方法

//如果节点值增加大于比移动到右子节点值

//如果右子是空的比新节点分配到此右子节点

//调用其他迭代法

如果这可以帮助你可以看看这里Binary Search Tree Insert node Implementation in Javascript