Class | Tree::TreeNode |
In: |
lib/tree.rb
|
Parent: | Object |
This class models the nodes for an N-ary tree data structue. The nodes are named and have a place-holder for the node data (i.e., `content’ of the node). The node names are required to be unique within the tree.
The node content is not required to be unique across different nodes in the tree, and can be nil as well.
The class provides various traversal methods to navigate the tree, methods to modify contents of the node or to change position of the node in the tree and methods to change structure of the tree.
A node can have any number of child nodes attached to it and hence can be used to create N-ary trees. Access to the child nodes can be made in order (with the conventional left to right access), or randomly.
The node also provides direct access to its parent and other superior parents in the path to root of the tree. In addition, a node can also access its sibling nodes, if present. Note that while this implementation does not explicitly support directed graphs, the class itself makes no restrictions on associating a node’s CONTENT with multiple nodes in the tree.
The following example implements this tree structure: +------------+ | ROOT | +-----+------+ +-------------+------------+ | | +-------+-------+ +-------+-------+ | CHILD 1 | | CHILD 2 | +-------+-------+ +---------------+ | | +-------+-------+ | GRANDCHILD 1 | +---------------+
require ‘tree’
root_node = Tree::TreeNode.new(“ROOT”, “Root Content”)
root_node << Tree::TreeNode.new(“CHILD1”, “Child1 Content”) << Tree::TreeNode.new(“GRANDCHILD1”, “GrandChild1 Content”)
root_node << Tree::TreeNode.new(“CHILD2”, “Child2 Content”)
root_node.printTree
child1 = root_node[“CHILD1”]
grand_child1 = root_node[“CHILD1”][“GRANDCHILD1”]
siblings_of_child1 = child1.siblings
children_of_root = root_node.children
# Process all nodes
root_node.each { |node| node.content.reverse }
root_node.remove!(child1) # Remove the child
content | [RW] | Content of this node. Can be nil. |
name | [R] | Name of this node. Expected to be unique within the tree. |
parent | [R] | Parent of this node. Will be nil for root nodes. |
Constructor which expects the name of the node. Name of the node is expected to be unique across the tree.
The content can be of any type, defaults to nil.
Convenience synonym for TreeNode#add method.
This method allows an easy method to add node hierarchies to the tree on a given path via chaining the method calls to successive child nodes.
Example: root << child << grand_child
Returns the added child node.
Provides a comparision operation for the nodes.
Comparision is based on the natural character-set ordering of the *node name*.
Returns the requested node from the set of immediate children.
If the argument is numeric, then the in-sequence array of children is accessed (see Tree#children). If the argument is NOT numeric, then it is assumed to be name of the child node to be returned.
Raises an exception is the requested child node is not found.
Adds the specified child node to the receiver node.
This method can also be used for grafting a subtree into the receiver node’s tree, if the specified child node is the root of a subtree (i.e., has child nodes under it).
The receiver node becomes parent of the node passed in as the argument, and the child is added as the last child (“right most”) in the current set of children of the receiver node.
Returns the added child node.
An exception is raised if another child node with the same name exists.
Returns breadth of the tree at the receiver node’s level. A single node without siblings has a breadth of 1.
Breadth is defined to be:
Breadth: | Number of sibling nodes to this node + 1 (this node itself), i.e., the number of children the parent of this node has. |
Performs breadth first traversal of the tree starting at the receiver node. The traversal at a given level is from left to right.
Returns an array of all the immediate children of the receiver node.
If a block is given, yields each child node to the block traversing from left to right.
Returns depth of the tree from the receiver node. A single leaf node has a depth of 1.
This method is DEPRECATED and may be removed in the subsequent releases. Note that the value returned by this method is actually the:
height + 1 of the node, NOT the depth.
For correct and conventional behavior, please use Tree::TreeNode#nodeDepth and Tree::TreeNode#nodeHeight methods instead.
Returns a copy of the receiver node, with its parent and children links removed. The original node remains attached to its tree.
Traverses every node (including the receiver node) from the (sub)tree by yielding the node to the specified block.
The traversal is depth-first and from left to right in pre-ordered sequence.
Yields all leaf nodes from the receiver node to the specified block.
May yield this node as well if this is a leaf node. Leaf traversal is depth-first and left to right.
Returns the first sibling for the receiver node. If this is the root node, returns itself.
‘First’ sibling is defined as follows:
First sibling: | The left-most child of the receiver’s parent, which may be the receiver itself |
Returns true if the receiver is a root node. Note that orphaned children will also be reported as root nodes.
Returns the last sibling for the receiver node. If this is the root node, returns itself.
‘Last’ sibling is defined as follows:
Last sibling: | The right-most child of the receiver’s parent, which may be the receiver itself |
Loads a marshalled dump of a tree and returns the root node of the reconstructed tree. See the Marshal class for additional details.
Returns the next sibling for the receiver node. The ‘next’ node is defined as the node to right of the receiver node.
Will return nil if no subsequent node is present.
Returns depth of the receiver node in its tree. Depth of a node is defined as:
Depth: | Length of the node’s path to its root. Depth of a root node is zero. |
Note that the deprecated method Tree::TreeNode#depth was incorrectly computing this value. Please replace all calls to the old method with Tree::TreeNode#nodeDepth instead.
Returns height of the (sub)tree from the receiver node. Height of a node is defined as:
Height: | Length of the longest downward path to a leaf from the node. |
Returns an array of ancestors of the receiver node in reversed order (the first element is the immediate parent of the receiver).
Returns nil if the receiver is a root node.
Traverses the tree in a pre-ordered sequence. This is equivalent to TreeNode#each
Returns the previous sibling for the receiver node. The ‘previous’ node is defined as the node to left of the receiver node.
Will return nil if no predecessor node is present.
Removes the specified child node from the receiver node.
This method can also be used for pruning a subtree, in cases where the removed child node is the root of the subtree to be pruned.
The removed child node is orphaned but accessible if an alternate reference exists. If accesible via an alternate reference, the removed child will report itself as a root node for its subtree.
Returns the child node.
Removes the receiver node from its parent. The reciever node becomes the new root for its subtree.
If this is the root node, then does nothing.
Returns self (the removed receiver node) if the operation is successful, and nil otherwise.
Returns root node for the (sub)tree to which the receiver node belongs.
Note that a root node’s root is itself (beware of any loop construct that may become infinite!)
Returns an array of siblings for the receiver node. The receiver node is excluded.
If a block is provided, yields each of the sibling nodes to the block. The root always has nil siblings.