NAME
::struct::tree - Create and manipulate tree objects
SYNOPSIS
package require struct ?1.0?
::struct::tree treeName
_________________________________________________________________
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 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 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 pre
vent 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.
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 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.
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.
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 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.
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.
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 gen
erated name is of the form nodex, where x is a num
ber. 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.
ited 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 chil
dren, followed by all of the root's grandchildren.
Post-order walking means that a parent node is vis
ited 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 rec
ognized:
%% 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.
KEYWORDS
tree
Man(1) output converted with
man2html