csPost.js (1168B)
1 import { csTdfs } from './csTdfs.js'; 2 /** 3 * Post order a tree of forest 4 * 5 * @param {Array} parent The tree or forest 6 * @param {Number} n Number of columns 7 * 8 * Reference: http://faculty.cse.tamu.edu/davis/publications.html 9 */ 10 11 export function csPost(parent, n) { 12 // check inputs 13 if (!parent) { 14 return null; 15 } // vars 16 17 18 var k = 0; 19 var j; // allocate result 20 21 var post = []; // (n) 22 // workspace, head: first n entries, next: next n entries, stack: last n entries 23 24 var w = []; // (3 * n) 25 26 var head = 0; 27 var next = n; 28 var stack = 2 * n; // initialize workspace 29 30 for (j = 0; j < n; j++) { 31 // empty linked lists 32 w[head + j] = -1; 33 } // traverse nodes in reverse order 34 35 36 for (j = n - 1; j >= 0; j--) { 37 // check j is a root 38 if (parent[j] === -1) { 39 continue; 40 } // add j to list of its parent 41 42 43 w[next + j] = w[head + parent[j]]; 44 w[head + parent[j]] = j; 45 } // loop nodes 46 47 48 for (j = 0; j < n; j++) { 49 // skip j if it is not a root 50 if (parent[j] !== -1) { 51 continue; 52 } // depth-first search 53 54 55 k = csTdfs(j, k, w, head, next, post, stack); 56 } 57 58 return post; 59 }