Guest User

Untitled

a guest
Jan 16th, 2019
68
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.30 KB | None | 0 0
  1. ```javascript
  2. // Root node does not have a parent
  3. // Nodes have only one parent
  4. // Three does no have cicle
  5.  
  6. // A
  7. // / \
  8. // B C
  9. // / \ / \
  10. // D E F G
  11.  
  12. const root = new TreeNode({value: 'A'});
  13.  
  14. const nodeB = root.setLeftNode('B');
  15. nodeB.setLeftNode('D');
  16. nodeB.setRightNode('E');
  17.  
  18. const nodeC = root.setRightNode('C');
  19. nodeC.setLeftNode('F');
  20. nodeC.setRightNode('G');
  21.  
  22. const binaryTree = new BinaryTree(root);
  23.  
  24. // Deep First Search (DFS)
  25. binaryTree.preOrder();
  26. binaryTree.print(); // A B D E C F G
  27.  
  28. // Deep First Search (DFS)
  29. binaryTree.postOrder();
  30. binaryTree.print(); // D E B F G C A
  31.  
  32.  
  33. // Deep First Search (DFS)
  34. binaryTree.inOrder();
  35. binaryTree.print(); // D B E A F C G
  36.  
  37. // Breadth First Search (BFS)
  38. binaryTree.levelOrder();
  39. binaryTree.print(); // A B C D E F G
  40.  
  41. function TreeNode({value, parentNode}) {
  42. this.value = value;
  43. this.parentNode = parentNode;
  44. this.leftNode = null;
  45. this.rightNode = null;
  46. this.visited = false;
  47.  
  48. this.visit = () => {
  49. this.visited = true;
  50. return this;
  51. };
  52.  
  53. this.getLeftChildren = () => this.leftNode;
  54.  
  55. this.setLeftNode = leftNode => {
  56. this.leftNode = new TreeNode({value: leftNode, parentNode: this});
  57. return this.leftNode;
  58. };
  59.  
  60. this.getRightChildren = () => this.rightNode;
  61.  
  62. this.setRightNode = rightNode => {
  63. this.rightNode = new TreeNode({value: rightNode, parentNode: this});
  64. return this.rightNode;
  65. };
  66. }
  67.  
  68. function BinaryTree(root) {
  69. this.root = root;
  70. this.nodesVisited = [];
  71.  
  72. this.preOrder = () => {
  73. this.nodesVisited = [];
  74. this._preOrder(root);
  75. };
  76. this._preOrder = node => {
  77. if (node != null) {
  78. const nodeVisited = node.visit();
  79. this.nodesVisited.push(nodeVisited);
  80.  
  81. this._preOrder(node.getLeftChildren());
  82. this._preOrder(node.getRightChildren());
  83. }
  84. };
  85.  
  86. this.postOrder = () => {
  87. this.nodesVisited = [];
  88. this._postOrder(root);
  89. };
  90. this._postOrder = node => {
  91. if (node != null) {
  92. this._postOrder(node.getLeftChildren());
  93. this._postOrder(node.getRightChildren());
  94.  
  95. const nodeVisited = node.visit();
  96. this.nodesVisited.push(nodeVisited);
  97. }
  98. };
  99.  
  100. this.inOrder = () => {
  101. this.nodesVisited = [];
  102. this._inOrder(root);
  103. };
  104. this._inOrder = node => {
  105. if (node != null) {
  106. this._inOrder(node.getLeftChildren());
  107.  
  108. const nodeVisited = node.visit();
  109. this.nodesVisited.push(nodeVisited);
  110.  
  111. this._inOrder(node.getRightChildren());
  112. }
  113. };
  114.  
  115. this.levelOrder = () => {
  116. this.nodesVisited = [];
  117. this._levelOrder(root);
  118. };
  119. this._levelOrder = node => {
  120. let current = null;
  121. this.tempNodesVisited = [];
  122. this.tempNodesVisited.push(node);
  123.  
  124. while (this.tempNodesVisited.length !== 0) {
  125. current = this.tempNodesVisited.shift();
  126. this.nodesVisited.push(current);
  127.  
  128. if (current.getLeftChildren() != null) {
  129. this.tempNodesVisited.push(current.getLeftChildren());
  130. }
  131.  
  132. if (current.getRightChildren() != null) {
  133. this.tempNodesVisited.push(current.getRightChildren());
  134. }
  135. }
  136. };
  137.  
  138. this.print = () => {
  139. console.log(this.nodesVisited.map(n => n.value));
  140. };
  141. }
  142. ```
Add Comment
Please, Sign In to add comment