In this assignment you are asked to implement a variety of functions that operat

Question

In this assignment you are asked to implement a variety of functions that operate on binary trees (the binary tree implementation from the book). You will be asked to test these functions on the following two trees (element data type is int):

For parts a through g, implement the given function and demonstrate the function working with the two trees provided earlier in this document:

a) (1 point) int count_leaves(BiTree *tree); Returns the number of leaf nodes in the tree.

b) (1 point) int count_non_leaves(BiTree *tree); Returns the number of non-leaf nodes in the tree.

c) (1 points) int get_height(BiTree *tree); Returns the height of the tree.

d) (1 point) void print_pre_order(BiTree *tree, void (*print)(const void *data))

Prints the elements of the tree to stdout using a pre-order traversal. The print parameter should contain the logic to print the data held in each node in the tree.

e) (1 point) void print_in_order(BiTree *tree, void (*print)(const void *data))

Prints the elements of the tree to stdout using an in-order traversal. The print parameter should contain the logic to print the data held in each node in the tree.

f) (1 point) void print_post_order(BiTree *tree, void (*print)(const void *data))

Prints the elements of the tree to stdout using a post-order traversal. The print parameter should contain the logic to print the data held in each node in the tree.

g) (3 points) void remove_leaves(BiTree *tree) Removes all leaf nodes from the tree.

Use print_pre_order, print_in_order, or print_post_order after calling remove_leaves to show that remove_leaves successfully removed all leaves.

Explanation / Answer

#include <stdio.h>
#include <stdlib.h>
#include<iostream>
using namespace std;
typedef struct node BiTree;
struct node
{
int data;
struct node* left;
struct node* right;
};

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);
}
void printvalue(const int value)
{
cout<<value<<" ";

}

int count_leaves(BiTree* tree)
{
if(tree == NULL)   
return 0;
if(tree->left == NULL && tree->right==NULL)
return 1;
else
return count_leaves(tree->left)+
count_leaves(tree->right);
}

void print_pre_order(BiTree* tree, void (*print)(const int data))
{
if (tree == NULL)
return;

//first print data of tree
(*print)(tree->data);

//then recur on left sutree
print_pre_order(tree->left, print);

//now recur on right subtree
print_pre_order(tree->right, print);
}
  
void print_in_order(BiTree* tree, void (*print)(const int data))
{
   if (tree == NULL)
return;

//first recur on left child
print_in_order(tree->left, print);

//then print the data of tree
(*print)(tree->data);

//now recur on right child
print_in_order(tree->right, print);

}

void print_post_order(BiTree* tree, void (*print)(const int data))
{
if (tree == NULL)
return;

// first recur on left subtree
print_post_order(tree->left, print);

// then recur on right subtree
print_post_order(tree->right, print);

// now deal with the tree
(*print)(tree->data);
}
  

int count_non_leaves(BiTree* tree)
{
   if(tree == NULL || (tree->left==NULL && tree->right==NULL)) //to work for empty tree
       return 0;
   return 1 + count_non_leaves(tree->left) + count_non_leaves(tree->right);
}

int get_height(BiTree* tree)
{
if (tree==NULL)
return 0;
else
{
/* compute the depth of each subtree */
int lDepth = get_height(tree->left);
int rDepth = get_height(tree->right);

/* use the larger one */
if (lDepth > rDepth)
return(lDepth+1);
else return(rDepth+1);
}
}

void remove_leaves(BiTree* p)
{
if(p != NULL)
{   
if(p->left) remove_leaves(p->left);
if(p->right) remove_leaves(p->right);
delete p;
}
else return;
}
//Driver program to test above functions
int main()
{
void (*print)(const int) = &printvalue;
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);

  
   int leaf = count_leaves(root);
cout<<"no of leaves:"<<leaf<<endl;
int c_non = count_non_leaves(root);
cout<<"no of non leaves:"<<c_non<<endl;
int height = get_height(root);
cout<<"height:"<<height<<endl;

cout<<"Preorder traversal of binary tree is:";
print_pre_order(root,print);
cout<<endl;

cout<<"Inorder traversal of binary tree is:";
print_in_order(root,print);
cout<<endl;
cout<<"Postorder traversal of binary tree is:";
print_post_order(root,print);
cout<<endl;
remove_leaves(root);
  
getchar();
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects