csTdfs.js (1228B)
1 /** 2 * Depth-first search and postorder of a tree rooted at node j 3 * 4 * @param {Number} j The tree node 5 * @param {Number} k 6 * @param {Array} w The workspace array 7 * @param {Number} head The index offset within the workspace for the head array 8 * @param {Number} next The index offset within the workspace for the next array 9 * @param {Array} post The post ordering array 10 * @param {Number} stack The index offset within the workspace for the stack array 11 * 12 * Reference: http://faculty.cse.tamu.edu/davis/publications.html 13 */ 14 export function csTdfs(j, k, w, head, next, post, stack) { 15 // variables 16 var top = 0; // place j on the stack 17 18 w[stack] = j; // while (stack is not empty) 19 20 while (top >= 0) { 21 // p = top of stack 22 var p = w[stack + top]; // i = youngest child of p 23 24 var i = w[head + p]; 25 26 if (i === -1) { 27 // p has no unordered children left 28 top--; // node p is the kth postordered node 29 30 post[k++] = p; 31 } else { 32 // remove i from children of p 33 w[head + p] = w[next + i]; // increment top 34 35 ++top; // start dfs on child node i 36 37 w[stack + top] = i; 38 } 39 } 40 41 return k; 42 }