Advertisement
Guest User

Untitled

a guest
Feb 22nd, 2019
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.42 KB | None | 0 0
  1. function BinarySearchTree() {
  2.  
  3. function Node(value) {
  4. this.value = value;
  5. this.left = null;
  6. this.right = null;
  7. }
  8.  
  9. this.root = null;
  10.  
  11. this.addNode = function(value) {
  12. let node = new Node(value);
  13. if (!this.root) {
  14. this.root = node;
  15. } else {
  16. insertNode(this.root, node);
  17. }
  18. }
  19.  
  20. function insertNode(currentNode, newNode) {
  21. if (newNode.value < currentNode.value) {
  22. if (!currentNode.left) {
  23. currentNode.left = newNode;
  24. } else {
  25. insertNode(currentNode.left, newNode);
  26. }
  27. } else {
  28. if (!currentNode.right) {
  29. currentNode.right = newNode;
  30. } else {
  31. insertNode(currentNode.right, newNode);
  32. }
  33. }
  34. }
  35.  
  36. //Breadh First Traversal method that accepts a callback argument which will be used on each node we traverse
  37. this.breadthFirstTraversal = function(callback) {
  38.  
  39. //Queue data structure to hold our nodes
  40. let queue = [];
  41. //nextNode binding to keep track of the current node we are traversing.
  42. let nextNode;
  43.  
  44. //First push the root node into the queue.
  45. queue.push(this.root);
  46.  
  47. //While we are still traversing the tree and there are still children nodes in the queue.
  48. while(queue.length>0) {
  49. //Remove the first indexed item from the queue array and store it in nextNode.
  50. nextNode = queue.shift();
  51.  
  52. //If the current node we are traversing has a left child, put it into the queue.
  53. if(nextNode.left) {
  54. queue.push(nextNode.left);
  55. }
  56.  
  57. //If the current node we are traversing has a right child, put it into the queue.
  58. if(nextNode.right) {
  59. queue.push(nextNode.right);
  60. }
  61.  
  62. //Perform the callback argument on the node's value.
  63. callback(node.value);
  64.  
  65. //Now if the queue still has nodes in it, the loop will continue to perform the callback and then stop when there are
  66. //no more child nodes.
  67. }
  68. }
  69.  
  70. }
  71.  
  72. let tree = new BinarySearchTree();
  73. tree.addNode(3);
  74. tree.addNode(5);
  75. tree.addNode(14);
  76. tree.addNode(11);
  77. tree.addNode(25);
  78. tree.addNode(2);
  79.  
  80. tree.breadthFirstTraversal(function log(value) {
  81. console.log(value);
  82. });
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement