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