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 elements, called nodes, one of which is dis‐
81 tinguished as a root, along with a relation ("parenthood") that places
82 a hierarchical structure on the nodes. (Data Structures and Algorithms;
83 Aho, Hopcroft and Ullman; Addison-Wesley, 1987). In addition to main‐
84 taining the node relationships, this tree implementation allows any
85 number of keyed values to be associated with each node.
86 The following commands are possible for tree objects:
88 treeName append node ?-key key? value
90 Appends a value to one of the keyed values associated with an
91 node. If no key is specified, the key data is assumed.
92 treeName children node
94 Return a list of the children of node.
95 treeName cut node
97 Removes the node specified by node from the tree, but not its
98 children. The children of node are made children of the parent
99 of the node, at the index at which node was located.
100 treeName delete node ?node ...?
102 Remove the specified nodes from the tree. All of the nodes'
103 children will be removed as well to prevent orphaned nodes.
104 treeName depth node
106 Return the number of steps from node node to the root node.
107 treeName destroy
109 Destroy the tree, including its storage space and associated
110 command.
111 treeName exists node
113 Remove true if the specified node exists in the tree.
114 treeName get node ?-key key?
116 Return the value associated with the key key for the node node.
117 If no key is specified, the key data is assumed.
118 treeName getall node
120 Returns a serialized list of key/value pairs (suitable for use
121 with [array set]) for the node.
122 treeName keys node
124 Returns a list of keys for the node.
125 treeName keyexists node ?-key key?
127 Return true if the specified key exists for the node. If no key
128 is specified, the key data is assumed.
129 treeName index node
131 Returns the index of node in its parent's list of children. For
132 example, if a node has nodeFoo, nodeBar, and nodeBaz as chil‐
133 dren, in that order, the index of nodeBar is 1.
134 treeName insert parent index ?child ?child ...??
136 Insert one or more nodes into the tree as children of the node
137 parent. The nodes will be added in the order they are given. If
138 parent is root, it refers to the root of the tree. The new nodes
139 will be added to the parent node's child list at the index given
140 by index. The index can be end in which case the new nodes will
141 be added after the current last child.
142 If any of the specified children already exist in treeName,
144 those nodes will be moved from their original location to the
145 new location indicated by this command.
146 If no child is specified, a single node will be added, and a
148 name will be generated for the new node. The generated name is
149 of the form nodex, where x is a number. If names are specified
150 they must neither contain whitespace nor colons (":").
151 The return result from this command is a list of nodes added.
153 treeName isleaf node
155 Returns true if node is a leaf of the tree (if node has no chil‐
156 dren), false otherwise.
157 treeName lappend node ?-key key? value
159 Appends a value (as a list) to one of the keyed values associ‐
160 ated with an node. If no key is specified, the key data is
161 assumed.
162 treeName move parent index node ?node ...?
164 Make the specified nodes children of parent, inserting them into
165 the parent's child list at the index given by index. Note that
166 the command will take all nodes out of the tree before inserting
167 them under the new parent, and that it determines the position
168 to place them into after the removal, before the re-insertion.
169 This behaviour is important when it comes to moving one or more
170 nodes to a different index without changing their parent node.
171 treeName next node
173 Return the right sibling of node, or the empty string if node
174 was the last child of its parent.
175 treeName numchildren node
177 Return the number of immediate children of node.
178 treeName parent node
180 Return the parent of node.
181 treeName previous node
183 Return the left sibling of node, or the empty string if node was
184 the first child of its parent.
185 treeName set node ?-key key? ?value?
187 Set or get one of the keyed values associated with a node. If no
188 key is specified, the key data is assumed. Each node that is
189 added to a tree has the value "" assigned to the key data auto‐
190 matically. A node may have any number of keyed values associ‐
191 ated with it. If value is not specified, this command returns
192 the current value assigned to the key; if value is specified,
193 this command assigns that value to the key.
194 treeName size ?node?
196 Return a count of the number of descendants of the node node; if
197 no node is specified, root is assumed.
198 treeName splice parent from ?to? ?child?
200 Insert a node named child into the tree as a child of the node
201 parent. If parent is root, it refers to the root of the tree.
202 The new node will be added to the parent node's child list at
203 the index given by from. The children of parent which are in
204 the range of the indices from and to are made children of child.
205 If the value of to is not specified it defaults to end. If no
206 name is given for child, a name will be generated for the new
207 node. The generated name is of the form nodex, where x is a
208 number. The return result from this command is the name of the
209 new node.
210 treeName swap node1 node2
212 Swap the position of node1 and node2 in the tree.
213 treeName unset node ?-key key?
215 Remove a keyed value from the node node. If no key is speci‐
216 fied, the key data is assumed.
217 treeName walk node ?-order order? ?-type type? -command cmd
219 Perform a breadth-first or depth-first walk of the tree starting
220 at the node node. The type of walk, breadth-first or depth-
221 first, is determined by the value of type; bfs indicates
222 breadth-first, dfs indicates depth-first. Depth-first is the
223 default. The order of the walk, pre-, post-, both- or in-order
224 is determined by the value of order; pre indicates pre-order,
225 post indicates post-order, both indicates both-order and in
226 indicates in-order. Pre-order is the default.
227 Pre-order walking means that a parent node is visited before any
229 of its children. For example, a breadth-first search starting
230 from the root will visit the root, followed by all of the root's
231 children, followed by all of the root's grandchildren. Post-
232 order walking means that a parent node is visited after any of
233 its children. Both-order walking means that a parent node is
234 visited before and after any of its children. In-order walking
235 means that a parent node is visited after its first child and
236 before the second. This is a generalization of in-order walking
237 for binary trees and will do the right thing if a binary is
238 walked. The combination of a breadth-first walk with in-order is
239 illegal.
240 As the walk progresses, the command cmd will be evaluated at
242 each node. Percent substitution will be performed on cmd before
243 evaluation, just as in a bind script. The following substitu‐
244 tions are recognized:
245 %% Insert the literal % character.
247 %t Name of the tree object.
249 %n Name of the current node.
251 %a Name of the action occurring; one of enter, leave, or
253 visit. enter actions occur during pre-order walks; leave
254 actions occur during post-order walks; visit actions
255 occur during in-order walks. In a both-order walk, the
256 command will be evaluated twice for each node; the action
257 is enter for the first evaluation, and leave for the sec‐
258 ond.
259
261 tree
262
264 Copyright (c) 2002 Andreas Kupries <andreas_kupries@users.sourceforge.net>
265struct 1.2.2 struct::tree v1(n)