Program 18TH in C++

PROBLEM STATEMENT :

calculate average of the values in a binary tree?

SOLUTION :

#include <cstdio>

#include <iostream.h>

#include <queue.h>

using namespace std;

class node

{

public:

int data;

node* left;

node* right;

};

//finding average by breadth first traversal

void traverse(node * root)

{

queue q;

q.push(root);

int current_count=1;

int next_count=0;

int tot=0;

int sum=0;

while(!q.empty())

{

node* p1 = q.front();

q.pop();

current_count--;

cout<<data<<" ";

//tot keeps the count of no of nodes popped

tot++;

//adding values of popped nodes

sum+=p1->data;

if(p1->left != NULL)

q.push(p1->left);

next_count++;

if(p1->right != NULL)

q.push(p1->right);

next_count++;

if(current_count == 0)

{

current_count=next_count;

next_count=0;

cout<<endl;

}

}

cout<<"\n\nAverage of the "<<tot<<" node values in the binary tree is : "<<sum/(float)tot;

}

int main()

{

node Node[10];

for(int i=0; i<10; i++)

{

Node[i].data=i*2;

Node[i].left=NULL;

Node[i].right=NULL;

}

Node[0].left = &Node[1];

Node[0].right= &Node[2];

Node[1].left = &Node[3];

Node[1].right= &Node[4];

Node[2].left = &Node[5];

Node[2].right= &Node[6];

Node[3].left = &Node[7];

Node[3].right= &Node[8];

Node[4].left = &Node[9];

traverse(Node);

}