Question

PLEASE implement all the empty methods in BTree.c (only four functions) in C.

#include 
#include

struct Node {
     int value;
     struct Node* leftChild;
     struct Node* rightChild;
};

struct bTree {
     struct Node * root;
};

//please implement all the four functions
struct bTree* newTree (int value) {
        return NULL
}

int add (struct bTree* root, int value) {
        return 1;   
}

//you need to use free() to release the memory when a node is removed
int removeNode (struct bTree* root, int value) {
        return 1;
}

int contain (struct bTree* root, int value) {
        return 1;
}



void printInorder(struct Node* node) 
{ 
    if (node == NULL) 
        return; 
  
    printInorder(node->leftChild); 
  

    printf("%d ", (node->value));
  

    printInorder(node->rightChild); 
}

int printTree (struct bTree* root) {
        printInorder(root->root);
        printf("\n");
}

int main () {
        struct bTree* root = newTree(72);
        add(root, 12);
        add(root, 52);
        add(root, 87);
        add(root, 18);
        add(root, 49);
        add(root, 43);
        add(root, 82);
        add(root, 34);
        add(root, 73);
        add(root, 21);

        printTree(root);

        if(contain(root, 73) == 1){
                printf("This tree contains 73\n");
        }else{
                printf("This tree doesn't contains 73\n");
        }
        
        if(contain(root, 22) == 1){
                printf("This tree contains 22\n");
        }else{
                printf("This tree doesn't contains 22\n");
        }

        removeNode(root, 18);
        printf("After delete 18\n");
        printTree(root);

        removeNode(root, 49);
        printf("After delete 49\n");
        printTree(root);
        return 0;
}

Answer 1

/******************************************************************************

Online C Compiler.
Code, Compile, Run and Debug C program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include<stdio.h>
#include<stdlib.h>

struct Node {
int value;
struct Node* leftChild;
struct Node* rightChild;
};

struct bTree {
struct Node * root;
};

struct Node * new_node(int value){
struct Node *node;
node = malloc(sizeof(struct Node));
node->value = value;
node->leftChild = NULL;
node->rightChild = NULL;
  
return node;
}

//please implement all the four functions
struct bTree* newTree (int value) {
struct bTree *p;
p = malloc(sizeof(struct bTree));
p->root = new_node(value);
/*p->root = malloc(sizeof(struct Node));
p->root->value = value;
p->root->leftChild = NULL;
p->root->rightChild = NULL;*/

return p;
}

struct Node* insert(struct Node *node, int x)
{
if(node==NULL)
return new_node(x);
else if(x > node->value) // x is greater. Should be inserted to right
node->rightChild = insert(node->rightChild, x);
else // x is smaller should be inserted to left
node->leftChild = insert(node->leftChild, x);
return node;
}

int add (struct bTree* root, int value) {
  
   insert(root->root, value);
   return 1;
}

struct Node* find_minimum(struct Node *root)
{
if(root == NULL)
return NULL;
else if(root->leftChild != NULL) // node with minimum value will have no left child
return find_minimum(root->leftChild); // left most element will be minimum
return root;
}

struct Node* delete(struct Node *root, int x)
{
//searching for the item to be deleted
if(root==NULL)
return NULL;
if (x > root->value)
root->rightChild = delete(root->rightChild, x);
else if(x<root->value)
root->leftChild = delete(root->leftChild, x);
else
{
//No Children
if(root->leftChild==NULL && root->rightChild==NULL)
{
free(root);
return NULL;
}

//One Child
else if(root->leftChild==NULL || root->rightChild==NULL)
{
struct Node *temp;
if(root->leftChild==NULL)
temp = root->rightChild;
else
temp = root->leftChild;
free(root);
return temp;
}

//Two Children
else
{
struct Node *temp = find_minimum(root->rightChild);
root->value = temp->value;
root->rightChild = delete(root->rightChild, temp->value);
}
}
return root;
}

//you need to use free() to release the memory when a node is removed
int removeNode (struct bTree* root, int value) {
       delete(root->root, value);
return 1;
}

struct Node *parent;
struct Node * search(struct Node *root, int data)
{
if(root == NULL) {
return 0;
} else if (root->value == data) {
return root;
} else if (data > root->value) {
parent = root;
search(root->rightChild, data);
} else (data < root->value) {
parent = root;
search(root->leftChild, data);
}
}

int contain (struct bTree* root, int value) {
  
struct Node *temp = search(root->root, value);
if(temp == NULL)
return 0;
else
return 1;
}

void printInorder(struct Node* node)
{
if (node == NULL)
return;
  
printInorder(node->leftChild);
  

printf("%d ", (node->value));
  

printInorder(node->rightChild);
}

int printTree (struct bTree* root) {
printInorder(root->root);
printf("\n");
}

int main () {
struct bTree* root = newTree(72);
add(root, 12);
add(root, 52);
add(root, 87);
add(root, 18);
add(root, 49);
add(root, 43);
add(root, 82);
add(root, 34);
add(root, 73);
add(root, 21);

printTree(root);

if(contain(root, 73) == 1){
printf("This tree contains 73\n");
}else{
printf("This tree doesn't contains 73\n");
}
  
if(contain(root, 22) == 1){
printf("This tree contains 22\n");
}else{
printf("This tree doesn't contains 22\n");
}

removeNode(root, 18);
printf("After delete 18\n");
printTree(root);

removeNode(root, 49);
printf("After delete 49\n");
printTree(root);
return 0;
}