 |
ActiveTcl User Guide
|
 |
|
[ Main table Of Contents | Tcllib Table Of Contents | Tcllib Index ]
tree(n) 1.2.1 "Tcl Data Structures"
tree - Create and manipulate tree objects
package require Tcl 8.2
package require struct ?1.3?
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 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 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 nodex, 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.
tree
Copyright © 2002 Andreas Kupries
<andreas_kupries@users.sourceforge.net>