What is a binary tree and why do we use it?

                                                                                                                                                                                                                                                                                                 

 

    A binary tree is a structure used to represent hierarchical data through the use of binary search and link lists.  It is composed of nodes, where each node has a data element, a right pointer and a left pointer These right and left pointers point to lower sub-trees on each side of the node. The following diagram represents a binary tree:

    There also exists a binary search tree (such as the one above). This is a type of binary tree where the nodes have been arranged in an order. The node arrangement is dependent on the values of the data elements and the left and right pointers. For each of the nodes, the left sub-tree should have a value less or equal to the data element value. For the right sub-tree, the value should be higher than the data element. Other important terms that should be considered are the leaves and the internal nodes. The leaves represent the nodes located at the bottom of the tree, while the internal nodes correspond to every node between the origin and leaves of the tree.

Problems:                       

                                                       

 

    "The major problem lies in the manner in which we laid out our records.  Even if we physically move the records such that they are ordered in some fashion (i.e, the 1st record is located before the 2nd, the 2nd before the 3rd, and so forth) because we can not calculate the base address of any record on the list (as we can with an array), we must still perform a sequential in order to locate a record."

 

As discussed in class, as well as Professor Kirs' slides this is how we set up a binary tree!!!

"Constructing a binary tree is relatively simple, but constructing a "good" tree (we will see examples of good trees versus bad trees later) is often difficult.  The manner in which we established our tree was perhaps the simplest way (although we admit that we "rigged" the order in which they were placed in the unordered list).  We took the first element in the list and established it as the root.  We then took each of the remaining elements (in order, we'll add them on two at a time to save space) and determined where we should put them (smaller values to the left, larger values to the right)."  (Textbook Material)

        Step 1.

                

                       

                        

                       

Terminology:

A tree is a hierarchical structure.                            

In our tree, the numbers are arranged by magnitude or size.  Smaller numbers are to the left and larger numbers are to the right.

Recurssion is a programming technique which allows a function to call itself.

Without recurssion, traversing (moving about) binary trees become very difficult.

Leaf is also referred to as a terminal node.