A binary tree can be used to sort n elements of an array data. First, create a c

Question

A binary tree can be used to sort n elements of an array data. First, create a complete binary tree, a tree with all leaves at one level, whose height h = ?lg n? + 1, and store all elements of the array in the first n leaves. In each empty leaf, store an element E greater than any element in the array. Figure 6.72a shows an example for data = {8, 20, 41, 7, 2}, h = ?lg(5)? + 1 = 4, and E = 42. Then, starting from the bottom of the tree, assign to each node the minimum of its two children values, as in Figure 6.72b, so that the smallest element emin in the tree is assigned to the root. Next, until the element E is assigned to the root, execute a loop that in each iteration stores E in the leaf, with the value of emin, and that, also starting from the bottom, assigns to each node the minimum of its two children. Figure 6.72c displays this tree after one iteration of the loop.

Explanation / Answer

#include<stdio.h>
#include<stdlib.h>
#define bool int

/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};

/* Returns the height of a binary tree */
int height(struct node* node);

/* Returns true if binary tree with root as root is height-balanced */
bool isBalanced(struct node *root)
{
int lh; /* for height of left subtree */
int rh; /* for height of right subtree */

/* If tree is empty then return true */
if(root == NULL)
return 1;

/* Get the height of left and right sub trees */
lh = height(root->left);
rh = height(root->right);

if( abs(lh-rh) <= 1 &&
isBalanced(root->left) &&
isBalanced(root->right))
return 1;

/* If we reach here then tree is not height-balanced */
return 0;
}

/* UTILITY FUNCTIONS TO TEST isBalanced() FUNCTION */

/* returns maximum of two integers */
int max(int a, int b)
{
return (a >= b)? a: b;
}

/* The function Compute the "height" of a tree. Height is the
number of nodes along the longest path from the root node
down to the farthest leaf node.*/
int height(struct node* node)
{
/* base case tree is empty */
if(node == NULL)
return 0;

/* If tree is not empty then height = 1 + max of left
height and right heights */
return 1 + max(height(node->left), height(node->right));
}

/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}

int main()
{
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->left->left->left = newNode(8);

if(isBalanced(root))
printf("Tree is balanced");
else
printf("Tree is not balanced");

getchar();
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.