A tree is an acyclic directed-graph data structure where the one node is the trunk, and every other node is a branch. Trees can be used, e.g., for representing the result in syntax parsing. An XML document is structured as a tree.
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....
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 node is needed. A node typically has three components: A value, attributes, and branches. The purpose of an attribute is to provide additional information about the node itself rather than the value it contains or the thing it refers to in a model. In other words, attributes describe the node itself rather than the thing the value of the node describes. A good format for a node might a list where the first item is the value of the node, additional items are keys and values representing attributes of the node, and any remaining final item is a list of branches, where each branch is itself a node. In other words:
The advantages of this format are that it is as standard Tcl list, and that both attributes and branches can be be indepenently ommitted 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 node or 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.