Creating a Generic Class The .NET Framework Class Library contains a number of generic classes readily available for you. You can also define your own generic classes, which is what you will do in this section. Before we do this, I will provide a bit of background theory. The Theory of Binary Trees In the following exercises, you will define and use a class that represents a binary tree. This is a very practical exercise because this class happens to be one that is missing from the | Creating a Generic Class The .NET Framework Class Library contains a number of generic classes readily available for you. You can also define your own generic classes which is what you will do in this section. Before we do this I will provide a bit of background theory. The Theory of Binary Trees In the following exercises you will define and use a class that represents a binary tree. This is a very practical exercise because this class happens to be one that is missing from the namespace. A binary tree is a very useful data structure used for a variety of operations including sorting and searching through data very quickly. There are volumes written on the minutiae of binary trees but it is not the purpose of this book to cover binary trees in detail. Instead we will just look at the pertinent details. If you are interested you should consult a book such as The Art of Computer Programming Volume 3 Sorting and Searching by Donald E. Knuth Addison-Wesley Professional 2nd edition 1998 . A binary tree is a recursive self-referencing data structure that can either be empty or comprise three elements some data that is typically referred to as the node and two subtrees which are themselves binary trees. The two sub-trees are conventionally called the left sub-tree and the right sub-tree because they are typically depicted to the left and right of the node respectively. Each left sub-tree or right sub-tree is either empty or contains a node and other sub-trees. In theory the whole structure can continue ad infinitum. Figure 17-1 shows the structure of a small binary tree. The real power of binary trees becomes evident when you use them for sorting data. If you start with an unordered sequence of objects of the same type you can use them to construct an ordered binary tree and then walk through the tree to visit each node in an ordered sequence. The algorithm for inserting an item into an ordered binary tree is shown below If the tree T is empty
