A tree is another data structure that you can use to store pieces of information, or rather, a bunch of elements.
Here, we'll consider elements that each have a key (that identifies the element) and a value (that is the data for an element), however, we'll ignore the value part for now.
Here is an example of a tree whose keys are letters:
tree ---- j <-- root / \ f k / \ \ a h z <-- leaves
Is k a leaf? Who is its parent?
How many parents can elements have?
For example, let's look at our tree of letters and examine the part starting at f and everything under it...
tree ---- j / \ f k / \ \ a h z
Doesn't it look like a tree itself? In this subtree, what is f (recall our vocabulary)?
What about just z? Doesn't it look like a subtree?
A tree whose elements have at most 2 children is called a binary tree.
Since each element in a binary tree can have only 2 children, we typically name them the left and right child.
The structure of a tree is hierarchical, meaning that things are ordered above or below other things. For example, the army is hierarchical, with generals above colonels, and colonels above lieutenants, etc.
Despite the hierarchical order of the structure of the tree, the order enforced on elements in the tree will depend on how we use the tree.
First, remember that the letters in the tree are keys for the elements held in the tree.
For any element, keys to its left are less than its own key. Also, keys to its right are greater than its own key. E.g.:
j f<j k>j / \ f k
Note that this is true for every element.
A tree with this ordering property AND that is binary is called a binary search tree. Why? Because in order to search for an element (with a specific key) in such a tree, you only need to make a series of binary (i.e., go left or right) decisions.
For example, to find h starting from the tree's root...
tree ---- j <-- root / \ f k / \ \ a h z <-- leaves
Moreover, searching in a binary search tree is easier than in an unordered tree since no backtracking is required.
Here are the operations that we will concern ourselves with for this binary search tree. You may need others for a particular use of the tree.
Add:
Places an element in the tree, maintaining the correct order.
For example, Add(tree, i)
tree ---- j <-- root / \ f k / \ \ a h z \ i <-- new leaf
To produce that tree, we added the elements in the following order:
j, f, k, a, h, z, i
What would the tree have looked like if we added these elements in the order: j, k, z, f, h, i, a? What about the order: a, z, k, f, i, h, j?
Since we typically use elements, each with a unique key, it is reasonable to require that there are no two elements in the tree with the same key.
IsMember:
Reports whether some element is in the tree.
For example, IsMember(tree, a)
IsMember(tree, y)
Print:
We also want something to print out the elements in the tree in key order (ascending or descending).
Printing out the elements in ascending order would give:
a f h i j k z
What would the list of elements be in descending order?
Does what the tree looks like affect the order that things are printed out?
Which of the operations need entire elements and which require only keys?
Let's consider an algorithm for adding an element to a binary search tree.
Adding an element requires searching for the proper place to put the new element, so that the binary search order will be preserved.
We've already seen that no backtracking is needed when searching the tree, so our algorithm can use iteration (looping)--it does not require recursion.
Here is an outline of such an algorithm (that assumes there is at least one element in the tree):
Add(tree, element)
[iterative]
while (not done) if (element's key < root's key) if (no left child of root) put new element left of root done! else tree = left subtree else if (element's key > root's key) if (no right child of root) put new element right of root done! else tree = right subtree else do whatever you do when key is already in tree done!
When the algorithm begins, it is given the entire tree.
As it continues to search, it works it's way to lower and lower subtrees.
We want to implement a binary search tree that has the above properties and operations in C. Although we could use an array to implement a tree, we'll use an implementation more akin to a linked list...
Recall that our trees store elements with both a key and a value. For simplicity, assume the values are just integers (a count, e.g.). The types needed for elements are thus:
typedef char treeKeyT; typedef int treeValueT; typedef struct { treeKeyT key; treeValueT value; } treeElementT;
Now, how will these elements be stored in a tree?
Like a linked list, elements will be stored in nodes. Furthermore, a node will have to keep track of its element's immediate children. How will a node keep track of the left and right child?
Answer: Like a linked list, nodes will point to one another in the tree--each node will point to the left and right child's node.
The type needed for a node is thus:
typedef struct treeNodeTag { treeElementT element; struct treeNodeTag *left, *right; } treeNodeT;
When there is no left or right child, of course, we'll make the corresponding
pointers NULL
.
Now, let's return to our original tree, but view
it as if it was made up of these C treeNodeT
s...
----- |j | |5 | |---| | | | /---\ v v ----- ----- |f | |k | |30 | |13 | |---| |---| | | | |0| | /---\ ----\ v v v ----- ----- ----- |a | |h | |z | |100| |50 | |1 | |---| |---| |---| |0|0| |0|0| |0|0| ----- ----- -----
While these nodes suffice to keep track of all the elements, what do we need to keep track of the whole tree?
Answer: We need a pointer to the root of the tree!
Answer: There are no nodes, so the pointer to the root should
be NULL
.
We have already thought a little about the types needed for our tree. Let's now think about how to organize those types and use them with an ADT/CDT design.
As usual, we'll put our tree data structure in its own module,
creating the source files tree.h
and tree.c
.
The types for a key, value and element
should be part of the interface in tree.h
.
The type for a node is an implementation detail, and thus,
goes in tree.c
.
Finally, we need something that holds all the information needed to keep track of the tree. We saw that this should be a pointer to the node at the root of the tree.
Since this pointer has to do with the implementation of the
tree, we put it in the concrete type, struct
treeCDT
:
typedef struct treeCDT { treeNodeT *root; } treeCDT;
which goes in tree.c
.
In the interface (tree.h
), we must fill in what the
abstract type is as follows:
typedef struct treeCDT *treeADT;
Finally, we have:
tree.h tree.c ------ ------ #include "tree.h" typedef char treeKeyT; typedef struct treeNodeTag { treeElementT element; typedef int treeValueT; struct treeNodeTag *left, *right; typedef struct { } treeNodeT; treeKeyT key; treeValueT value; } treeElementT; typedef struct treeCDT typedef struct treeCDT { *treeADT; treeNodeT *root; } treeCDT;
Now that we've finished the types, let's discuss the tree functions. Based on the tree operations we mentioned above, the tree functions we'll need are:
We've briefly discussed the types and functions needed. Before we discuss implementing any functions, take a look at the test program treetest.c to see how the types and functions (from the tree module) will be used.
Let's now consider what is needed for 2 tree functions:
TreeCreate()
and TreeAdd()
.
TreeCreate:
Prototype:
treeADT TreeCreate(void);
Remember that a treeADT
is just a pointer, so
TreeCreate()
will have to create a treeCDT
,
initialize it, and give back a pointer to the CDT.
TreeAdd:
Prototype:
void TreeAdd(treeADT tree, treeElementT element);
We've already discussed an algorithm for adding an element.
Remember we assumed adding an element to a tree with at least one element, so adding to an empty tree is a special case...How do we detect that case and then what do we do?
Also remember that since no backtracking is needed when finding where to place an element in a binary search tree, we wrote the algorithm using iteration.
Go ahead and implement these functions!
If desired, you may write the other functions needed for the binary search tree.
Fill in the prototypes for the rest of the tree functions:
treeADT TreeCreate(void); return-type TreeDestroy(parameters); return-type TreeIsMember(parameters); void TreeAdd(treeADT tree, treeElementT element); return-type TreePrint(parameters); ...
For functions that refer to elements, which need a complete element and which only need take a key as parameter?
After writing the prototypes, write definitions for each function.
tree.h
) and function definitions in the
implementation (tree.c
) of your tree module.
Test your implementation with the sample program treetest.c
that uses
elements that are letter/count pairs. A Makefile
is also available
for the program.