Class: Tree::BinaryTreeNode

Inherits:
TreeNode show all
Defined in:
lib/tree/binarytree.rb

Overview

Provides a Binary tree implementation. This node allows only two child nodes (left and right child). It also provides direct access to the left or right child, including assignment to the same.

This inherits from the TreeNode class.

Author:

Core Attributes (collapse)

Instance Attribute Summary (collapse)

Structure Modification (collapse)

Constructor Details

This class inherits a constructor from Tree::TreeNode

Dynamic Method Handling

This class handles dynamic methods through the method_missing method in the class Tree::Utils::CamelCaseMethodHandler

Instance Attribute Details

- (Integer) breadth (readonly) Originally defined in module Utils::TreeMetricsHandler

Breadth of the tree at this 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.

Returns:

  • (Integer)

    breadth of the node's level.

- (Object) content Originally defined in class TreeNode

Content of this node. Can be nil. Note that there is no uniqueness constraint related to this attribute.

See Also:

  • name

- (Integer) depth (readonly) Originally defined in module Utils::TreeMetricsHandler

Deprecated.

This method returns an incorrect value. Use the #node_depth method instead.

Depth of the tree from this 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 #node_depth and #node_height methods instead.

Returns:

  • (Integer)

    depth of the node.

See Also:

- (Boolean) has_children? (readonly) Originally defined in class TreeNode

true if the this node has any child node.

Returns:

  • (Boolean)

    true if child nodes exist.

See Also:

- (Boolean) has_content? (readonly) Originally defined in class TreeNode

true if this node has content.

Returns:

  • (Boolean)

    true if the node has content.

- (Integer) in_degree (readonly) Originally defined in module Utils::TreeMetricsHandler

The incoming edge-count of this node.

In-degree is defined as:

In-degree

Number of edges arriving at the node (0 for root, 1 for all other nodes)

  • In-degree = 0 for a root or orphaned node

  • In-degree = 1 for a node which has a parent

Returns:

  • (Integer)

    The in-degree of this node.

- (Boolean) is_leaf? (readonly) Originally defined in class TreeNode

true if this node is a leaf - i.e., one without any children.

Returns:

  • (Boolean)

    true if this is a leaf node.

See Also:

- (Boolean) is_left_child?

true if the receiver node is the left child of its parent. Always returns false if it is a root node.

Returns:

  • (Boolean)

    true if this is the left child of its parent.



83
84
85
86
# File 'lib/tree/binarytree.rb', line 83

def is_left_child?
  return false if is_root?
  self == parent.left_child
end

- (Boolean) is_right_child? (readonly)

true if the receiver node is the right child of its parent. Always returns false if it is a root node.

Returns:

  • (Boolean)

    true if this is the right child of its parent.



93
94
95
96
# File 'lib/tree/binarytree.rb', line 93

def is_right_child?
  return false if is_root?
  self == parent.right_child
end

- (Boolean) is_root? (readonly) Originally defined in class TreeNode

Returns true if this is a root node. Note that orphaned children will also be reported as root nodes.

Returns:

  • (Boolean)

    true if this is a root node.

- (Tree::BinaryTreeNode) left_child

Left child of the receiver node. Note that left Child == first Child.

Returns:

See Also:



62
63
64
# File 'lib/tree/binarytree.rb', line 62

def left_child
  children.first
end

- (Integer) length (readonly) Originally defined in module Utils::TreeMetricsHandler

Deprecated.

This method name is ambiguous and may be removed. Use #size instead.

Convenience synonym for #size.

Returns:

  • (Integer)

    The total number of nodes in this (sub)tree.

See Also:

- (Object) level (readonly) Originally defined in module Utils::TreeMetricsHandler

Alias for #node_depth

See Also:

- (Object) name (readonly) Originally defined in class TreeNode

Name of this node. Expected to be unique within the tree.

Note that the name attribute really functions as an ID within the tree structure, and hence the uniqueness constraint is required.

This may be changed in the future, but for now it is best to retain unique names within the tree structure, and use the content attribute for any non-unique node requirements.

See Also:

  • content

- (Integer) node_depth (readonly) Originally defined in module Utils::TreeMetricsHandler

Depth of this 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 #depth was incorrectly computing this value. Please replace all calls to the old method with #node_depth instead.

#level is an alias for this method.

Returns:

  • (Integer)

    Depth of this node.

- (Integer) node_height (readonly) Originally defined in module Utils::TreeMetricsHandler

Height of the (sub)tree from this node. Height of a node is defined as:

Height

Length of the longest downward path to a leaf from the node.

  • Height from a root node is height of the entire tree.

  • The height of a leaf node is zero.

Returns:

  • (Integer)

    Height of the node.

- (Integer) out_degree (readonly) Originally defined in module Utils::TreeMetricsHandler

The outgoing edge-count of this node.

Out-degree is defined as:

Out-degree

Number of edges leaving the node (zero for leafs)

Returns:

  • (Integer)

    The out-degree of this node.

- (Object) parent Originally defined in class TreeNode

Parent of this node. Will be nil for a root node.

- (Array<Tree::TreeNode>?) parentage (readonly) Originally defined in class TreeNode

An array of ancestors of this node in reversed order (the first element is the immediate parent of this node).

Returns nil if this is a root node.

Returns:

  • (Array<Tree::TreeNode>)

    An array of ancestors of this node

  • (nil)

    if this is a root node.

- (Tree::BinaryTreeNode) right_child

Right child of the receiver node. Note that right child == last child unless there is only one child.

Returns nil if the right child does not exist.

Returns:

See Also:



74
75
76
# File 'lib/tree/binarytree.rb', line 74

def right_child
  children[1]
end

- (Tree::TreeNode) root (readonly) Originally defined in class TreeNode

Root node for the (sub)tree to which this node belongs. A root node's root is itself.

Returns:

- (Integer) size (readonly) Originally defined in module Utils::TreeMetricsHandler

Total number of nodes in this (sub)tree, including this node.

Size of the tree is defined as:

Size

Total number nodes in the subtree including this node.

Returns:

  • (Integer)

    Total number of nodes in this (sub)tree.

Instance Method Details

- (Object) add(child)

Adds the specified child node to the receiver node. The child node's parent is set to be the receiver.

The child nodes are added in the order of addition, i.e., the first child added becomes the left node, and the second child added will be the second node.

If only one child is present, then this will be the left child.

Parameters:

Raises:

  • (ArgumentError)

    This exception is raised if two children are already present.



110
111
112
113
114
# File 'lib/tree/binarytree.rb', line 110

def add(child)
  raise ArgumentError, "Already has two child nodes" if @children.size == 2

  super(child)
end

- (Tree::BinaryTreeNode, Enumerator) inordered_each {|node| ... }

Performs inorder traversal (including this node).

Yield Parameters:

Returns:

  • (Tree::BinaryTreeNode)

    This node, if a block is given

  • (Enumerator)

    An enumerator on this tree, if a block is not given

See Also:

Since:

  • 0.9.0



128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
# File 'lib/tree/binarytree.rb', line 128

def inordered_each(&block)

  return self.to_enum unless block_given?

  node_stack = []
  current_node = self

  until node_stack.empty? and current_node == nil
    if current_node
      node_stack.push(current_node)
      current_node = current_node.left_child
    else
      current_node = node_stack.pop()
      yield current_node
      current_node = current_node.right_child
    end
  end

  return self if block_given?

end

- (Object) swap_children

Swaps the left and right child nodes of the receiver node with each other.



195
196
197
# File 'lib/tree/binarytree.rb', line 195

def swap_children
  self.left_child, self.right_child = self.right_child, self.left_child
end