Scroll to navigation

struct::tree_v1(3tcl) Tcl Data Structures struct::tree_v1(3tcl) 





NAME


struct::tree_v1 - Create and manipulate tree objects






SYNOPSIS


package require Tcl 8.5 9


package require struct::tree ?1.2.3?


treeName option ?arg arg ...?


treeName append node ?-key key?
    value


treeName children node


treeName cut node


treeName delete node ?node ...?


treeName depth node


treeName destroy


treeName exists node


treeName get node ?-key
  key?


treeName getall node


treeName keys node


treeName keyexists node ?-key key?


treeName index node


treeName insert parent index
    ?child ?child ...??


treeName isleaf node


treeName lappend node ?-key key?
    value


treeName move parent index node
    ?node ...?


treeName next node


treeName numchildren node


treeName parent node


treeName previous node


treeName set node ?-key key?
    ?value?


treeName size ?node?


treeName splice parent from
    ?to? ?child?


treeName swap node1 node2


treeName unset node ?-key
  key?


treeName walk node ?-order
    order? ?-type type? -command cmd










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:



  

  
Option and the args determine the exact behavior of the
      command.




A tree is a collection of named 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 element names can be arbitrary strings.


A tree is thus similar to an array, but with three important
    differences:



  
[1]

  
Trees are accessed through an object command, whereas arrays are accessed
      as variables. (This means trees cannot be local to a procedure.)

  
[2]

  
Trees have a hierarchical structure, whereas an array is just an unordered
      collection.

  
[3]

  
Each node of a tree has a separate collection of attributes and values.
      This is like an array where every value is a dictionary.




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.

  

  
Return a list of the children of 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.

  

  
Removes the specified nodes from the tree. All of the nodes' children will
      be removed as well to prevent orphaned nodes.

  

  
Return the number of steps from node node to the root node.

  

  
Destroy the tree, including its storage space and associated command.

  

  
Returns true if the specified node exists in the tree.

  

  
Return the value associated with the key key for the node
      node. If no key is specified, the key data is assumed.

  

  
Returns a serialized list of key/value pairs (suitable for use with
      [array set]) for the node.

  

  
Returns a list of keys for the node.

  

  
Return true if the specified key exists for the node. If no
      key is specified, the key data is assumed.

  

  
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.

  

  
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 nodex, 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.

  

  

  
Returns true if node is a leaf of the tree (if node has no
      children), false otherwise.

  

  
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.

  

  
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.

  

  
Return the right sibling of node, or the empty string if
      node was the last child of its parent.

  

  
Return the number of immediate children of 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.

  

  
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.

  

  
Return a count of the number of descendants of the node node; if no
      node is specified, root is assumed.

  

  
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 nodex,
      where x is a number. The return result from this command is the
      name of the new node.

  

  
Swap the position of node1 and node2 in the tree.

  

  
Removes a keyed value from the node node. If no key is specified,
      the key data is assumed.

  

  
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:

  







  
%%

  
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.










BUGS, IDEAS, FEEDBACK


This document, and the package it describes, will undoubtedly
    contain bugs and other problems. Please report such in the category
    struct :: tree of the Tcllib Trackers
    [http://core.tcl.tk/tcllib/reportlist]. Please also report any ideas for
    enhancements you may have for either package and/or documentation.


When proposing code changes, please provide unified diffs,
    i.e the output of diff -u.


Note further that attachments are strongly preferred over
    inlined patches. Attachments can be made by going to the Edit form of
    the ticket immediately after its creation, and then using the left-most
    button in the secondary navigation bar.






KEYWORDS


tree






CATEGORY


Data structures






COPYRIGHT


Copyright (c) 2002 Andreas Kupries <andreas_kupries@users.sourceforge.net>








  

    1.2.3
    tcllib