Guest User

Untitled

a guest
Jan 22nd, 2019
74
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.81 KB | None | 0 0
  1. class Node {
  2. constructor(value) {
  3. this.left = null;
  4. this.right = null;
  5. this.value = value;
  6. }
  7. }
  8.  
  9. class BinarySearchTree {
  10. constructor() {
  11. this.root = null;
  12. }
  13. insert(value) {
  14. const newNode = new Node(value);
  15. if (this.root == null) {
  16. this.root = newNode;
  17. } else {
  18. let currentNode = this.root;
  19. while (true) {
  20. if (value < currentNode.value) {
  21. // left
  22. if (!currentNode.left) {
  23. currentNode.left = newNode;
  24. return this;
  25. }
  26. currentNode = currentNode.left;
  27.  
  28. } else {
  29. // right
  30. if (!currentNode.right) {
  31. if (!currentNode.right) {
  32. currentNode.right = newNode;
  33. return this;
  34. }
  35. currentNode = currentNode.right;
  36. }
  37. }
  38. }
  39. }
  40. }
  41. lookup(value){
  42. if(!this.root){
  43. return false;
  44. }
  45. let currentNode = this.root;
  46. while(currentNode!=null){
  47. if(currentNode.value ==value){
  48. return currentNode;
  49. }else if(currentNode.value < value){
  50. currentNode = currentNode.right;
  51. }else if(currnetNode.value > value){
  52. currentNode = currentNode.left;
  53. }
  54.  
  55. }
  56. return false;
  57.  
  58. }
  59. // remove(value){
  60.  
  61. // }
  62.  
  63. }
  64. // lookup(value){
  65.  
  66. // }
  67. // remove(value){
  68.  
  69.  
  70.  
  71. const tree = new BinarySearchTree();
  72. // myTree.insert
  73. tree.insert(9)
  74. tree.insert(4)
  75. tree.insert(6)
  76. tree.insert(20)
  77. // tree.insert(170)
  78. // tree.insert(15)
  79. // tree.insert(1)
  80. console.log(tree.lookup(9));
  81. // tree.lookup(4);
  82. JSON.stringify(traverse(tree.root))
  83.  
  84. // 9
  85. // 4 20
  86. //1 6 15 170
  87.  
  88. function traverse(node) {
  89. const tree = { value: node.value };
  90. tree.left = node.left === null ? null : traverse(node.left);
  91. tree.right = node.right === null ? null : traverse(node.right);
  92. return tree;
  93. }
Add Comment
Please, Sign In to add comment