PLS INCULDE SOURCE CODE WITH PROGRAMMING THANK YOU Binary Trees You are given a

Question

PLS INCULDE SOURCE CODE WITH PROGRAMMING THANK YOU

Binary Trees

You are given a file that contains data describing a binary tree whose nodes are strings. The file begins with an integer N, the number of nodes in the tree, on a line by itself. This first line is followed by N additional lines where each line specifies child information for a node in the tree. The line for a node X starts with X itself followed by a list of the children of X. Names of nodes are separated by whitespace. For example, the data set

5

Al Bob Carol

Bob DebbyElaine

Carol

Debby

Elaine

Represents a binary tree in which Al has two children named Bob and Carol; Bob has two children named Debby and Elaine; and Carol, Debby, and Elaine have no children. Write a C++ or Java program that reads in data from such a file that describes a binary tree then lists all the nodes in the tree by their distance from the root: first the root, then all the children of the root, then all nodes that are children of a child of the root, and so on. For example, the program with input above will output the nodes in any of the following orders:

Al - Bob - Carol - Debby - Elaine

Al - Carol - Bob - Elaine - Debby

Al - Bob - Carol - Debby - Elaine

Reference (Breadth-First Traversal): https://en.wikipedia.org/wiki/Breadth-first_search Key Features to Use: Binary Tree, Breadth-First Traversal, File I/O, Sorting & Searching

PLS INCULDE SOURCE CODE WITH PROGRAMMING THANK YOU

Explanation / Answer

#include<iostream.h> // Required header files

#include<conio.h>

#include<process.h>

#include<fstream>

using namespace std;

struct node{ // Node structure

node *left; // left child

node *right; // right child

string data;// data

} ;

class bt{ // binary tree class

node *root;

public:

bt(){

root=NULL; // initial condition

}

int isempty() { // if no tree

return(root==NULL);

}

void insert(string item); // declaring functions

void leordertrav();

void LevelOrder(struct node* root);

void printLevel(struct node* root, int level);

int height(struct node* node);

};

void bt::insert(string item){// function to insert values into a tree

node *p=new node;

node *parent;

p->data=item;

p->left=NULL;

p->right=NULL;

parent=NULL;

if(isempty())

root=p;

else{

node *ptr;

ptr=root;

while(ptr!=NULL){

parent=ptr;

if(item>ptr->data)

ptr=ptr->right;

else

ptr=ptr->left;

}

if(item<parent->data)

parent->left=p;

else

parent->right=p;

}

}

void bt::leordertrav(){

LevelOrder(root);

}

void bt::LevelOrder(struct node* root){ /* Function to print level order traversal of the tree*/

int h = height(root); // getting height of the tree in h

int i;

for (i=1; i<=h; i++) // printing data in every level

printLevel(root, i);

}

void bt::printLevel(struct node* root, int level){ /* Print nodes at a given level */

cout<<root->data;

if (root == NULL)

return;

if (level == 1)

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

else if (level > 1){

printLevel(root->left, level-1);

printLevel(root->right, level-1);

}

}

int bt::height(struct node* node){/* Compute the "height" of a tree -- the number of nodes along the longest path from the root node down to the farthest leaf node.*/

if (node==NULL)

return 0;

else{ /* compute the height of each subtree */

int lheight = height(node->left);

int rheight = height(node->right);

if (lheight > rheight) /* use the larger one */

return(lheight+1);

else return(rheight+1);

}

}

int main(){// main function

bt b;

int f;

ifstream fin;

fin.open("bt.txt");

string output;

if (fin.is_open()) {

while (!fin.eof()) {

fin >> output;

b.insert(output);

}

}

b.leordertrav();

fin.close();

cin>>f;

return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

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