|
1 | 1 | /** |
2 | | - *@typedef {Object} Callbacks |
3 | | - *@property {function(node: BinaryTreeNode, child: BinaryTreeNode): boolean} allowTraversal - |
4 | | - * Determines whether DFS should traverse from the node to its child. |
| 2 | + *@typedef {Object} TraversalCallbacks |
| 3 | + * |
| 4 | + *@property {function(node: BinaryTreeNode, child: BinaryTreeNode): boolean} allowTraversal |
| 5 | + * - Determines whether DFS should traverse from the node to its child. |
| 6 | + * |
5 | 7 | *@property {function(node: BinaryTreeNode)} enterNode - Called when DFS enters the node. |
| 8 | + * |
6 | 9 | *@property {function(node: BinaryTreeNode)} leaveNode - Called when DFS leaves the node. |
7 | 10 | */ |
8 | 11 |
|
9 | 12 | /** |
10 | | - *@param {Callbacks} [callbacks] |
11 | | - *@returns {Callbacks} |
| 13 | + * Extend missing traversal callbacks with default callbacks. |
| 14 | + * |
| 15 | + *@param {TraversalCallbacks} [callbacks] - The object that contains traversal callbacks. |
| 16 | + *@returns {TraversalCallbacks} - Traversal callbacks extended with defaults callbacks. |
12 | 17 | */ |
13 | 18 | functioninitCallbacks(callbacks={}){ |
14 | | -constinitiatedCallback=callbacks; |
| 19 | +// Init empty callbacks object. |
| 20 | +constinitiatedCallbacks={}; |
15 | 21 |
|
| 22 | +// Empty callback that we will use in case if user didn't provide real callback function. |
16 | 23 | conststubCallback=()=>{}; |
17 | | -constdefaultAllowTraversal=()=>true; |
| 24 | +// By default we will allow traversal of every node |
| 25 | +// in case if user didn't provide a callback for that. |
| 26 | +constdefaultAllowTraversalCallback=()=>true; |
18 | 27 |
|
19 | | -initiatedCallback.allowTraversal=callbacks.allowTraversal||defaultAllowTraversal; |
20 | | -initiatedCallback.enterNode=callbacks.enterNode||stubCallback; |
21 | | -initiatedCallback.leaveNode=callbacks.leaveNode||stubCallback; |
| 28 | +// Copy original callbacks to our initiatedCallbacks object or use default callbacks instead. |
| 29 | +initiatedCallbacks.allowTraversal=callbacks.allowTraversal||defaultAllowTraversalCallback; |
| 30 | +initiatedCallbacks.enterNode=callbacks.enterNode||stubCallback; |
| 31 | +initiatedCallbacks.leaveNode=callbacks.leaveNode||stubCallback; |
22 | 32 |
|
23 | | -returninitiatedCallback; |
| 33 | +// Returned processed list of callbacks. |
| 34 | +returninitiatedCallbacks; |
24 | 35 | } |
25 | 36 |
|
26 | 37 | /** |
27 | | - *@param {BinaryTreeNode} node |
28 | | - *@param {Callbacks} callbacks |
| 38 | + * Recursive depth-first-search traversal for binary. |
| 39 | + * |
| 40 | + *@param {BinaryTreeNode} node - binary tree node that we will start traversal from. |
| 41 | + *@param {TraversalCallbacks} callbacks - the object that contains traversal callbacks. |
29 | 42 | */ |
30 | 43 | exportfunctiondepthFirstSearchRecursive(node,callbacks){ |
| 44 | +// Call the "enterNode" callback to notify that the node is going to be entered. |
31 | 45 | callbacks.enterNode(node); |
32 | 46 |
|
33 | | -// Traverse left branch. |
| 47 | +// Traverse left branch only if case if traversal of the left node is allowed. |
34 | 48 | if(node.left&&callbacks.allowTraversal(node,node.left)){ |
35 | 49 | depthFirstSearchRecursive(node.left,callbacks); |
36 | 50 | } |
37 | 51 |
|
38 | | -// Traverse right branch. |
| 52 | +// Traverse right branch only if case if traversal of the right node is allowed. |
39 | 53 | if(node.right&&callbacks.allowTraversal(node,node.right)){ |
40 | 54 | depthFirstSearchRecursive(node.right,callbacks); |
41 | 55 | } |
42 | 56 |
|
| 57 | +// Call the "leaveNode" callback to notify that traversal |
| 58 | +// of the current node and its children is finished. |
43 | 59 | callbacks.leaveNode(node); |
44 | 60 | } |
45 | 61 |
|
46 | 62 | /** |
47 | | - *@param {BinaryTreeNode} rootNode |
48 | | - *@param {Callbacks} [callbacks] |
| 63 | + * Perform depth-first-search traversal of the rootNode. |
| 64 | + * For every traversal step call "allowTraversal", "enterNode" and "leaveNode" callbacks. |
| 65 | + * See TraversalCallbacks type definition for more details about the shape of callbacks object. |
| 66 | + * |
| 67 | + *@param {BinaryTreeNode} rootNode - The node from which we start traversing. |
| 68 | + *@param {TraversalCallbacks} [callbacks] - Traversal callbacks. |
49 | 69 | */ |
50 | 70 | exportdefaultfunctiondepthFirstSearch(rootNode,callbacks){ |
51 | | -depthFirstSearchRecursive(rootNode,initCallbacks(callbacks)); |
| 71 | +// In case if user didn't provide some callback we need to replace them with default ones. |
| 72 | +constprocessedCallbacks=initCallbacks(callbacks); |
| 73 | + |
| 74 | +// Now, when we have all necessary callbacks we may proceed to recursive traversal. |
| 75 | +depthFirstSearchRecursive(rootNode,processedCallbacks); |
52 | 76 | } |