Algorithm to print a tree

Hi all,

I am writing a plugin for Xojo and I am struggling to write the algorithm to accomplish the following (simple) task. Image a tree like this:

A0 B0 C0 D0 E0
      |
      C1 D1 E1
      |
      C2 D2 

Of course it is stored in a tree, where each node has a pointer to the parent and a vector of pointers to the childs (it is a multiway tree). Something like this:

struct Node {
    Data          m_data;
    Node*         m_prev;
    vector<Node*> m_next;
}

I would like to write an iterative Print function to write the tree like this:

A0 B0 C0  
   1: C1 D1 E1 
   2: C2 D2
D0 E0

However I fail in correctly navigate trough the childs in case of multiple childs. Any suggestions?

Thank you very much.

Cheers,
Davide

ciao Davide (credo tu sia italiano).
Io ho dovuto fare una cosa simile, su volumi di dati comunque ridotti.
I miei dati stavano su un database e ho sfruttato questa entità (potresti usare un database Sqlite in memoria, creato a runtime).

Immagina una tabella “nodo”, contenente la colonna “padre”. Fai una SELECT su tutti i record che hanno la colonna “padre” NON valorizzata. Poi, in cascata, ricorsivamente, per ogni nodo X, cerchi i nodi che hanno come padre appunto X, e via dicendo, appunto in maniera ricorsiva.
Forse non è molto efficiente, ma funziona :slight_smile:

The keyword to search for ist “self referenced”. I’d suggest to make use of a self-referenced datasource, for instance a database table, where each record has a pointer to a parent (no need to reference the children). Then you make use of recursive functions to build nodes, sub-nodes, sub-sub-nodes and so forth.

Search for treeview recursion, treeview from a self referencing data table, and the like.
There used to be plenty of examples on the former Realbasic forum, now gone …

I found an old sample project to build a tree recursively, from a database table:

Check out the load_tree and find_node methods in Window1. If you use Windows, then you will need to create a CopyFile BuildStep for the treeview.rsd Sqlite database file, for macOS it is already there.

A zip file with that Xojo project can be download from here:
https://nws-informatik.ch/download/treeview-recursive.zip

EDIT: Requires the Einhugur TreeView control.

Check out the visitor pattern for tasks like this. It’s well explained in one of Bob Nystrom’s online books: Representing Code · Crafting Interpreters

1 Like

Thank you very much for all the suggestion. I will take a look at them.

That is a great link Garry - thanks!

That book is without a doubt the best programming book I’ve ever read by a country mile.

2 Likes

Having read a chapter online for free I think I’ll buy the actual paper book - really enjoying it so far.

I have the printed book too. It’s lovingly made as well. I also recommend his other programming book (again free online): https://gameprogrammingpatterns.com/