Okay. Again, we're on an honors part of the class, largely for people who want to go on in computer science, or in the C ++ sequence. We're dealing with a especially important data structure called the binary tree. So again with these data structures, you're going to see a lot of recursion, you're going to see a lot of use of indirection, links, pointers, and we're going to try and simplify the stuff by using typedefs, and this material is also found in a book on, see in Chapter 10.8. So if you have that available, you can read about it as well in detail. So let's start with a typedef up char. Let's realize that while we'll think of data as something that could be complex in our simple case, we're just going to store a character in a node of the binary tree. Struct node looks very similar to what we had for lists, except that now there's a data element, and now there are two pointers, a left and a right pointer. So those are the branches. Then we're going to make things easier to write. Well, typedef struct node as capital node, or typedef a node will typedef up a binary tree as a pointer to node. So in effect, you'll be able to look at a binary tree by a pointer to its root, that will be the critical representation within C. We have different modes, different ways to traverse the tree, and one of them is what's called an in-order mode. There's also pre-order and post-order, but I won't discuss that right here, but that's something for you to investigate. So if we do an in-order traversal of the tree, we check to see if the root is null, if the root is null we return. Otherwise, we recur to the left, we print the current, what essentially is what the data is being pointed at, and then we recur to the right. So all the lefts are going to be done first before the rights get done, and that's going to be in-order traversal. Now, we also need a way to build a tree, and we're going to build the tree by allocating off of malloc. Remember malloc is our standard library function that goes to the heap size of nodes. So however, if node gets to find size of which in effect is a key word in a built-in operation, gets as much memory as needed to represent a node. We return that value which is a pointer value. So it's a pointer value to this much memory, and then we also have a method for initializing the data. So there will be a data item, a left pointer and a right pointer, and then we assign all of that. We create a new node that's calling this function, and then we assign values to each of the three members of that struck. We're going to return a B-tree value namely a pointer value which is what we are currently pointing at, that's going to be the item created. Now, let's say we want to create a whole tree from our common data structure where we might be storing a lot of data in array. In create tree, we're going to check to see if we're done with the size of the array, this is going to be the size of the array. If we're done we don't have to do anything anymore. So we'll return the set O-pointer value null, otherwise, we'll call initialize node, create that initialized node. So let's say it's a zero, and then we create the left pointer and the right pointer. Those are also by calling create tree so this is recursive, and we use the fact that there's a mapping by the data elements, say I into, remember the tree bifurcates by factors of two. So you get two times I plus one, and two times I plus two, and those are going to be a left and right element, and they will be stored in that tree. Let's see all that work. Again, if this is all new to you, you're going to have to play with this kind of code to make sure you understand it. Once you can understand it, you can just use the idioms over and over again, or in more advanced languages like C++ such trees come in data packages so you don't have to recreate a mutual staff to understand how to use them. So here's a character array. So main is going to create a five-element character array, and we're going to store A, B, C, D, E, into that character. So D of zero is A, D of four is C etc. Then we have a B-tree. Remember this is a typedef and it's a pointer, and then we call that routine, that recursive routine up here to create a tree. We have five elements in data, and we're going to start with element zero, and we will do the in-order printing of that tree. So let's try all that out. I've already compiled this code, and here is the execution. A, B, C, D, created in the code and printed in-order gets to be D, B, E, A, C. If you walk such a tree, it will see that it comes out in that order. So this is a use of storing data into a binary tree, and remember the binary tree is going to be very useful because it can do certain kinds of operations in logarithmic time as opposed to searches that might require linear time when the data is just stored in arrays. So there are certain kinds of problems for which this kind of data structure is very, very desirable.
