Tree traversal: Difference between revisions
→{{header|J}}
Line 2,491:
Syntactically, N2 is a binary node expressed as <code>m N2 n y</code>. N1 is a node with a single child, expressed as <code>m N2 y</code>. L is a leaf node, expressed as <code>m L</code>. In all three cases, the parent value (<code>m</code>) for the node appears on the left, and the child tree(s) appear on the right. (And <code>n</code> must be parenthesized if it is not a single word.)
=== J: Alternate implementation ===
Of course, there are other ways of representing tree structures in J. One fairly natural approach pairs a list of data with a matching list of parent indices. For example:
<lang J>example=:1 8 3 4 7 5 9 6 2,: 0 7 0 8 3 8 7 2 0</lang>
Here, we have two possible ways of identifying the root node. It can be in a known place in the list (index 0, for this example). But it is also the only node which is its own parent. For this task we'll use the more general (and thus slower) approach which allows us to place the root node anywhere in the sequence.
Next, let's define a few utilities:
<lang J>depth=: +/@((~: , (~: i.@#@{.)~) {:@,)@({~^:a:)
reorder=:4 :0
'data parent'=. y
data1=. x{data
parent1=. x{data1 i. parent{data
if. 0=L.y do. data1,:parent1 else. data1;parent1 end.
)
data=:3 :'data[''data parent''=. y'
parent=:3 :'parent[''data parent''=. y'</lang>
Here, <code>data</code> extracts the list of data items from the tree and <code>parent</code> extracts the structure from the tree.
<code>depth</code> examines the parent structure and returns the distance of each node from the root.
<code>reorder</code> is like indexing, except that it returns an equivalent tree (with the structural elements updated to maintain the original tree structure). The left argument for reorder should select the entire tree. Selecting partial trees is a more complex problem which needs specifications about how to deal with issues such as dangling roots and multiple roots. (Our abstraction here has no problem ''representing'' trees with multiple roots, but they are not relevant to this task.)
Next, we define our "traversal" routines (actually, we are going a bit overboard here - we really only need to extract the data for this tasks's concept of traversal):
<lang J>dataorder=: /:@data reorder ]
levelorder=: /:@depth@parent reorder ]
inorder=: inperm@parent reorder ]
inperm=:3 :0
chil=. childinds y
node=. {.I.(= i.@#) y
todo=. i.0 2
r=. i.0
whilst. (#todo)+.0<:node do.
if. 0 <: node do.
if. 0 <: {.ch=. node{chil do.
todo=. todo, node,{:ch
node=. {.ch
else.
r=. r, node
node=. _1 end.
else.
r=. r, {.ch=. {: todo
todo=. }: todo
node=. {:ch end. end.
r
)
postorder=: postperm@parent reorder ]
postperm=:3 :0
chil=. 0,1+childinds y
todo=. 1+I.(= i.@#) y
r=. i.0
whilst. (#todo) do.
node=. {: todo
todo=. }: todo
if. 0 < node do.
if. #ch=. (node{chil)-.0 do.
todo=. todo,(-node),|.ch
else.
r=. r, <:node end.
else.
r=. r, <:|node end. end.
)
preorder=: preperm@parent reorder ]
preperm=:3 :0
chil=. childinds y
todo=. I.(= i.@#) y
r=. i.0
whilst. (#todo) do.
r=. r,node=. {: todo
todo=. }: todo
if. #ch=. (node{chil)-._1 do.
todo=. todo,|.ch end. end.
r
)</lang>
These routines assume that children of a node are arranged so that the lower index appears to the left of the higher index. If instead we wanted to rely on the ordering of their values, we could first use <code>dataorder</code> to enforce the assumption that child indexes are ordered properly.
Example use:
<lang J> levelorder example
1 3 2 4 5 6 8 7 9
0 0 0 2 2 1 5 3 5
inorder example
8 6 9 3 1 7 4 2 5
1 3 1 4 4 6 7 4 7
postorder example
8 9 6 3 7 4 5 2 1
2 2 3 8 5 7 7 8 8
preorder example
1 3 6 8 9 2 4 7 5
0 0 1 2 2 0 5 6 5</lang>
(Once again, all we really need for this task is the first row of those results - the part that represents data.)
=={{header|Java}}==
| |||