I'm reading Jorge Gajon's Trees as Linked Lists in Common Lisp, which includes a description of a tree done in Lisp. The author gives this basic example:
Then gives a Lisp list representaton:
(1 (2 6 7 8) 3 (4 (9 12)) (5 10 11))
where position implies hierarchy level: 1 is first in the list, i.e., it's at the top, 2 is at the next level, but it's the top of its level, etc. But then he gives this caveat:
PLEASE NOTE, that if you need to represent trees in a production program you shouldn’t use lists as described here unless you have a good reason. This is only an exercise in understanding how cons cells work.
All right, how should one represent the tree data structure in "production" code? BTW, I'd also like to see an example of an acyclic directed graph, i.e., something tree-like that also has "multiple parent" capabilities. For example in the diagram above, 8 is a child of 2, but also 3. I'm guessing something like this:
(1 (2 6 7 8) (3 8) (4 (9 12)) (5 10 11))
but it seems like I've created a "shadow" twin of 8 and not really relating how the 8 that is the child of 3 is the same 8 that also has 2 as a parent. This problem gets worse if I wanted to have 3 as 12's parent.
(1 (2 6 7 8) (3 8 12) (4 (9 12)) (5 10 11))
The fact that 12 is in a lower hierarchy gets lost in the shuffle, so to speak.
Is there a good and proper treatment (book, etc.) of data structures in the Lisp/Scheme/Clojure world? I've only found one-off stuff like this.
defstructordefclass) to contain the elements and tree structure in separate slots, removing any need to distinguish them. – gsg