Untitled

mail@pastecode.io avatar
unknown
plain_text
3 months ago
5.0 kB
3
Indexable
Never
#include <stdio.h>
#include <math.h>

struct BinarySerchTreeNode{
    int data;
    struct BinarySerchTreeNode* left; //left child
    struct BinarySerchTreeNode* right; //right child
};


struct BinarySerchTreeNode* singleRotation(struct BinarySerchTreeNode* node){
    struct BinarySerchTreeNode* node2 = node->right;

    node2->left = node;
    node->right = NULL;

    return node2;
}

struct BinarySerchTreeNode* singleRotation1(struct BinarySerchTreeNode* node, struct BinarySerchTreeNode* parent){
    struct BinarySerchTreeNode* node2 = node->right;

    node2->left = node;
    node->right = NULL;

    if(parent != NULL){
        parent->right = node2;
    }

    return node2;
}

int heightDifference(struct BinarySerchTreeNode* node){
    // 2 0 = 2-0 = 2
    // 1 1 = 1-1 = 0
    // 1 2 = 2-1 = 1

    int leftHeight = height(node->left);
    int rightHeight = height(node->right);

    int heightDifference1 = leftHeight - rightHeight;
    return abs(heightDifference1);


/*
    if(leftHeight > rightHeight){
        return leftHeight - rightHeight;
    } else {
        return rightHeight - leftHeight;
    }
*/
}

int height(struct BinarySerchTreeNode* node){
    if(node == NULL) return -1;

    //printf("we are calculating the height of %d\n", node->data);

    //if(node->left == NULL && node->right ==NULL) {
    //    height  = 0;
    //}

    int leftHeight = height(node->left); //2
    int rightHeight = height(node->right); //1

    int height = findMax(leftHeight, rightHeight);

    //printf("calculation of height for node %d is completed\n ", node->data);
    return height+1;

};

int findMax(int a, int b){
    if(a > b){
        return a;
    } else {
        return b;
    }
}

struct BinarySerchTreeNode* addData(int data){
    struct BinarySerchTreeNode* node =  malloc(sizeof(struct BinarySerchTreeNode));
    node->data = data;
    node->left = NULL;
    node->right = NULL;

    return node;
};

struct BinarySerchTreeNode* insertN(int data, struct BinarySerchTreeNode* node){
    if(node == NULL){
        node = addData(data);
    }
    else if(data < node->data){
        node->left = insertN(data,node->left);

    }
    else if(data > node->data){
        node->right = insertN(data,node->right);


    }
    return node;

}

struct BinarySerchTreeNode* makeTree(){
    struct BinarySerchTreeNode* root = insertN(6, NULL);
    insertN(2, root);
    insertN(8, root);
    insertN(1, root);
    insertN(4, root);
    insertN(3, root);

    return root;
}

struct BinarySerchTreeNode* findMin(struct BinarySerchTreeNode* node){
    if(node == NULL){
        return NULL;
    }
    else if(node->left == NULL){
        return (node);
    }
    else {
        return(findMin(node->left));
    }
}

struct BinarySerchTreeNode* deleteN(int data, struct BinarySerchTreeNode* node){
    struct BinarySerchTreeNode* deleteStore;
    struct BinarySerchTreeNode* child;
    if(node == NULL){

    }
    else if(data < node->data){
        printf("%d -> ", node->data);
        node->left = deleteN(data,node->left);

    }
    else if(data > node->data){
        printf("%d -> ", node->data);
        node->right = deleteN(data,node->right);
    }
    else if(node->left != NULL && node->right != NULL){
        printf("reached node %d ->", node->data);
        printf("finding the minimum node in right sub tree -> ");
        deleteStore = findMin(node->right);
        printf(" replacing %d with %d -> ", node->data, deleteStore->data);
        node->data = deleteStore->data;
        node->right = deleteN(node->data,node->right);

    }
    else{
        deleteStore = node;
        if(node->left == NULL){
            child = node->right;
        }
        else if(node->right == NULL){
            child = node->left;
        }
        printf(" deleting %d", node->data);

        free(deleteStore);

        return child;
    }
    return node;
}

void inOrderTraversal(struct BinarySerchTreeNode* node){
    if(node == NULL) return;

    inOrderTraversal(node->left);
    printf("%d ", node->data);
    inOrderTraversal(node->right);
}

int main(){
    struct BinarySerchTreeNode* root = insertN(1, NULL);
    insertN(2, root);
    insertN(3, root);

    root = singleRotation1(root, NULL);
    struct BinarySerchTreeNode* node2 = root;

    struct BinarySerchTreeNode* node3 = root->right;
    insertN(4, root);
    struct BinarySerchTreeNode* node4 = node3->right;
    insertN(5, root);
    struct BinarySerchTreeNode* node5 = node4->right;

    int height5 = heightDifference(node5);
    int height4 = heightDifference(node4);
    int height3 = heightDifference(node3);


    printf("%d %d %d", height5,height4, height3);

    struct BinarySerchTreeNode* node = singleRotation1(node3, node2);
    printf("\n%d", node->data);



    return 0;
}




Leave a Comment