Final commit

Rewrite of our original try

tree/src/tree.c

@@ -6,7 +6,8 @@
  */
 
 // Tree function: you are allowed to change the contents, but not the method signature
-Tree* tree_create(){
+Tree *tree_create()
+{
     Tree *tree = malloc(sizeof(Tree));
     tree->root = NULL;
 
@@ -14,67 +15,322 @@ Tree* tree_create(){
 }
 
 // Helper function: you are allowed to change this to your preferences
-void tree_node_delete(Node* node) {
-    if (node == NULL) return;
-
-    free(node);
+// node can be null
+void tree_node_delete(Node *node)
+{
+    if (node == NULL)
+        return;
 
     tree_node_delete(node->left);
     tree_node_delete(node->right);
+
+    free(node);
 }
 
 // Tree function: you are allowed to change the contents, but not the method signature
-void tree_delete(Tree* tree) {
+// tree cannot be null
+void tree_delete(Tree *tree)
+{
     tree_node_delete(tree->root);
-
-    free(tree);
+    tree->root = NULL;
 }
 
 // Helper function: you are allowed to change this to your preferences
-void node_insert(Node* node, int age, char* name) {
-    if (age <= node->age){
-        if (node->left == NULL){
-            Node* newLeft = malloc(sizeof(Node));
+// node cannot be null
+void node_insert(Node *node, int age, char *name)
+{
+    if (age <= node->age)
+    {
+        if (node->left == NULL)
+        {
+            Node *newLeft = malloc(sizeof(Node));
             newLeft->age = age;
             newLeft->name = name;
+            newLeft->left = NULL;
+            newLeft->right = NULL;
+            newLeft->parent = node;
             node->left = newLeft;
-        } else {
+        }
+        else
+        {
             node_insert(node->left, age, name);
         }
-    } else {
-        if (node->right == NULL){
-            Node* newRight = malloc(sizeof(Node));
+    }
+    else
+    {
+        if (node->right == NULL)
+        {
+            Node *newRight = malloc(sizeof(Node));
             newRight->age = age;
             newRight->name = name;
+            newRight->left = NULL;
+            newRight->right = NULL;
+            newRight->parent = node;
             node->right = newRight;
-        } else {
+        }
+        else
+        {
             node_insert(node->right, age, name);
         }
     }
 }
 
 // Tree function: you are allowed to change the contents, but not the method signature
-void tree_insert(Tree* tree, int age, char* name) {
-    if (tree->root == NULL) {
+// tree cannot be null
+void tree_insert(Tree *tree, int age, char *name)
+{
+    if (tree == NULL)
+    {
+        return;
+    }
+
+    if (tree->root == NULL)
+    {
         Node *node = malloc(sizeof(Node));
         node->name = name;
         node->age = age;
+        node->left = NULL;
+        node->right = NULL;
+        node->parent = NULL;
         tree->root = node;
-    } else {
+    }
+    else
+    {
         node_insert(tree->root, age, name);
     }
 }
 
 // Tree function: you are allowed to change the contents, but not the method signature
-void tree_erase(Tree* tree, int age, char* name) {
-    Node* data = tree_find(tree, age, name);
+// tree cannot be null
+void tree_erase(Tree *tree, int age, char *name)
+{
+    Node *nodeToBeDeleted = tree_find(tree, age, name);
+    printf("Node to be deleted:");
+    tree_print_node(nodeToBeDeleted);
+    printf("\n");
+
+    if (nodeToBeDeleted == NULL)
+    {
+        printf("No node to be deleted \n");
+        return;
+    }
+
+    if (nodeToBeDeleted->parent == NULL)
+    { // we're root
+        if (nodeToBeDeleted->left == NULL && nodeToBeDeleted->right == NULL)
+        { // no children
+            tree_delete(tree);
+        }
+        else if (nodeToBeDeleted->left == NULL)
+        { // no left node, so replace with direct right
+            tree->root = nodeToBeDeleted->right;
+            tree->root->parent = NULL; // remove parent
+            free(nodeToBeDeleted);
+        }
+        else
+        { // left node exists, so one step left, then right most node down the tree
+            Node *nodeToReplaceWith = find_rightmost_node(nodeToBeDeleted->left);
+            if (nodeToReplaceWith->left != NULL)
+            { // connect left child (only child) with its grandparent and vice-versa
+                nodeToReplaceWith->left->parent = nodeToReplaceWith->parent;
+                nodeToReplaceWith->parent->right = nodeToReplaceWith->left;
+            }
+            // now nodeToReplaceWith has no children anymore
+            tree->root = nodeToReplaceWith;
+            nodeToReplaceWith->parent = NULL; // remove parent because we're the new root
+            // move left child of deleted node
+            if (nodeToBeDeleted->left != nodeToReplaceWith)
+            {
+                nodeToReplaceWith->left = nodeToBeDeleted->left;
+                nodeToReplaceWith->left->parent = nodeToReplaceWith;
+            }
+            // move right child of deleted node
+            if (nodeToBeDeleted->right != nodeToReplaceWith)
+            {
+                nodeToReplaceWith->right = nodeToBeDeleted->right;
+                nodeToReplaceWith->right->parent = nodeToReplaceWith;
+            }
+            free(nodeToBeDeleted);
+        }
+    }
+    else
+    { // not root, we have a parent!
+        if (nodeToBeDeleted->left == NULL && nodeToBeDeleted->right == NULL)
+        { // no children
+            // delete reference from parent to use (need to check whether we're left or right child):
+            if (nodeToBeDeleted->parent->left == nodeToBeDeleted)
+            {
+                nodeToBeDeleted->parent->left = NULL;
+            }
+            else
+            {
+                nodeToBeDeleted->parent->right = NULL;
+            }
+            free(nodeToBeDeleted);
+        }
+        else if (nodeToBeDeleted->left == NULL)
+        { // no left node, so replace with direct right
+            // change reference from parent to our right child (need to check whether we're left or right child):
+            if (nodeToBeDeleted->parent->left == nodeToBeDeleted)
+            {
+                nodeToBeDeleted->parent->left = nodeToBeDeleted->right;
+            }
+            else
+            {
+                nodeToBeDeleted->parent->right = nodeToBeDeleted->right;
+            }
+            nodeToBeDeleted->right->parent = nodeToBeDeleted->parent;
+            free(nodeToBeDeleted);
+        }
+        else
+        {
+            // left node exists, so one step left, then right most node down the tree
+            Node *nodeToReplaceWith = find_rightmost_node(nodeToBeDeleted->left);
+            if (nodeToReplaceWith->left != NULL)
+            { // connect left child (only child) with its grandparent and vice-versa
+                nodeToReplaceWith->left->parent = nodeToReplaceWith->parent;
+                nodeToReplaceWith->parent->right = nodeToReplaceWith->left;
+            }
+            // now nodeToReplaceWith relatives have been interconnected (nodeToReplaceWith still has its child)
+            // change reference from parent to our right child (need to check whether we're left or right child):
+            if (nodeToBeDeleted->parent->left == nodeToBeDeleted)
+            {
+                nodeToBeDeleted->parent->left = nodeToReplaceWith;
+            }
+            else
+            {
+                nodeToBeDeleted->parent->right = nodeToReplaceWith;
+            }
+            if (nodeToReplaceWith->parent->left == nodeToReplaceWith)
+            {
+                nodeToReplaceWith->parent->left = NULL;
+            }
+            else
+            {
+                nodeToReplaceWith->parent->right = NULL;
+            }
+            nodeToReplaceWith->parent = nodeToBeDeleted->parent;
+            // move left child of deleted node
+            if (nodeToBeDeleted->left != nodeToReplaceWith)
+            {
+                nodeToReplaceWith->left = nodeToBeDeleted->left;
+                if (nodeToBeDeleted->left != NULL)
+                {
+                    nodeToReplaceWith->left->parent = nodeToReplaceWith;
+                }
+            }
+            // move right child of deleted node
+            if (nodeToBeDeleted->right != nodeToReplaceWith)
+            {
+                nodeToReplaceWith->right = nodeToBeDeleted->right;
+                if (nodeToBeDeleted->right != NULL)
+                {
+                    nodeToReplaceWith->right->parent = nodeToReplaceWith;
+                }
+            }
+            free(nodeToBeDeleted);
+        }
+    }
+}
+
+void printTabs(int numTabs)
+{
+    // Insert tabs before printing
+    if (numTabs > 0)
+    {
+        printf("   ");
+    }
+    for (int i = 0; i < numTabs - 1; ++i)
+    {
+        printf("|  ");
+    }
+}
+
+char *checkChildrenRelationship(Node *parentNode)
+{
+    char *result = malloc(sizeof(char) * 50);
+    if (parentNode->left != NULL)
+    {
+        if (parentNode->left->parent == parentNode)
+        {
+            strcpy(result, "left linked, ");
+        }
+        else
+        {
+            strcpy(result, "left broken, ");
+        }
+    }
+    else
+    {
+        strcpy(result, "left null, ");
+    }
+    if (parentNode->right != NULL)
+    {
+        if (parentNode->right->parent == parentNode)
+        {
+            strcat(result, "right linked");
+        }
+        else
+        {
+            strcat(result, "right broken");
+        }
+    }
+    else
+    {
+        strcat(result, "right null");
+    }
 
-    free(data);
+    return result;
 }
 
 // Helper function: you are allowed to change this to your preferences
-void tree_print_node(Node* node){
-    if (node == NULL) {
+// node can be null
+// start with numTabs = 0
+void tree_fancy_print_node(Node *node, int numTabs)
+{
+    if (node == NULL)
+    {
+        printTabs(numTabs);
+        printf("null");
+        return;
+    }
+
+    printTabs(numTabs);
+    printf("{\n");
+    printTabs(numTabs + 1);
+    char *status = checkChildrenRelationship(node); // create here because we can't free in the function itself (well, don't know how...)
+    printf("\"%d\":\"%s\" (children status: %s),\n", node->age, node->name, status);
+    free(status);
+    tree_fancy_print_node(node->left, numTabs + 1);
+    printf(",\n");
+    tree_fancy_print_node(node->right, numTabs + 1);
+    printf("\n");
+    printTabs(numTabs);
+    printf("}");
+}
+
+void tree_fancy_print(Tree *tree, int printNewline)
+{
+    // TODO can tree be null? tree->root can be
+    // Not with our implementation, since we set the root to NULL when deleting the tree instead of removing the entire tree
+    if (tree == NULL)
+    {
+        printf("Tree pointer points to null");
+        return;
+    }
+
+    tree_fancy_print_node(tree->root, 0);
+
+    if (printNewline)
+    {
+        printf("\n");
+    }
+}
+
+void tree_print_node(Node *node)
+{
+    if (node == NULL)
+    {
         printf("null");
         return;
     }
@@ -88,33 +344,102 @@ void tree_print_node(Node* node){
 }
 
 // Tree function: you are allowed to change the contents, but not the method signature
-void tree_print(Tree* tree, int printNewline){
-    if (tree == NULL) {
+void tree_print(Tree *tree, int printNewline)
+{
+    // TODO can tree be null? tree->root can be
+    // Not with our implementation, since we set the root to NULL when deleting the tree instead of removing the entire tree
+    if (tree == NULL)
+    {
         printf("null");
         return;
     }
 
     tree_print_node(tree->root);
 
-    if (printNewline){
+    if (printNewline)
+    {
         printf("\n");
     }
 }
 
 // Helper function: you are allowed to change this to your preferences
-Node* node_find(Node* node, int age, char* name) {
-    if (node->age == age && node->name == name) {
+// node can be null
+Node *node_find(Node *node, int age, char *name)
+{
+    if (node == NULL)
+    {
+        return NULL;
+    }
+    if (node->age == age && !strcmp(node->name, name))
+    {
         return node;
     }
 
-    if (age <= node->age) {
+    if (node->left == NULL && node->right == NULL)
+    {
+        return NULL;
+    }
+
+    if (age <= node->age)
+    {
         return node_find(node->left, age, name);
-    } else {
+    }
+    else
+    {
         return node_find(node->right, age, name);
     }
 }
 
 // Tree function: you are allowed to change the contents, but not the method signature
-Node* tree_find(Tree* tree, int age, char* name) {
+// tree cannot be null
+Node *tree_find(Tree *tree, int age, char *name)
+{
     return node_find(tree->root, age, name);
 }
+
+// from cannot be null
+// may return a node with children!
+Node *find_replacement_node(Node *from)
+{
+    if (from->left != NULL)
+    { // one step left, then non-stop right
+        return find_rightmost_node(from->left);
+    }
+    else if (from->right != NULL)
+    { // no left child, so we just take the only child
+        return from->right;
+    }
+    else
+    { // no children so no replacement required
+        return NULL;
+    }
+}
+
+// Assumes from is not null
+Node *find_rightmost_node(Node *from)
+{
+    while (from->right != NULL)
+    {
+        from = from->right;
+    }
+    return from;
+}
+
+// Assumes node to not be null!!
+void cut_node_free(Node *node)
+{
+    Node *parent = node->parent;
+    if (node == parent->left)
+    {
+        parent->left = NULL;
+    }
+    else
+    {
+        parent->right = node->left;
+        if (node->left)
+        {
+            node->left->parent = parent;
+        }
+    }
+    node->parent = NULL;
+}
\ No newline at end of file