1struct::tree v1(n) Tcl Data Structures struct::tree v1(n)
2______________________________________________________________________________
6
8 struct::tree v1 - Create and manipulate tree objects
9
11 package require Tcl 8.2
12 package require struct::tree ?1.2.2?
14 treeName option ?arg arg ...?
16 treeName append node ?-key key? value
18 treeName children node
20 treeName cut node
22 treeName delete node ?node ...?
24 treeName depth node
26 treeName destroy
28 treeName exists node
30 treeName get node ?-key key?
32 treeName getall node
34 treeName keys node
36 treeName keyexists node ?-key key?
38 treeName index node
40 treeName insert parent index ?child ?child ...??
42 treeName isleaf node
44 treeName lappend node ?-key key? value
46 treeName move parent index node ?node ...?
48 treeName next node
50 treeName numchildren node
52 treeName parent node
54 treeName previous node
56 treeName set node ?-key key? ?value?
58 treeName size ?node?
60 treeName splice parent from ?to? ?child?
62 treeName swap node1 node2
64 treeName unset node ?-key key?
66 treeName walk node ?-order order? ?-type type? -command cmd
68_________________________________________________________________
70
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 treeName option ?arg arg ...?
78 Option and the args determine the exact behavior of the command.
79 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 The element names can be arbitrary strings.
88 A tree is thus similar to an array, but with three important differ‐
90 ences:
91 [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 [2] Trees have a hierarchical structure, whereas an array is just an
97 unordered collection.
98 [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 The following commands are possible for tree objects:
103 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 treeName children node
109 Return a list of the children of node.
110 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 treeName delete node ?node ...?
117 Remove the specified nodes from the tree. All of the nodes'
118 children will be removed as well to prevent orphaned nodes.
119 treeName depth node
121 Return the number of steps from node node to the root node.
122 treeName destroy
124 Destroy the tree, including its storage space and associated
125 command.
126 treeName exists node
128 Remove true if the specified node exists in the tree.
129 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 treeName getall node
135 Returns a serialized list of key/value pairs (suitable for use
136 with [array set]) for the node.
137 treeName keys node
139 Returns a list of keys for the node.
140 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 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 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 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 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 The return result from this command is a list of nodes added.
168 treeName isleaf node
170 Returns true if node is a leaf of the tree (if node has no chil‐
171 dren), false otherwise.
172 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 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 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 treeName numchildren node
192 Return the number of immediate children of node.
193 treeName parent node
195 Return the parent of node.
196 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 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 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 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 treeName swap node1 node2
227 Swap the position of node1 and node2 in the tree.
228 treeName unset node ?-key key?
230 Remove a keyed value from the node node. If no key is speci‐
231 fied, the key data is assumed.
232 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 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 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 %% Insert the literal % character.
262 %t Name of the tree object.
264 %n Name of the current node.
266 %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
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 SF Trackers [http://source‐
279 forge.net/tracker/?group_id=12883]. Please also report any ideas for
280 enhancements you may have for either package and/or documentation.
281
283 tree
284
286 Copyright (c) 2002 Andreas Kupries <andreas_kupries@users.sourceforge.net>
287struct 1.2.2 struct::tree v1(n)