Binary Trees

Trees are a special kind of recursive structure made up of a root node, branches nodes, and leaves nodes. Siblings nodes are designated when they have the same parent node. 

Trees also have levels. These are designated by the distance at which the same siblings (or one single node) are separated from the root node.

Here's an example of what a binary tree looks like:

To define a new tree, we create a tree class by implementing the __init__ method in the following way: __init__(self, cargo, left = None, right = None).

Since trees are a recursive structure, we can create as many subtrees as desired inside left or right.

Trees are a fine way to represent data. For example, we can represent a mathematical expression using trees. The operator will be the parent node of the two operands that we want to work with.

In order to build a tree this way, we can create a list where every element of the expression will be an element of the list. Then we will implement some recursive functions to evaluate the type of these elements to know where they should be placed in the tree.

When we translate a mathematical expression into a tree, we can traverse it in multiple ways…We can get a prefix expression by traversing the tree from the root to the left and right subtrees, or get a postfix expression by traversing the tree from the left and right subtrees to the root, or an infix expression by traversing the tree from the bottom of the left subtree to the root and then from the bottom of the right subtree to the top (omitting the root at the end).

Binary trees are definitely one of the most interesting things we have learned in this course so far and I can’t wait to learn how to apply them to solve problems in real life! 

While thinking about this, I couldn’t help myself to go back to this old app I used to play with some years ago…It guesses a character that you are thinking about by traversing a tree depending on the input you give to the program! Here’s the link: http://en.akinator.com/

picture taken from: http://upload.wikimedia.org/wikibooks/en/4/41/HSE_ch5_binary_tree.png

Inheritance, Multiple Inheritance, and Composition

Inheritance is one of the most important features offered by Object-Oriented Programming languages.  We can create a subclass of a base class by passing the base class name as an argument in the subclass class definition (only if the base class is available in the current module, of course!). By proceeding this way, the subclass “inherits” all the attributes and methods of the base class. 

For example, let’s say that we create a class called Car. In the __init__ method of Car we will define some default attributed such as wheels, windows…and we will also include some methods in the implementation of this class such as accelerating or breaking…

Later on, we can create a subclass of Car called Ferrari, that will inherit all the properties of Car. This allows us to add attributes and methods to Ferrari without modifying Car and it will also save us tons of lines of code if we were going to create a Ferrari class from scratch!

Inheritance is in fact a very powerful and useful tool, but we need to know when to avoid it…

Multiple inheritance is usually something that should be avoided. This takes place when we create a subclass of two or more base classes. Multiple inheritance makes our code too complex and it can get confusing to choose names for new methods in our subclass if similar methods with similar names are defined in our base classes.

This is why we should always consider composition. We can call baseclass.__init__(self) inside the implementation of our subclass __init__ method to tell Python that we want our subclass to have the same attributes as our base class but the methods of base class will not be inherited by the subclass. Furthermore, we can call any method of the base class inside the implementation of the subclass by calling baseclass.method(self)