1struct::tree_v1(n)            Tcl Data Structures           struct::tree_v1(n)
2
3
4
5______________________________________________________________________________
6

NAME

8       struct::tree_v1 - Create and manipulate tree objects
9

SYNOPSIS

11       package require Tcl  8.2
12
13       package require struct::tree  ?1.2.2?
14
15       treeName option ?arg arg ...?
16
17       treeName append node ?-key key? value
18
19       treeName children node
20
21       treeName cut node
22
23       treeName delete node ?node ...?
24
25       treeName depth node
26
27       treeName destroy
28
29       treeName exists node
30
31       treeName get node ?-key key?
32
33       treeName getall node
34
35       treeName keys node
36
37       treeName keyexists node ?-key key?
38
39       treeName index node
40
41       treeName insert parent index ?child ?child ...??
42
43       treeName isleaf node
44
45       treeName lappend node ?-key key? value
46
47       treeName move parent index node ?node ...?
48
49       treeName next node
50
51       treeName numchildren node
52
53       treeName parent node
54
55       treeName previous node
56
57       treeName set node ?-key key? ?value?
58
59       treeName size ?node?
60
61       treeName splice parent from ?to? ?child?
62
63       treeName swap node1 node2
64
65       treeName unset node ?-key key?
66
67       treeName walk node ?-order order? ?-type type? -command cmd
68
69______________________________________________________________________________
70

DESCRIPTION

