Is there a standard name for this tree structure?

Alf P. Steinbach alfps at start.no
Sun Apr 4 14:34:47 CEST 2010


* Steven D'Aprano:
> I have a hierarchical structure something like a directory tree or a 
> nested tree structure:
> 
> Mammal
> +-- Ape
> :   +-- Chimpanzee
> :   +-- Gorilla
> :   +-- Human
> +-- Carnivore
> :   +-- Cat
> :       +-- Tiger
> Reptile
> +-- Lizard
> +-- Snake
>     +-- Cobra
>     +-- Python
> 
> This is a forest because each top-level element (Mammal, Reptile) is 
> itself a tree. By adding a root to the (former) top-level elements, I 
> turn it into a single tree.
> 
> I can implement this tree using a flat dict:
> 
> root = object()
> data = {root: ['Mammal', 'Reptile'], 
>     'Mammal': ['Ape', 'Carnivore'],
>     'Ape': ['Chimpanzee', 'Gorilla', 'Human'],
>     'Reptile': ['Lizard', 'Snake'],
>     # fill in the rest yourself... 
>     }
> 
> 
> Is there a particular name for this structure? I've been calling it a 
> dict-based flattened tree, but I can't shake the feeling that there is 
> another name for it...

The only difference from an ordinary tree is that you have a provided a way to 
access non-root nodes (with strings as keys) that doesn't work for the root node.

Still, all nodes can be accessed with objects as keys.

So, you have just introduced some ambiguity that allows both views: it's a tree, 
and it's a forest, depending on what point of view one chooses.

In passing, this terminology is the one used in programming and computer science.

Donald Knuth notes that for e.g. a binary tree, if one (impractically) adopted 
the terminology of some authors on graph theory then one would have to say 
"topological bifurcating arborescence" instead of "binary tree"...


Cheers & hth.,

- Alf



More information about the Python-list mailing list