Question

Write a program in C language that implements the logic of Binary Trees with the following requirements:

1- Elements of the tree should be read from the user.

2- Keep the binary tree heigh-balanced that is the absloute value of ((hight of left sub-tree) - ( height of right sub-tree)) should not be greater than 1. If so, then the binary tree is no longer balanced.

Hint: The best approach is to maintain balance during insertion.

*Remember, we are talking about baisc binary trees not binary search trees. ONLY CODE IN C LANGUAGE IS ACCEPTED.

Answer 1

The complete code is provided below:

Screenshot of the code:

Sample Output:

Code To Copy:

//Include the header files.

#include <stdio.h>

#include<stdlib.h>

//Define the structure.

struct Tree_Node

{

    int key_value;

    struct Tree_Node *left_ptr;

    struct Tree_Node *right_ptr;

    int Tree_height;

};

//Define the function the compute

// the height of the tree.

int compute_height(struct Tree_Node *t_node)

{

    if (t_node == NULL)

        return 0;

    return t_node->Tree_height;

}

//Define the function to compute maximum.

int max(int a, int b)

{

    return (a > b)? a : b;

}

//Define a function that create a newnode.

struct Tree_Node* newNode(int key)

{

    struct Tree_Node* new_node = (struct Tree_Node*)

                        malloc(sizeof(struct Tree_Node));

    new_node->key_value   = key;

    new_node->left_ptr   = NULL;

    new_node->right_ptr = NULL;

    new_node->Tree_height = 1;

    return(new_node);

}

//Define the function used to rotate the tree at right.

struct Tree_Node *rightRotate(struct Tree_Node *y)

{

    struct Tree_Node *x = y->left_ptr;

    struct Tree_Node *T2 = x->right_ptr;

    // Perform rotation

    x->right_ptr = y;

    y->left_ptr = T2;

   

    y->Tree_height = max(compute_height(y->left_ptr), compute_height(y->right_ptr))+1;

    x->Tree_height = max(compute_height(x->left_ptr), compute_height(x->right_ptr))+1;

    return x;

}

//Define the function used to rotate the tree at left.

struct Tree_Node *leftRotate(struct Tree_Node *x)

{

    struct Tree_Node *y = x->right_ptr;

    struct Tree_Node *T2 = y->left_ptr;

    //Perform the rotation in the tree.

    y->left_ptr = x;

    x->right_ptr = T2;

    //Update the height of the tree.

    x->Tree_height = max(compute_height(x->left_ptr), compute_height(x->right_ptr))+1;

    y->Tree_height = max(compute_height(y->left_ptr), compute_height(y->right_ptr))+1;

    // Return new root

    return y;

}

// Get Balance factor of node N

int getBalance(struct Tree_Node *N)

{

    if (N == NULL)

        return 0;

    return compute_height(N->left_ptr) - compute_height(N->right_ptr);

}

//Define the function to insert the element in the tree.

struct Tree_Node* Insert_element(struct Tree_Node* t_node, int key)

{

   

    if (t_node == NULL)

        return(newNode(key));

    if (key < t_node->key_value)

        t_node->left_ptr = Insert_element(t_node->left_ptr, key);

    else if (key > t_node->key_value)

        t_node->right_ptr = Insert_element(t_node->right_ptr, key);

    else

        return t_node;

  

    t_node->Tree_height = 1 + max(compute_height(t_node->left_ptr),

                           compute_height(t_node->right_ptr));

  

    int balance = getBalance(t_node);

    if (balance > 1 && key < t_node->left_ptr->key_value)

        return rightRotate(t_node);

  

    if (balance < -1 && key > t_node->right_ptr->key_value)

        return leftRotate(t_node);

   

    if (balance > 1 && key > t_node->left_ptr->key_value)

    {

        t_node->left_ptr = leftRotate(t_node->left_ptr);

        return rightRotate(t_node);

    }

   

    if (balance < -1 && key < t_node->right_ptr->key_value)

    {

        t_node->right_ptr = rightRotate(t_node->right_ptr);

        return leftRotate(t_node);

    }

    return t_node;

}

//Define the preorder traversal.

void Preorder_traversal(struct Tree_Node *root)

{

    if(root != NULL)

    {

        printf("%d ", root->key_value);

        Preorder_traversal(root->left_ptr);

        Preorder_traversal(root->right_ptr);

    }

}

//Define the main function.

int main()

{

//Create a root node of the tree.

struct Tree_Node *root_node = NULL;

//Insert the elements.

root_node = Insert_element(root_node, 10);

root_node = Insert_element(root_node, 20);

root_node = Insert_element(root_node, 30);

root_node = Insert_element(root_node, 40);

root_node = Insert_element(root_node, 50);

root_node = Insert_element(root_node, 25);

printf("Preorder Traversal : ");

//Call the function of preorder.

Preorder_traversal(root_node);

//Return the value for the main function.

return 0;

}