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