Algorithm to print a tree

General
1

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

2

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:

3

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 …

4

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

Bildschirmfoto 2022-09-20 um 10.40.40
Bildschirmfoto 2022-09-20 um 10.40.40832Ă—1080 316 KB

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.

5

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
6

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

7

That is a great link Garry - thanks!

8

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

2 Likes
9

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

10

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/