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:

Instance Attribute Summary (collapse)

Instance Method Summary (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::TreeNode

Instance Attribute Details

- (Integer) breadth (readonly) Originally defined in class TreeNode

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.

Returns:

  • (Integer) —

    breadth of the node's level.

- (Array<Tree::TreeNode>) children {|child| ... } Originally defined in class TreeNode

An array of all the immediate children of the receiver node. The child nodes are ordered "left-to-right" in the returned array.

If a block is given, yields each child node to the block traversing from left to right.

Yields:

  • (child) —

    Each child is passed to the block, if given

Yield Parameters:

Returns:

  • (Array<Tree::TreeNode>) —

    An array of the child nodes, if no block is given.

- (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

- (Tree::TreeNode) first_child Originally defined in class TreeNode

First child of the receiver node. Will be nil if no children are present.

Returns:

- (Tree::TreeNode) first_sibling Originally defined in class TreeNode

First sibling of the receiver node. If this is the root node, then 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:

See Also:

- (Integer) in_degree (readonly) Originally defined in class TreeNode

The incoming edge-count of the receiver 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.

- (Tree::TreeNode) last_child Originally defined in class TreeNode

Last child of the receiver node. Will be nil if no children are present.

Returns:

- (Tree::TreeNode) last_sibling Originally defined in class TreeNode

Last sibling of the receiver node. If this is the root node, then 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

Returns:

See Also:

- (Tree::BinaryTreeNode) left_child

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

Returns:

See Also:



76
77
78
 
# File 'lib/tree/binarytree.rb', line 76

def left_child
  children.first
end

- (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

- (Tree::treeNode) next_sibling Originally defined in class TreeNode

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, or if the receiver is a root node.

Returns:

  • (Tree::treeNode) —

    the next sibling node, if present.

See Also:

- (Integer) node_depth (readonly) Also known as: level Originally defined in class TreeNode

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#node_depth instead.

'level' is an alias for this method.

Returns:

  • (Integer) —

    Depth of this node.

- (Integer) node_height (readonly) Originally defined in class TreeNode

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.

  • 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 class TreeNode

The outgoing edge-count of the receiver 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?) parentage (readonly) Originally defined in class TreeNode

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.

Returns:

  • (Array, nil) —

    An array of ancestors of the receiver node, or nil if this is a root node.

- (Tree::treeNode) previous_sibling Originally defined in class TreeNode

Previous sibling of the receiver node. 'Previous' node is defined to be the node to left of the receiver node.

Will return nil if no predecessor node is present, or if the receiver is a root node.

Returns:

  • (Tree::treeNode) —

    the previous sibling node, if present.

See Also:

- (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:



88
89
90
 
# File 'lib/tree/binarytree.rb', line 88

def right_child
  children[1]
end

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

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

Returns:

- (Array<Tree::TreeNode>) siblings {|sibling| ... } Originally defined in class TreeNode

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.

Yields:

  • (sibling) —

    Each sibling is passed to the block.

Yield Parameters:

Returns:

See Also:

- (Integer) size (readonly) Originally defined in class TreeNode

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

Size of the tree is defined as:

Size

Total number nodes in the subtree including the receiver 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.



64
65
66
67
68
 
# File 'lib/tree/binarytree.rb', line 64

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

  super(child)
end

- (Boolean) is_left_child?

Returns 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.



138
139
140
141
 
# File 'lib/tree/binarytree.rb', line 138

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

- (Boolean) is_right_child?

Returns 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.



147
148
149
150
 
# File 'lib/tree/binarytree.rb', line 147

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

- (Object) swap_children

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



153
154
155
 
# File 'lib/tree/binarytree.rb', line 153

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