Package dsc_suite :: Package tools :: Module graphtheory :: Class BinaryTrees
[hide private]
[frames] | no frames]

Class BinaryTrees

source code

object --+
         |
        BinaryTrees

class BinaryTree() - basic BT functionality

This class implements basic binary tree functionality, such as binary tree generation and numbering.

Most methods are static (class) methods. Basically, this class is used to encapsulated conjoined functions.

Instance Methods [hide private]

Inherited from object: __delattr__, __format__, __getattribute__, __hash__, __init__, __new__, __reduce__, __reduce_ex__, __repr__, __setattr__, __sizeof__, __str__, __subclasshook__

Static Methods [hide private]
 
get_num_binary_trees(n)
Calculate number of possible binary trees.
source code
 
get_binary_tree(n, i)
Generate number i binary tree as a binary in order sequence.
source code
 
generate_relations(topology)
Generate topology relations from a given pre-order representation.
source code
 
generate_inversion_table(n, result, i=0, d=0, s=[]) source code
 
get_binary_trees(n) source code
Properties [hide private]

Inherited from object: __class__

Method Details [hide private]

get_num_binary_trees(n)
Static Method

source code 

Calculate number of possible binary trees.

n -> number of inner nodes

Return catalan number of n.

get_binary_tree(n, i)
Static Method

source code 

Generate number i binary tree as a binary in order sequence.

n -> number of inner nodes i -> index of binary tree, 0 <= i < catalan_number(n)

From all possible binary trees with n inner nodes the i'tht tree is generated as an pre-order binary sequence. Algorithm by Ruskey1978.