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. 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? ** 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 dict%|%deep dictionary]: Each key is the name of a node and each value is either a dictionary of contained nodes or a list containing a single value which is itself a list of leaf nodes. [What's wrong with the tree widgets?]: [https://groups.google.com/forum/#!topic/comp.lang.tcl/7A1BjFVsgJE%|%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 implementatio 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 Lopes%|%rui]: [ycl%|%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]: [http://oomadness.tuxfamily.org/p-treewidget.php%|%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 nodes on a [Bwidget::Tree%|%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 structure%|%data structures] such as [list%|%lists] and [dict%|%dictionaries] are [value%|%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: : ''`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 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. <> Arts and Crafts of Tcl-Tk Programming | Command | tcllib | struct | Data Structure