Class: Tree::BinaryTreeNode
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.
Core Attributes collapse

#left_child ⇒ Tree::BinaryTreeNode
Left child of the receiver node.

#left_child? ⇒ Boolean
(also: #is_left_child?)
true
if the receiver node is the left child of its parent. 
#right_child ⇒ Tree::BinaryTreeNode
Right child of the receiver node.

#right_child? ⇒ Boolean
(also: #is_right_child?)
readonly
true
if the receiver node is the right child of its parent.
Metrics and Measures collapse

#breadth ⇒ Integer
included
from Utils::TreeMetricsHandler
readonly
Breadth of the tree at this node’s level.

#in_degree ⇒ Integer
included
from Utils::TreeMetricsHandler
readonly
The incoming edgecount of this node.

#length ⇒ Integer
included
from Utils::TreeMetricsHandler
readonly
deprecated
Deprecated.
This method name is ambiguous and may be removed. Use

#level ⇒ Object
included
from Utils::TreeMetricsHandler
readonly
Alias for Utils::TreeMetricsHandler#node_depth.

#node_depth ⇒ Integer
included
from Utils::TreeMetricsHandler
readonly
Depth of this node in its tree.

#node_height ⇒ Integer
included
from Utils::TreeMetricsHandler
readonly
Height of the (sub)tree from this node.

#out_degree ⇒ Integer
included
from Utils::TreeMetricsHandler
readonly
The outgoing edgecount of this node.

#size ⇒ Integer
included
from Utils::TreeMetricsHandler
readonly
Total number of nodes in this (sub)tree, including this node.
Structure Modification collapse

#add(child) ⇒ Object
Adds the specified child node to the receiver node.

#add_from_hash(hashed_subtree) ⇒ Array
Instantiate and insert child nodes from data in a Ruby
Hash
. 
#inordered_each {node ... } ⇒ Tree::BinaryTreeNode, Enumerator
Performs inorder traversal (including this node).

#swap_children ⇒ Object
Swaps the left and right child nodes of the receiver node with each other.
Constructor Details
This class inherits a constructor from Tree::TreeNode
Instance Attribute Details
#breadth ⇒ Integer (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.
#in_degree ⇒ Integer (readonly) Originally defined in module Utils::TreeMetricsHandler
The incoming edgecount of this node.
Indegree is defined as:
 Indegree

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

Indegree = 0 for a root or orphaned node

Indegree = 1 for a node which has a parent
#left_child ⇒ Tree::BinaryTreeNode
Left child of the receiver node. Note that left Child == first Child.
60 61 62 
# File 'lib/tree/binarytree.rb', line 60 def left_child children.first end 
#left_child? ⇒ Boolean Also known as: is_left_child?
true
if the receiver node is the left child of its parent. Always returns false
if it is a root node.
83 84 85 86 87 
# File 'lib/tree/binarytree.rb', line 83 def left_child? return false if root? self == parent.left_child end 
#length ⇒ Integer (readonly) Originally defined in module Utils::TreeMetricsHandler
#level ⇒ Object (readonly) Originally defined in module Utils::TreeMetricsHandler
Alias for #node_depth
#node_depth ⇒ Integer (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.
#level is an alias for this method.
#node_height ⇒ Integer (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.
#out_degree ⇒ Integer (readonly) Originally defined in module Utils::TreeMetricsHandler
The outgoing edgecount of this node.
Outdegree is defined as:
 Outdegree

Number of edges leaving the node (zero for leafs)
#right_child ⇒ Tree::BinaryTreeNode
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.
74 75 76 
# File 'lib/tree/binarytree.rb', line 74 def right_child children[1] end 
#right_child? ⇒ Boolean (readonly) Also known as: is_right_child?
true
if the receiver node is the right child of its parent. Always returns false
if it is a root node.
96 97 98 99 100 
# File 'lib/tree/binarytree.rb', line 96 def right_child? return false if root? self == parent.right_child end 
#size ⇒ Integer (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.
Instance Method Details
#add(child) ⇒ Object
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.
119 120 121 122 123 
# File 'lib/tree/binarytree.rb', line 119 def add(child) raise ArgumentError, 'Already has two child nodes' if @children.size == 2 super(child) end 
#add_from_hash(hashed_subtree) ⇒ Array
Instantiate and insert child nodes from data in a Ruby Hash
This method is used in conjunction with TreeNode.from_hash to provide a convenient way of building and inserting child nodes present in a Ruby hashes.
This method will instantiate a TreeNode instance for each top level key of the input hash, to be inserted as children of the receiver instance.
Nested hashes are expected and further child nodes will be created and added accordingly. If a hash key is a single value that value will be used as the name for the node. If a hash key is an Array, both node name and content will be populated.
A leaf element of the tree should be represented as a hash key with corresponding value nil or {}.
>
154 155 156 157 158 159 
# File 'lib/tree/binarytree.rb', line 154 def add_from_hash(hashed_subtree) raise ArgumentError, 'Too many children'\ if hashed_subtree.size + @children.size > 2 super(hashed_subtree) end 
#inordered_each {node ... } ⇒ Tree::BinaryTreeNode, Enumerator
Performs inorder traversal (including this node).
noinspection RubyUnusedLocalVariable
174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 
# File 'lib/tree/binarytree.rb', line 174 def inordered_each return to_enum unless block_given? node_stack = [] current_node = self until node_stack.empty? && 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 self if block_given? end 
#swap_children ⇒ Object
Swaps the left and right child nodes of the receiver node with each other.
246 247 248 
# File 'lib/tree/binarytree.rb', line 246 def swap_children self.left_child, self.right_child = right_child, left_child end 