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 | let top = 0
|
17 | // place j on the stack
|
18 | w[stack] = j
|
19 | // while (stack is not empty)
|
20 | while (top >= 0) {
|
21 | // p = top of stack
|
22 | const p = w[stack + top]
|
23 | // i = youngest child of p
|
24 | const i = w[head + p]
|
25 | if (i === -1) {
|
26 | // p has no unordered children left
|
27 | top--
|
28 | // node p is the kth postordered node
|
29 | post[k++] = p
|
30 | } else {
|
31 | // remove i from children of p
|
32 | w[head + p] = w[next + i]
|
33 | // increment top
|
34 | ++top
|
35 | // start dfs on child node i
|
36 | w[stack + top] = i
|
37 | }
|
38 | }
|
39 | return k
|
40 | }
|