NAME¶
struct::tree1 - Create and manipulate tree objects (version 1)
SYNOPSIS¶
package require
Tcl 8.2
package require
struct::tree ?1.2.2?
treeName option ?
arg arg ...?
treeName append node ?-key
key?
value
treeName children node
treeName cut node
treeName delete node ?
node ...?
treeName depth node
treeName destroy
treeName exists node
treeName get node ?
-key key?
treeName getall node
treeName keys node
treeName keyexists node ?-key
key?
treeName index node
treeName insert parent index ?
child
?
child ...??
treeName isleaf node
treeName lappend node ?-key
key?
value
treeName move parent index node ?
node
...?
treeName next node
treeName numchildren node
treeName parent node
treeName previous node
treeName set node ?
-key key? ?
value?
treeName size ?
node?
treeName splice parent from ?
to?
?
child?
treeName swap node1 node2
treeName unset node ?
-key key?
treeName walk node ?
-order order?
?
-type type?
-command cmd
DESCRIPTION¶
The
::struct::tree command creates a new tree object with an associated
global Tcl command whose name is
treeName. This command may be used to
invoke various operations on the tree. It has the following general form:
- treeName option ?arg arg ...?
- Option and the args determine the exact
behavior of the command.
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). In addition to maintaining
the node relationships, this tree implementation allows any number of keyed
values to be associated with each node.
The element names can be arbitrary strings.
A tree is thus similar to an array, but with three important differences:
- [1]
- Trees are accessed through an object command, whereas
arrays are accessed as variables. (This means trees cannot be local to a
procedure.)
- [2]
- Trees have a hierarchical structure, whereas an array is
just an unordered collection.
- [3]
- Each node of a tree has a separate collection of attributes
and values. This is like an array where every value is a dictionary.
The following commands are possible for tree objects:
- treeName append node ?-key key?
value
- Appends a value to one of the keyed values
associated with an node. If no key is specified, the key
data is assumed.
- treeName children node
- Return a list of the children of node.
- treeName cut node
- Removes the node specified by node from the tree,
but not its children. The children of node are made children of the
parent of the node, at the index at which node was
located.
- treeName delete node ?node
...?
- Remove the specified nodes from the tree. All of the nodes'
children will be removed as well to prevent orphaned nodes.
- treeName depth node
- Return the number of steps from node node to the
root node.
- treeName destroy
- Destroy the tree, including its storage space and
associated command.
- treeName exists node
- Remove true if the specified node exists in the tree.
- treeName get node ?-key
key?
- Return the value associated with the key key for the
node node. If no key is specified, the key data is
assumed.
- treeName getall node
- Returns a serialized list of key/value pairs (suitable for
use with [ array set]) for the node.
- treeName keys node
- Returns a list of keys for the node.
- treeName keyexists node ?-key
key?
- Return true if the specified key exists for the
node. If no key is specified, the key data is
assumed.
- treeName index node
- Returns the index of node in its parent's list of
children. For example, if a node has nodeFoo, nodeBar, and
nodeBaz as children, in that order, the index of nodeBar is
1.
- treeName insert parent index
?child ?child ...??
- Insert one or more nodes into the tree as children of the
node parent. The nodes will be added in the order they are given.
If parent is root, it refers to the root of the tree. The
new nodes will be added to the parent node's child list at the
index given by index. The index can be end in which
case the new nodes will be added after the current last child.
If any of the specified children already exist in treeName, those
nodes will be moved from their original location to the new location
indicated by this command.
If no child is specified, a single node will be added, and a name
will be generated for the new node. The generated name is of the form
node x, where x is a number. If names are specified
they must neither contain whitespace nor colons (":").
The return result from this command is a list of nodes added.
- treeName isleaf node
- Returns true if node is a leaf of the tree (if
node has no children), false otherwise.
- treeName lappend node ?-key
key? value
- Appends a value (as a list) to one of the keyed
values associated with an node. If no key is specified, the
key data is assumed.
- treeName move parent index
node ? node ...?
- Make the specified nodes children of parent,
inserting them into the parent's child list at the index given by
index. Note that the command will take all nodes out of the tree
before inserting them under the new parent, and that it determines the
position to place them into after the removal, before the re-insertion.
This behaviour is important when it comes to moving one or more nodes to a
different index without changing their parent node.
- treeName next node
- Return the right sibling of node, or the empty
string if node was the last child of its parent.
- treeName numchildren node
- Return the number of immediate children of
node.
- treeName parent node
- Return the parent of node.
- treeName previous node
- Return the left sibling of node, or the empty string
if node was the first child of its parent.
- treeName set node ?-key
key? ? value?
- Set or get one of the keyed values associated with a node.
If no key is specified, the key data is assumed. Each node that is
added to a tree has the value "" assigned to the key data
automatically. A node may have any number of keyed values associated with
it. If value is not specified, this command returns the current
value assigned to the key; if value is specified, this command
assigns that value to the key.
- treeName size ?node?
- Return a count of the number of descendants of the node
node; if no node is specified, root is assumed.
- treeName splice parent from
?to? ?child?
- Insert a node named child into the tree as a child
of the node parent. If parent is root, it refers to
the root of the tree. The new node will be added to the parent node's
child list at the index given by from. The children of
parent which are in the range of the indices from and
to are made children of child. If the value of to is
not specified it defaults to end. If no name is given for
child, a name will be generated for the new node. The generated
name is of the form nodex, where x is a number. The
return result from this command is the name of the new node.
- treeName swap node1 node2
- Swap the position of node1 and node2 in the
tree.
- treeName unset node ?-key
key?
- Remove a keyed value from the node node. If no key
is specified, the key data is assumed.
- treeName walk node ?-order
order? ? -type type? -command cmd
- Perform a breadth-first or depth-first walk of the tree
starting at the node node. The type of walk, breadth-first or
depth-first, is determined by the value of type; bfs
indicates breadth-first, dfs indicates depth-first. Depth-first is
the default. The order of the walk, pre-, post-, both- or in-order is
determined by the value of order; pre indicates pre-order,
post indicates post-order, both indicates both-order and
in indicates in-order. Pre-order is the default.
Pre-order walking means that a parent node is visited before any of its
children. For example, a breadth-first search starting from the root will
visit the root, followed by all of the root's children, followed by all of
the root's grandchildren. Post-order walking means that a parent node is
visited after any of its children. Both-order walking means that a parent
node is visited before and after any of its children. In-order
walking means that a parent node is visited after its first child and
before the second. This is a generalization of in-order walking for binary
trees and will do the right thing if a binary is walked. The combination
of a breadth-first walk with in-order is illegal.
As the walk progresses, the command cmd will be evaluated at each
node. Percent substitution will be performed on cmd before
evaluation, just as in a bind script. The following substitutions
are recognized:
- %%
- Insert the literal % character.
- %t
- Name of the tree object.
- %n
- Name of the current node.
- %a
- Name of the action occurring; one of enter,
leave, or visit. enter actions occur during pre-order
walks; leave actions occur during post-order walks; visit
actions occur during in-order walks. In a both-order walk, the command
will be evaluated twice for each node; the action is enter for the
first evaluation, and leave for the second.
BUGS, IDEAS, FEEDBACK¶
This document, and the package it describes, will undoubtedly contain bugs and
other problems. Please report such in the category
struct :: tree of
the
Tcllib SF Trackers
[
http://sourceforge.net/tracker/?group_id=12883]. Please also report any ideas
for enhancements you may have for either package and/or documentation.
KEYWORDS¶
tree
CATEGORY¶
Data structures
COPYRIGHT¶
Copyright (c) 2002 Andreas Kupries <andreas_kupries@users.sourceforge.net>