Tree

A tree is an acyclic directed-graph data structure composed of branches. One branch is the trunk, and every other branch stems from it, either directly or indirectly. Trees can be used, e.g., for representing the result in syntax parsing. An XML document is structured as a tree.

EMJ 2021-01-04
So a node is a branch. Is a branch a node? I think this terminology is just confusing and counter-intuitive.
PYK 2021-01-04
One term is needed for the node that does not stem from any other node, and one term is needed for the other nodes. "trunk" and "branch" seemed suitable to me, as they fit it with the analogy to a tree in the physical world. What are the other options?
EMJ 2021-01-04
I am aware of the need for two terms. In the physical world, a trunk is a path from the root to an end point, usually taken to mean the "thickest" such path. A branch is the same, except it starts at a node other than the root.
I have used root and node for a very long time, and seen it used by others in very many places. I don't think I've seen trunk and branch used with that particular meaning at all.
PYK 2020-01-05
I tried just now to replace "trunk" with "root", but it didn't work out. The problem may be the term, "node". There's no need for it. It's branches all the way down. I've removed the word "node" where possible in this page. If everything is branches, "root" isn't the right term because a root isn't a branch. A "trunk", on the other hand, is a branch, so it still seems like the better term.

See Also

Data Format
Includes a list of formats for tree-like data.
Decision Trees
deep dict
A tree can be represented as a deep dictionary: Each key is the name of a branch and each value is either a dictionary of further branches or a list containing a single value which is the value corresponding to that key.
What's wrong with the tree widgets?
Best Tree Widget , comp.lang.tcl, 2009-03-11
A discussion between Martyn, Ruediger, and Alexander.

Types of Trees

RBTree
Red-black tree data type.

Implementations

Tcllib struct tree
Containers, by Iain B. Findleton
ODIE
Includes tools for data tree maintenance.
tdom
An implementation of the DOM.
Tree Objects
Discussed by Clif Flynt.
Various useful Tcl packages (Rempel)
Includes some tree operation packages.
A Tree class using TclOO, by Tom Krehbiel
An experimental tree structure, by Marco Maggi
Simple tree structure, by rui
ycl list deep, by PYK
An implementation of a deep list.

Widgets

BWidget::Tree
A tree widget. More accessible for beginners. Featurs edit capabilities.
TkTreeCtrl
A multicolumn, hierarchical listbox widget. Complex for beginners.
Hipp miscellaneous widgets
Includes some tree widgets.
mtree widget
BLT
Tix
ClassyTk
incr widgets
Includes a hierarchy widget.
mkWidgets
PRS Open Source Software
Zinc
TreeWidget
A pure-Python tree widget for Tkinter.
Tk Tree Widget in C++
tkgcv
hierarchy
Tree Table
born2net's Iwidgets version of Hipp's tree widget
Tree Widget, by Brighton
An Iwidgets tree widget.
Tree widget, by Mutlu: An Iwidgets version tree widget
Pryce's itk widget base class
tktree
GRIDPLUS
Includes a basic scrollable tree widget.
A Minimal Tree Widget
gnocl::tree

Browsers

A little RSS browser
A little XML browser, by RS
Tree nodes in motion
Move branches on a Bwidget tree.
LemonTree
Trees as nested lists
An exploration of both structural approaches for trees, along with some simple graphical interfaces.
Displaying Tree Hierarchy with Incremental Node Numbering

Techniques

Simple tree layout, by Richard Suchenwirth
How to display a tree structure on a canvas.

Visualizations

Pythagoras Tree

description

AMG: A tree is sometimes called a DAG because it is a directed acyclic graph. I find this to be a useful mnemonic.

NEM: Well, all trees are DAGs, but not all DAGs are trees.

AMG: Yes, quite right; see the other tree properties listed in the first line of this page.


LV In the following text, I notice a number of cases where GUI widget sets have some sort of tree widget. In each of these cases, is the data structure intermingled with the data representation? Seems a shame that someone doesn't just build a graphically viewable widget that depends on a data structure that is separate. That way, someone could do work with one piece of code, and then, in other pieces, display that data. Seems like a natural method of developing and maintaining code....

The Value of a Tree

PYK 2021-01-03:

In Tcl, data structures such as lists and dictionaries are values. In order to form a value that represents a tree, a value that represents a branch is needed. A branch typically has three components: A value, attributes, and branches. The purpose of an attribute is to provide additional information about the branch itself rather than the value it contains or the thing it refers to in a model. In other words, attributes describe the branch itself rather than the thing the value of the branch describes. A good format for a branch might be a list where the first item is the value of the branch, additional items are keys and values representing attributes of the branch, and any remaining final item is a list of further branches. In other words:

value ?{key 1} {attribute 1}? ... ?branches?

The advantages of this format are that it is as standard Tcl list, and that both attributes and branches can be independently omitted or provided in a concise way.

A small example of a tree:

atoms {
    {
        hydrogen {
            {symbol H}
            {{atomic weight} 1.008}
        }
    }

    {
        helium {
            {symbol He}
            {{atomic weight} 4.002}
        }
    }
}

For processing efficency and also for verification, it may be useful to provide a count of the items in a list representing a branch or list of branches. Such a count would quickly indicate the number of attributes, and also whether there are any branches. This could be provided using a notation similar to that of Tcl's {*} operator: Lists are preceded by a number enclosed in braces:

{4}{value {key 1} {attribute 1} {2}{
    {
        {branch 1}
    }
    {
        {branch 2}
    }
}

This is not a valid Tcl list, but as an extension it makes about as much sense as extending Tcl with the {*} did, and perhaps more, since it isn't as disruptive to the larger system.

The same notation could make the representation more robust by providing the number of characters used to represent each value:

{4}{{5}value {5}{key 1} {12}"attribute\ 1" {2}{
    {
        {8}{branch 1}
    }
    {
        {8}{branch 2}
    }
}

With these additions, this format becomes reminiscent of netstrings, but has some built-in structure, and is also more Tcl-ish.