tree.c

#include "tree.h"
#include "mymalloc.h"

bool isLeaf(TreeNode* node){
    if(!node->left && !node->right){
        return true;
    }
    return false;
}

bool Tree_Init( Tree * const root ){
    if(!root){
        return false;
    }
    root->itemsCount = 0;
    root->root = NULL;
    return true;
}


void Tree_Clear( Tree* const root ){
    if(!root){
        return;
    }
    else{
        Tree_Clear_Rec(root->root);
        root->root = NULL;
        root->itemsCount = 0;
    }

}

void Tree_Clear_Rec(TreeNode* root){
    if(!root){
        return;
    }
    Tree_Clear_Rec(root->left);
    root->left = NULL;
    Tree_Clear_Rec(root->right);
    root->right = NULL;
    myFree(root);
}


bool Tree_Insert( Tree* const root, const Data_t data){
    if(!root || Tree_Find_Node(*root, data)){
        return false;
    }
    else{
        TreeNode* newnode = myMalloc(sizeof(TreeNode));
        if(!newnode){
            return false;
        }
        newnode->data = data;
        newnode->left = NULL;
        newnode->right = NULL;

        if(!root->root){
            root->root = newnode;
        }
        else{
            Tree_Insert_Rec(root->root, newnode);
        }

        root->itemsCount++;
        return true;
    }
}

void Tree_Insert_Rec(TreeNode* root, TreeNode* newnode){
    if(Data_Cmp(&newnode->data, &root->data) < 0){
        if(root->left){
            Tree_Insert_Rec(root->left, newnode);
        }
        else{
            root->left = newnode;
        }
    }
    else if(Data_Cmp(&newnode->data, &root->data) > 0){
        if(root->right){
            Tree_Insert_Rec(root->right, newnode);
        }
        else{
            root->right = newnode;
        }
    }
}

TreeNode * minValueNode(TreeNode* root)
{
    TreeNode* current = root;

    while (current->right != NULL)
        current = current->right;

    return current;
}


TreeNode* Tree_Delete_Rec(TreeNode* root, Data_t data)
{
    if (!root){
        return root;
    }

    else if (Data_Cmp(&data, &root->data) < 0){
        root->left = Tree_Delete_Rec(root->left, data);
    }

    else if (Data_Cmp(&data, &root->data) > 0){
        root->right = Tree_Delete_Rec(root->right, data);
    }

    else
    {
        if (!root->left)
        {
            TreeNode *temp = root->right;
            myFree(root);
            return temp;
        }
        else if (!root->right)
        {
            TreeNode *temp = root->left;
            myFree(root);
            return temp;
        }

        TreeNode* temp = minValueNode(root->left);
        root->data = temp->data;
        root->left = Tree_Delete_Rec(root->left, temp->data);
    }
    return root;
}


void Tree_Delete( Tree* const root, const Data_t data ){
    if(!root || !Tree_Find_Node(*root, data)){
        return;
    }
    else{
        root->root = Tree_Delete_Rec(root->root, data);
        root->itemsCount--;
    }
}


const Data_t *Tree_Get_Data( const TreeNode* const node ){
    if(!node){
        return NULL;
    }
    return &node->data;
}


TreeNode* Tree_Find_Node( Tree root, const Data_t data ){
    return Tree_Find_Node_Rec(data, root.root);
}

TreeNode* Tree_Find_Node_Rec(const Data_t data, TreeNode* root){
    if(!root){
        return NULL;
    }
    if(Data_Cmp(&data, &root->data) < 0){
        return Tree_Find_Node_Rec(data, root->left);
    }
    else if(Data_Cmp(&data, &root->data) > 0){
        return Tree_Find_Node_Rec(data, root->right);
    }
    else{
        return root;
    }
}

size_t Tree_Get_Count( Tree root ){
    return root.itemsCount;
}

void Tree_Process( Tree root, TreeNodeProc proc, TreeProcessMode mode ){
    if(!root.root){
        return;
    }
    switch(mode){
        case procPREORDER:
        Tree_Process_Preorder(proc, root.root);
        break;

        case procINORDER:
        Tree_Process_Inorder(proc, root.root);
        break;

        case procPOSTORDER:
        Tree_Process_Postorder(proc, root.root);
        break;
    }
}

void Tree_Process_Preorder(TreeNodeProc proc, TreeNode* root){
    (*proc)(root);
    if(root->left){
        Tree_Process_Preorder(proc, root->left);
    }
    if(root->right){
        Tree_Process_Preorder(proc, root->right);
    }
}

void Tree_Process_Inorder(TreeNodeProc proc, TreeNode* root){
    if(root->left){
        Tree_Process_Inorder(proc, root->left);
    }
    (*proc)(root);
    if(root->right){
        Tree_Process_Inorder(proc, root->right);
    }
}

void Tree_Process_Postorder(TreeNodeProc proc, TreeNode* root){
    if(root->left){
        Tree_Process_Postorder(proc, root->left);
    }
    if(root->right){
        Tree_Process_Postorder(proc, root->right);
    }
    (*proc)(root);
}

int Tree_Get_Height(Tree* tree){
    if(!tree){
        return -1;
    }

    int maxheight = 0;
    Tree_Get_Height_Recursive(tree->root, 1, &maxheight);

    return maxheight;
}

void Tree_Get_Height_Recursive(TreeNode* root, int currentlevel, int* maxheight){
    if(!root){
        return;
    }
    if(currentlevel > *maxheight){
        *maxheight = currentlevel;
    }
    Tree_Get_Height_Recursive(root->left, currentlevel + 1, maxheight);
    Tree_Get_Height_Recursive(root->right, currentlevel + 1, maxheight);
}

unsigned int findMax(int* widtharray, unsigned int length){
    int maxvalue = 0;
    for(unsigned int i = 0; i < length; i++){
        if (widtharray[i] > maxvalue){
            maxvalue = widtharray[i];
        }
    }
    return maxvalue;
}

int Tree_Get_Width(Tree* tree){
    if(!tree){
        return -1;
    }
    int widtharray[255] = {0};
    Tree_Get_Width_Recursive(tree->root, 0, widtharray);

    return findMax(widtharray, 255);
}

void Tree_Get_Width_Recursive(TreeNode* root, int currentlevel, int* widtharray){
    if(!root){
        return;
    }
    widtharray[currentlevel] ++;
    Tree_Get_Width_Recursive(root->left, currentlevel+1, widtharray);
    Tree_Get_Width_Recursive(root->right, currentlevel+1, widtharray);
}