“Apter trees”

[trx2358...@yahoo.com]

Hi, I’ve not done much scholarship on the origins of this data structure but I have played around quite a bit with trees represented as “parent” vectors.  I’ve taken to calling them Apter trees because Stevan Apter wrote about them in Vector magazine.

http://archive.vector.org.uk/art10500340 

I’ve done a little write-up about them that you might enjoy.  

https://code.jsoftware.com/wiki/User:Doug_Mennella/Trees 

It has a pretty extensive description targeted at beginners of my rendering algorithm as an example of “thinking in arrays”.

It differs quite significantly from Roger Hui’s algorithm which essentially works on parent vectors as well.

https://code.jsoftware.com/wiki/Essays/Tree_Display 

I hope to expand on this article and/or write a companion to cover more tricks you can do with this data structure.

In any event, I hope it is useful.

Regards,

-Doug

Sent from Yahoo Mail for iPhone

[Pawel Jakubas]

Thanks Doug,

Great stuff!

What about adding one more section before Display algo and add there some basic tree algorithms and 4 traversals (level order, inorder, preorder and postorder with a way to inject function)? Would be a great addition IMHO:-)

Best,

Pawel

[trx2358...@yahoo.com]

Thanks!  That’s not a bad idea, though it’s always hard to know how much fun to leave to the reader.

There is already one tree walk in the code in the function dfo which can be adapted to do other work.  The same basic framework was used to compile a parsed regular expression into a state machine in another post.

I’ll try to add a few more words about this.  I’m still relatively new to J but have a few year’s experience with K.

[Igor Zhuravlov]

On Tue, Sep 10, 2024 at 5:09 PM trx2358-discord via forum
<fo...@jsoftware.com> wrote:
> I’ve done a little write-up about them that you might enjoy.
> https://code.jsoftware.com/wiki/User:Doug_Mennella/Trees

Thank you, it is very interesting! I've posted some comments in Discussion
page: https://code.jsoftware.com/wiki/User_talk:Doug_Mennella/Trees

--
Regards,
Igor

[trx2358...@yahoo.com]

Awesome.  Thanks very much.  I’ve already made some edits based on your comments.

[Marcin Żołek]

Pawel,

In the meantime I came up with a non-recursive, fast way to compute level, pre and post order for any rooted tree using J features without performing depth-first search.

To make examples of usage more understandable I used graphviz addon, which is available in Jqt, to visualize example trees.

I put the code with comments and example usage on my github. Just run the following file in Jqt.

https://github.com/kapustaikwas27/graph-algorithms/blob/main/tree.ijs

Graphviz addon uses external program which may require additional (easy) installation described in JWiki.

https://code.jsoftware.com/wiki/Addons/graphics/graphviz

I recommend using graphviz with J9.6.

Marcin

To unsubscribe from this group and stop receiving emails from it, send an email to forum+un...@jsoftware.com.