Tree

A branch doesn't know it is a branch. It thinks it is God.

A tree is an directed acyclic graph (DAG) 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.

HE 2022-04-18: Possibly I missed something but as far as I know a tree is defined a bit different. Why not using the definition of Wikipedia (https://en.wikipedia.org/wiki/Tree_(data_structure) )? Or from another source: https://afteracademy.com/blog/what-is-a-tree-data-structure .

: I would define a tree (as a summary what I read in internet) as:

A tree exists out of nodes. Nodes are the elements which contains the data.
A tree can't be empty. It contains at least out of one node.
Nodes are connected by edges. Edges are often called connections or branches. The edges between root and its children is sometimes named trunk. Edges define the relation between nodes.
parent and children are relations of nodes.
Every node has exactly one parent beside the root node which has no parent.
Every node has one or more children beside leaves which have no children.
Ancestors are all nodes from one node point of view in direction of the root and including the root.
Descendant are all nodes from one node point of view in direction of the leaves and including the leaves.
No node can have an edge to an ancestor beside its parent.
No node can have an edge to a descendant beside its children.

: Another definition could be (summary from what I read in book "Algorithmen in C" by Robert Sedgewick; there is an english version of this book, too):

A tree is a not empty amount of nodes and edges.
A node is a simple object with a name and other associated data.
An edge is the connection between two nodes.
A path in a tree is a list of nodes in which the sequential nodes are connected by edges.
One node is defined as root node. Between root and every other node of the tree exists exactly one path.

EMJ 2022-05-02: For another definition, look at the documentation of the struct::tree module in Tcllib, which says:

A tree is a collection of named elements, called nodes, one of which is distinguished as a root, along with a relation ("parenthood") that places a hierarchical structure on the nodes.
(Data Structures and Algorithms; Aho, Hopcroft and Ullman; Addison-Wesley, 1987).
The book is a classic data structures text.

HE 2022-05-03: As far as I remember the book cited by EMJ and the documentation of struct tree package defines the tree formally as:

A single node by itself is a tree. This node is also the root of the tree.
Suppose n is a node and T1, T2, . . . , Tk are trees with roots n1, n2, . . . , nk, respectively. We can construct a new tree by making n be the parent of nodes n1, n2, . . . , nk. In this tree n is the root and T1, T2, . . . , Tk are the subtrees of the root. Nodes n1 , n2, . . . , nk are called the children of node n.

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.

Arts and Crafts of Tcl-Tk Programming

Category Command

Category tcllib

struct

Category Data Structure