|
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
arg
s 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:
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
node
x
, 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:
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.
treeName
append
node
?-key
key
?
value
|
