I'm used to implement tree structures in object oriented languages, which of course is a nice thing to be able to do. For some time now I've been doing some coding in C, first the shell to learn more about pipes, forks and so on, this time it's about implementing a tree structure in C, each node in the tree has 2 parents (a left and a right) and 2 children, the idea is more of a grid where a nodes left child can be the left parents, left childs, right child (if that makes sense).
The idea of this, is to try and take the maximum sum of a path, from the top to the bottom.
More over I'm parsing the tree structure from a file, where the structure is a bit like this (without the spaces at the beginning):
75 95 64 17 47 82 18 35 87 10 20 04 82 47 65 19 01 23 75 03 34 88 02 77 73 07 63 67 99 65 04 28 06 16 70 92 41 41 26 56 83 40 80 70 33 41 48 72 33 47 32 37 16 94 29 53 71 44 65 25 43 91 52 97 51 14 70 11 33 28 77 73 17 78 39 68 17 57 91 71 52 38 17 14 91 43 58 50 27 29 48 63 66 04 68 89 53 67 30 73 16 69 87 40 31 04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
So for instance if we take 35, which is in the 4. line, it has 17 as left parent, 47 as right parent, 4 as left child and 82 as right child.
The struct I use for this is pretty basic:
The sum is used to keep intermediate calculations, the value is the number the node repressents, the rest is pretty self self explainatory.
The parsing is done using a pointer for the current node, and a pointer to the top. There are 3 cases, which are all explained here:
- If we encounter a space (' '), we move the current node pointer to its parent right, then we check to see if current's right is null, if so we allocate it, then we check to see if currents right parent isn't null and that current right parents right child isn't null, if that's the case, we then set the new nodes right parent to currents parents rights, right node and the other way around. The we move current to current right, which is the new node (or an existing node) and add 1 to a "rowcount" variable.
- If we encounter a newline('\n'), current now points to the top node of the tree, then we follow the left child down "rowcount" - 1 times and allocate on our way down as necessary. This time we try to set new nodes left parent and vica versa (as described above, just the other direction). Then we reset "rowcount" to 0.
- If we encounter a number, we then set currents value to that number, if there's already a part of a number in value, we take that and multiplies it by 10, then adds the new value. So if 3 is in value, and we encounter 4, it's: 3 * 10 + 4, which is 34.
Now for the recursive iteration through the tree:
The recursion is pretty basic, it simply calculates the sum of the child node to the left and right, returning the maximum of these upwards, the sum variable here stores the result, so if we encounter the same node again (which we will in big trees), we don't have to calculate the sum again. This gives an extreme speed increase, since all sums only have to be calculated once:
Now there's an apparent problem here, if the sum of a deep subtree is 0, it'll get recalculated without the sum.
Now then, since I use malloc for the tree, it means everything in the tree is allocated on the heap. For this I made a function that frees a tree (or subtree), it's pretty basic since it just checks if both children are NULL, if not we call recursively, then we make sure that the parents (if any) aren't pointing to this node anymore. Then we free the current node and return.
Now this is how I chose to solve a problem found at project euler, which is why I don't link the code in it's full version.