Binary Trees

The types of containers we have studied so far are not the only way to store data. A storage type not discussed so far is what is known as a tree. A tree consists of a finite number of nodes (also called vertices) and a finite set of connections between these nodes (also called directed arcs). The following graph represents what a tree would look like:

The nodes are represented by the numbered circles above and the directed arcs are represented by the line segments with the arrow heads. In this tree, the node labeled 1 is referred to as the root of the tree. Those nodes that are not connected by a directed arc to any other node are called leaves. The nodes labeled with 5, 6, 7 and 8 are called leaves. The nodes that have a directed arc that connects to a node above are called the children of the node above. Therefore the nodes labeled 4 and 5 are the children of the node labeled 2. The nodes labeled 6 and 7 are similarly the children of the node labeled 3. There is a reverse relationship between these nodes as well. The node labeled 2 is called the parent of the nodes labeled 4 and 6. The node labeled 3 is the parent of the nodes labeled 6 and 7. Those trees whose nodes have at most two children are called a binary tree.

While it is possible to construct a binary tree with an array, a better tool would be a type of linked list. In considering the graphic of the binary tree above, we can see that the nodes of the linked list would need to have two pointers: one to the next node and one to the previous node. The following would be a representation of such a node:

You will notice that instead of using next and previous, left and right were used.

This model is similar to the doubly linked list in a previous lecture. The tree in the graphic above is known as a linked binary tree and would look like the following:

Notice that those nodes that are leaves have both their left and right pointers pointing to NULL. Those that have only one child have one pointer pointing to the child while the other pointer points to NULL. For example in the graphic above, the leaf that has for data the value 8 has both the left and right pointers pointing to NULL. The node that has for data the value 4 has the right pointer pointing to NULL but the left pointer is pointing to the node that has data of value 8.

From the discussion above on doubly linked lists, the binode class could be defined as the following:

 class binode {   public:     datatype data;     binode * left;     binode * right; binode()     {       left = right = NULL;     }     binode(datatype value)     {       data = value;       left = right = NULL;     }     binode(datatype value,binode* ptr1, binode * ptr2)     {       data = value;       left = ptr1;       right = ptr2;     } }; 

In the next section this class will be incorporated into another class bst that will permit what is called a binary search tree also known as a BST.