Differences between revisions 4 and 5
 ⇤ ← Revision 4 as of 2007-12-07 16:27:05 → Size: 2665 Editor: DevonMcCormick Comment: I want to double-check that I have the full right list correct before I correct ← Revision 5 as of 2008-12-08 10:45:46 → ⇥ Size: 2666 Editor: anonymous Comment: converted to 1.6 markup Deletions are marked like this. Additions are marked like this. Line 4: Line 4: Here's a summary of how the "tree" data structure is handled in the book "[:Essays/Bibliography#APL:A Programming Language]" by Kenneth Iverson (John Wiley and Sons, New York, 1962). Here's a summary of how the "tree" data structure is handled in the book "[[Essays/Bibliography#APL|A Programming Language]]" by Kenneth Iverson (John Wiley and Sons, New York, 1962).

Here's a summary of how the "tree" data structure is handled in the book "A Programming Language" by Kenneth Iverson (John Wiley and Sons, New York, 1962).

In the section in dealing with trees, it looks as though trees are represented by using matrixes. A directed graph is shown represented as a boolean matrix with a one in the row and column where node "row number" goes to node "column number".

What are called "trees" - that is "a graph...which contains no circuits and has at most one branch entering each node is called a tree." (p. 46) can be represented by a "full left list" or "full right list" matrix. An example may help clarify this.

Here is a pair of trees (reading down) represented pictorially in two ways (reading across): as numbered nodes and as index vectors which increase in length as they denote nodes further down from the roots of the trees.

Node Representation         Index Representation

```n1----n2---n3           1----11----111
\    |                 \    |
n4  n5---n6           12   112---1121
|\                     |\
| \                    | \
n7  n8               1123  1122

n9--------n10---n11     2--------21---211
|\        |\            |\        |\
| \       | \           | \       | \
|  \      |  \          |  \      |  \
|   \     |   \         |   \     |   \
n12  n13  n14  n15     23   22   213  212```

This pair of trees may be represented in two different forms as matrixes. What Iverson refers to as Full left list is what we might call "depth first" [well, maybe not - I'm checking this - DHM]; the Full right list version is what we might call "breadth first". The dots in the matrix represent an empty fill element.

Full left list matrix          Full right list matrix

```Node    I'             Node    I''
n1     1 . . .         n1     . . . 1
n2     1 1 . .         n9     . . . 2
n3     1 1 1 .         n2     . . 1 1
n4     1 2 . .         n4     . . 1 2
n5     1 1 2 .         n10    . . 2 1
n6     1 1 2 1         n13    . . 2 2
n7     1 1 2 3         n12    . . 2 3
n8     1 1 2 2         n3     . 1 1 1
n9     2 . . .         n5     . 1 1 2
n10    2 1 . .         n11    . 2 1 1
n11    2 1 1 .         n15    . 2 1 2
n12    2 3 . .         n14    . 2 1 3
n13    2 2 . .         n6     1 1 2 1
n14    2 1 3 .         n8     1 1 2 2
n15    2 1 2 .         n7     1 1 2 3```

In J, we would need to box each element or forgo the fill elements entirely to represent these as vectors of simple numeric vectors.

DevonMcCormick/APLTree (last edited 2008-12-08 10:45:46 by anonymous)