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