72       The ::struct::tree command creates a new tree object with an associated
73       global Tcl command whose name is treeName. This command may be used  to
74       invoke  various  operations  on  the tree. It has the following general
75       form:
76
77       treeName option ?arg arg ...?
78              Option and the args determine the exact behavior of the command.
79
80       A tree is a collection of named elements, called nodes, one of which is
81       distinguished  as  a  root,  along  with a relation ("parenthood") that
82       places a hierarchical structure on  the  nodes.  (Data  Structures  and
83       Algorithms;  Aho, Hopcroft and Ullman; Addison-Wesley, 1987).  In addi‐
84       tion to maintaining the node relationships,  this  tree  implementation
85       allows any number of keyed values to be associated with each node.
86
87       The element names can be arbitrary strings.
88
89       A  tree  is  thus similar to an array, but with three important differ‐
90       ences:
91
92       [1]    Trees are accessed through an object command, whereas arrays are
93              accessed  as  variables.  (This means trees cannot be local to a
94              procedure.)
95
96       [2]    Trees have a hierarchical structure, whereas an array is just an
97              unordered collection.
98
99       [3]    Each  node of a tree has a separate collection of attributes and
100              values. This is like an array where every value is a dictionary.
101
102       The following commands are possible for tree objects:
103
104       treeName append node ?-key key? value
105              Appends a value to one of the keyed values  associated  with  an
106              node. If no key is specified, the key data is assumed.
107
108       treeName children node
109              Return a list of the children of node.
110
111       treeName cut node
112              Removes  the  node  specified by node from the tree, but not its
113              children.  The children of node are made children of the  parent
114              of the node, at the index at which node was located.
115
116       treeName delete node ?node ...?
117              Removes  the  specified  nodes from the tree.  All of the nodes'
118              children will be removed as well to prevent orphaned nodes.
119
120       treeName depth node
121              Return the number of steps from node node to the root node.
122
123       treeName destroy
124              Destroy the tree, including its  storage  space  and  associated
125              command.
126
127       treeName exists node
128              Returns true if the specified node exists in the tree.
129
130       treeName get node ?-key key?
131              Return  the value associated with the key key for the node node.
132              If no key is specified, the key data is assumed.
133
134       treeName getall node
135              Returns a serialized list of key/value pairs (suitable  for  use
136              with [array set]) for the node.
137
138       treeName keys node
139              Returns a list of keys for the node.
140
141       treeName keyexists node ?-key key?
142              Return  true if the specified key exists for the node. If no key
143              is specified, the key data is assumed.
144
145       treeName index node
146              Returns the index of node in its parent's list of children.  For
147              example,  if  a  node has nodeFoo, nodeBar, and nodeBaz as chil‐
148              dren, in that order, the index of nodeBar is 1.
149
150       treeName insert parent index ?child ?child ...??
151              Insert one or more nodes into the tree as children of  the  node
152              parent.  The nodes will be added in the order they are given. If
153              parent is root, it refers to the root of the tree. The new nodes
154              will be added to the parent node's child list at the index given
155              by index. The index can be end in which case the new nodes  will
156              be added after the current last child.
157
158              If  any  of  the  specified  children already exist in treeName,
159              those nodes will be moved from their original  location  to  the
160              new location indicated by this command.
161
162              If  no  child  is  specified, a single node will be added, and a
163              name will be generated for the new node. The generated  name  is
164              of  the  form nodex, where x is a number. If names are specified
165              they must neither contain whitespace nor colons (":").
166
167              The return result from this command is a list of nodes added.
168
169       treeName isleaf node
170              Returns true if node is a leaf of the tree (if node has no chil‐
171              dren), false otherwise.
172
173       treeName lappend node ?-key key? value
174              Appends  a  value (as a list) to one of the keyed values associ‐
175              ated with an node. If no key  is  specified,  the  key  data  is
176              assumed.
177
178       treeName move parent index node ?node ...?
179              Make the specified nodes children of parent, inserting them into
180              the parent's child list at the index given by index.  Note  that
181              the command will take all nodes out of the tree before inserting
182              them under the new parent, and that it determines  the  position
183              to  place  them into after the removal, before the re-insertion.
184              This behaviour is important when it comes to moving one or  more
185              nodes to a different index without changing their parent node.
186
187       treeName next node
188              Return  the  right  sibling of node, or the empty string if node
189              was the last child of its parent.
190
191       treeName numchildren node
192              Return the number of immediate children of node.
193
194       treeName parent node
195              Return the parent of node.
196
197       treeName previous node
198              Return the left sibling of node, or the empty string if node was
199              the first child of its parent.
200
201       treeName set node ?-key key? ?value?
202              Set or get one of the keyed values associated with a node. If no
203              key is specified, the key data is assumed.  Each  node  that  is
204              added  to a tree has the value "" assigned to the key data auto‐
205              matically.  A node may have any number of keyed  values  associ‐
206              ated  with  it.  If value is not specified, this command returns
207              the current value assigned to the key; if  value  is  specified,
208              this command assigns that value to the key.
209
210       treeName size ?node?
211              Return a count of the number of descendants of the node node; if
212              no node is specified, root is assumed.
213
214       treeName splice parent from ?to? ?child?
215              Insert a node named child into the tree as a child of  the  node
216              parent.  If  parent  is root, it refers to the root of the tree.
217              The new node will be added to the parent node's  child  list  at
218              the  index  given  by from.  The children of parent which are in
219              the range of the indices from and to are made children of child.
220              If  the  value of to is not specified it defaults to end.  If no
221              name is given for child, a name will be generated  for  the  new
222              node.   The  generated  name  is of the form nodex, where x is a
223              number.  The return result from this command is the name of  the
224              new node.
225
226       treeName swap node1 node2
227              Swap the position of node1 and node2 in the tree.
228
229       treeName unset node ?-key key?
230              Removes  a  keyed value from the node node.  If no key is speci‐
231              fied, the key data is assumed.
232
233       treeName walk node ?-order order? ?-type type? -command cmd
234              Perform a breadth-first or depth-first walk of the tree starting
235              at  the  node  node.   The type of walk, breadth-first or depth-
236              first, is  determined  by  the  value  of  type;  bfs  indicates
237              breadth-first,  dfs  indicates  depth-first.  Depth-first is the
238              default. The order of the walk, pre-, post-, both-  or  in-order
239              is  determined  by  the value of order; pre indicates pre-order,
240              post indicates post-order,  both  indicates  both-order  and  in
241              indicates in-order. Pre-order is the default.
242
243              Pre-order walking means that a parent node is visited before any
244              of its children.  For example, a breadth-first  search  starting
245              from the root will visit the root, followed by all of the root's
246              children, followed by all of  the  root's  grandchildren.  Post-
247              order  walking  means that a parent node is visited after any of
248              its children. Both-order walking means that  a  parent  node  is
249              visited  before  and after any of its children. In-order walking
250              means that a parent node is visited after its  first  child  and
251              before  the second. This is a generalization of in-order walking
252              for binary trees and will do the right  thing  if  a  binary  is
253              walked. The combination of a breadth-first walk with in-order is
254              illegal.
255
256              As the walk progresses, the command cmd  will  be  evaluated  at
257              each node.  Percent substitution will be performed on cmd before
258              evaluation, just as in a bind script.  The  following  substitu‐
259              tions are recognized:
260
261              %%     Insert the literal % character.
262
263              %t     Name of the tree object.
264
265              %n     Name of the current node.
266
267              %a     Name  of  the  action  occurring; one of enter, leave, or
268                     visit.  enter actions occur during pre-order walks; leave
269                     actions  occur  during  post-order  walks;  visit actions
270                     occur during in-order walks.  In a both-order  walk,  the
271                     command will be evaluated twice for each node; the action
272                     is enter for the first evaluation, and leave for the sec‐
273                     ond.
274

BUGS, IDEAS, FEEDBACK

276       This  document,  and the package it describes, will undoubtedly contain
277       bugs and other problems.  Please report such in the category struct  ::
278       tree  of  the  Tcllib  Trackers [http://core.tcl.tk/tcllib/reportlist].
279       Please also report any ideas for enhancements you may have  for  either
280       package and/or documentation.
281
282       When proposing code changes, please provide unified diffs, i.e the out‐
283       put of diff -u.
284
285       Note further that  attachments  are  strongly  preferred  over  inlined
286       patches.  Attachments  can  be  made  by  going to the Edit form of the
287       ticket immediately after its creation, and  then  using  the  left-most
288       button in the secondary navigation bar.
289

KEYWORDS

291       tree
292

CATEGORY

294       Data structures
295
297       Copyright (c) 2002 Andreas Kupries <andreas_kupries@users.sourceforge.net>
298
299
300
301
302tcllib                               1.2.2                  struct::tree_v1(n)
Impressum