Teaching graph theory is nice because you can always draw a picture. A simple example can be drawn on the board and you can go through it step by step and for most students, the ideas sink in.Teaching graph theory is useful because it is a way to set up problems that computers can solve, so it helps to have an understanding of how the information of a graph will be represented in a computer.
Computers allow programmers to create arrays. An array is a list of data. As the programmer, I can type in "int Tree[100];", and the computer sets aside 100 memory locations of type "int" in a row that are called Tree[0], Tree[1], Tree[2], ... up to Tree[99]. Computers and programmers are used to the idea of starting counting at zero instead of one, but the data structure for a binary tree is easiest if we ignore Tree[0] and start the root of the tree at Tree[1]. We then have the next level, the children of Tree[1] at Tree[2] and Tree[3], the children of tree[2] are at Tree[4] and Tree[5], the children of Tree[3] at Tree[6] and Tree[7], and on and on. This makes for a simple way in computers to find the children of a node and the parent of a node.
Take the position of a node on the list and multiply that number by two to get the left child, and add one more to the left child number to get the right child. For example, the children of Tree[25] are at Tree[50] and Tree[51].
Take the position of a node and divide by two to get the parent position. If the number is odd, ignore the ½ and just use the whole number that remains. (Note: because I asked for "int" memory locations, the computer is forced to ignore the ½ when dividing, so that makes life easy in this particular instance.)
The parent of Tree[51] is Tree[25]. The parent of Tree[25] is Tree[12], whose parent is Tree[6], whose parent is Tree[3], whose parent is the root node Tree[1].
Let's look at the trees from last week and see how a computer would store the information. Whenever we get a node that that has no children, the location on the list should have a number that shows it is empty. On factor trees, we never use the number 0 as a factor, so 0 will be the number we use to show a position is empty.
Tree on the left:
Tree[1] = 300
Tree[2] = 30 || Tree[3] = 10
Tree[4] = 5 || Tree[5] = 6 || Tree[6] = 5 || Tree[7] = 2
Tree[8] = 0 || Tree[9] = 0 || Tree[10] = 3 || Tree[11] = 2 || Tree[12] = 0 ...
Tree on the right:
Tree[1] = 300
Tree[2] = 150 || Tree[3] = 2
Tree[4] = 15 || Tree[5] = 10 || Tree[6] = 0 || Tree[7] = 0
Tree[8] = 3 || Tree[9] = 5 || Tree[10] = 5 || Tree[11] = 2 || Tree[12] = 0 ...
The ellipsis in both lists indicates that all the entries are 0 for the entire rest of the list.
I know this will make sense to anyone who has programmed a computer. I'm not as sure if it makes sense to folks who have never done that task, which can be both enjoyable and frustrating. If you are in that second group, drop a note to tell me how much sense this makes.
