|
I like the word loopNode, it makes me happy.
Today was a good day. I worked for about a solid seven hours at school.
During that time i wrote and almost finished my binary search tree class, it’s setup is mostly the same as the linked list except that each node has three pointers to other nodes, one to the parent of the node, one to the lower child and one to the higher child. The instructions to the assignment states that i need to have functions for inserting a value, erasing a value, searching for a value, getting the size of the tree, one function that gives the traversal_in_order assortment of the values, one which gives the traversal_in_order and one that gives the traversal_post_order.
During the day i finished the functions for inserting and erasing values, i was unsure what i was supposed to return with the search function so i waited with it, the size function i solved the easy way by letting the tree keep a global variable which i change whenever i add or remove a node from the tree, the traversals i only finished one off as i was busy getting the erase function to work.
I probably could have done the size function by taking a function for traversal and add count the numbers but i think my solution might be simpler.
The most difficult thing i did today was the function for erasing nodes. When erasing a node there was 1 X 2 X 3 X 4 (i think) different possibilities of whether the node had any children and if they themselves had children of their own. Depending on the combination, the connecting pointers between the nodes have to be changed to new values. This is especially hard if both nodes connected to the node to be removed have two nodes each. What i did was to follow a tip i got during the day, using the following segment of code.
node * searchNode = loopNode->lowChild->highChild;
while (searchNode->highChild != nullptr)
{
searchNode = searchNode->highChild;
}
loopNode->data = searchNode->data;
searchNode->parent->highChild = nullptr;
searchNode = nullptr;
What it does is basically to go through the high child of the low child connected to the node to be deleted. When it finds one without a high child, it removes that node and sets the original node to be removed to the value of the now removed node. I chose to take the higher of the lower for no particular reason.
What i notice now is that this does not account for whether this final node contains a lower child, i will have to fix that tomorrow.
In other news, i went through the linked list and tested all the functions until they worked as intended and changed all my nodes to be pointers rather than just variables who would disappear at the end of the current scope.
All in all a good day. I hope to be compleatley done with this assignment by Friday.
 
|