Heap Tree

[TBNolan]

Hello all

i need to be practically spoon fed- i need to create a complete binary tree. each time i call this function add() i need to detect where the next empty spot in the tree is is using the two variables, count (the number of nodes in the tree) and height (the depth/number of rows to the tree). I also am passing a pointer to the root of the tree. I was planning on starting at the root and navigating, left to right, until i hit a leaf or a node with only one child.

any suggestions? maybe recursion? i just cant seem to wrap my head around the logic.

Thank you in advance

[redhead]

The value you're adding will determain where in teh tree it is going to be located, your seach tree here will always have values less than (or equal to) your value to add placed on the left branch, values higher placed on the right.

So some sort of bubble sort algorithm would do, see if the leaf value is less or equal to, then go right, if higher go left, when leaf holds an empty branch in the intended direction, place value here.

The real problem arises when deleting from the tree, then you'd need a balance function to make sure the tree structurial will allways support your adding scheme.

But most likely this tree handling, beeing adding, deleting or balancing will require some form of recursive calling.

[TBNolan]

Originally Posted by redhead

The value you're adding will determain where in teh tree it is going to be located, your seach tree here will always have values less than (or equal to) your value to add placed on the left branch, values higher placed on the right.

i understand that once i add it to the heap, i will need to 'reheapify' to make sure each parent is less than its child---

i plan to add the new entry to the next available location, maintaining the Complete Binary Tree property, but then it will not be a heap, so i will then re-heapify.

the problem arises when i try to find the next available place that will maintain the CBT. i can't seem to come up with the correct algorithm to do this using only count, height, and a pointer to the root node.

[redhead]

I've found a few pointers which might be of use for you.
First the theory in heap trees
Then two implementations 1; 2 in C++
Then an example in C

These might no be, exactly what you're looking for, but it should give you a clear view on how you want to implement it.