Week 6: Trolling for Trees

After our tour of Python’s memory model, we arrive at a data structure called a tree.  We will go over what is a tree and we will introduce some terms that come with trees.  So what is a tree?  A tree is set of nodes such that every node is an object with a value and a link to other nodes.  We can represent the appearance of a tree horizontally from left-to-right with this diagram.

                                                           

                                                            9                                                         

                                                                                    4

                                    5

                        2

                                                                                                11

                                                                        6

                                                                                                5

                                                7

                                                                        2

My apologies that I cannot get the vertical to work.  I could just steal one from the internet but they look very strange next to this background…

There are terms to describe the nodes by their positions.  Here are the ones that come from the analogy of the tree as a plant:

(1)  Root:  This is the node with the value of 2 at the top of the tree (or the left of the in sideways representation).

(2)  Leaves:  These are nodes with values 2, 5, 11 and 4 at the bottom of the tree (or the right of the tree in sideways representation).  They have no links to other nodes.

Here are the terms that come from the analogy of a tree as a family tree:

(1)  Parents:  These are the nodes with values 2, 7, 6, 5, and 9.  They have links to other nodes. 

(2)  Children.  Every node in a tree, except the root, is a child because they are linked by other nodes.

Here are some other terms:

(1)  Arity:  If we have a set that contains the number of children for every parent in a tree, then the arity of that tree is the maximum number in that set.   The arity for the tree above is two because every parent either has one child or two children.

(2)  Length of path:  The length of the path between two nodes is number of nodes in the sequence of every node from the first node to the last.

(3)  Depth of a node:  The depth of a node is the length of the path from the root to the node.

(4)  Tree traversal:  The act of visiting every node in the tree.  There are three ways of traversing a tree: preorder, postorder and inorder.

(5)  Preorder:  Preorder traversals start from the root.  They visit the parents first and then the left and right children.  The preorder traversal for the tree above is 2, 7, 2, 5, 6, 11, 5, 9, 4.

(6)  Postorder:  Postorder traversals start from the leftmost node.  They visit the left and right children first and then the parent.  The postorder traversal for the tree above is 2, 5, 11, 6, 7, 4, 9, 5, 2.

(7)  Inorder:  Inorder traversals also start from the leftmost node.  They visit the left child, then the parent and then the right child.  The preorder traversal for the tree above is 2, 7, 6, 5, 11, 2, 5, 9, 4.

One important thing to note is that trees are not cyclical.  Nodes of the left subtree cannot link to nodes in the right subtree.  If the node with value 4 in the tree above links to the node with value 11, then it is not a tree.

            When my professor introduced the concept of a tree to us, I did not find it terribly difficult to understand.  However, my problem with implementing classes from the post about Object-Oriented Programming are still present three weeks later.  This is mostly related to the syntax.  However, I believe I am getting better at it.  Probably a little more work should do it.