Write the program in c++ in three different files. A. Header file(.h) B. Impleme
ID: 3606989 • Letter: W
Question
Write the program in c++ in three different files. A. Header file(.h) B. Implementation file(.cpp) Problem An a-b tree is a binary tree in which each node can contain elther one key or two keys. The children in a node's left subtree are all less than or equal to the largest key at the node. In the followlng example, the keys are all single characters The root node contains 2 keys, d and g. It has a left child that contains a single node, c. The right child is a node with 2 keys, s and v. That node has two chidren, the left child has keys u and the right child, the key w. Inserting into an a-b tree is like inserting into a binary search tree, except when you come to a node containing only one key, you simply add the new key to the node containing one key. The node then contains two keys. For example, b would be added to the node containing c More interestingly, consider what happens when an is added to the tree. At the root, we go left (since f is less than or equal to the larger of the keys at the root), and then to the right of eb (since f is larger than the larger of the keys in the node). And so on. Input: Five strings. Each string will be less than 50 characters long and will contains the letters A through Z. Each letter is a key to be added to an initially empty ab tree. Output: For each input string, print the tree using in in-order. That is, print a node's left subtree, then the node, and then the node's right subtree. Within a node with 2 keys, the keys are listed in the order in which they were added to the node. The in-order listing of the tree above (after b and f are added) is: cbfdgunsvw. Sample Input: Line #1: INDIA Line #2: CANADA Line #3: PORTUGAL Line #4: SWITZERLAND Line 5: UNITEDKINGDOM Sample Output: Output #1: A D 1 1 N Output #2: A A C A N D Output 3: G A L P O R T U Output #4: D L A N E R I Tswz Output #5: D E D G K INNOITUNExplanation / Answer
Program Of Binary tree to find In order traversal of the tree in C++
#include<iostream>
#include<conio.h>
using namespace std;
class tree
{
int data;
tree *lchild;
tree *rchild;
public:
tree()
{
lchild=NULL;
rchild=NULL;
}
void build(tree *ptr,int key)
{
char choice;
int value;
if(ptr)
{
ptr->data=key;
ptr->lchild=ptr->rchild=NULL;
}
cout<<" Do you want Left Child Node (Y/N) := ";
cin>>choice;
if(choice=='y')
{
ptr->lchild=new tree;
cout<<" Enter Data:= ";
cin>>value;
build(ptr->lchild,value);
}
choice='n';
cout<<" Do you want Right Child Node (Y/N) := ";
cin>>choice;
if(choice=='y')
{
ptr->rchild=new tree;
cout<<" Enter Data:= ";
cin>>value;
build(ptr->rchild,value);
}
}
tree *search(tree *root,int key)
{
tree *temp=NULL;
if(root->data==key)
temp=root;
else
{
if(root->lchild)
{
temp=search(root->lchild,key);
}
if(!temp)
{
if(root->rchild)
temp=search(root->rchild,key);
}
}
return temp;
}
void insert(tree *ptr,int val,int key)
{
char choice;
tree *temp=search(ptr,key);
if(temp==NULL)
{
cout<<" Can't insert Node";
}
else
{
cout<<" Insert at Left side or Right side (L/R) := ";
cin>>choice;
if(choice=='l')
{
if(temp->lchild!=NULL)
cout<<" Can not Insert";
else
{
temp->lchild=new tree;
temp->lchild->data=val;
//temp->lchild->lchild=NULL;
//temp->lchild->rchild=NULL;
cout<<" Inserted";
}
}
else if(choice=='r')
{
if(temp->rchild!=NULL)
cout<<" Cannot Insert";
else
{
temp->rchild=new tree;
temp->rchild->data=val;
// temp->rchild->lchild=NULL;
// temp->rchild->rchild=NULL;
cout<<" Inserted";
}
}
}
}
void inorder(tree *ptr)
{
if(ptr)
{
inorder(ptr->lchild);
cout<<ptr->data<<" -> ";
inorder(ptr->rchild);
}
}
void preorder(tree *ptr)
{
if(ptr)
{
cout<<ptr->data<<" -> ";
preorder(ptr->lchild);
preorder(ptr->rchild);
}
}
void postorder(tree *ptr)
{
if(ptr)
{
postorder(ptr->lchild);
postorder(ptr->rchild);
cout<<ptr->data<<" -> ";
}
}
};
void main()
{
tree s,*root;
root=new tree;
int data;
cout<<" Enter Data:= ";
cin>>data;
s.build(root,data);
do
{
cout<<" Binary Tree Operation";
cout<<" 1. Insert";
cout<<" 2. Display";
cout<<" 3. Exit";
cout<<" Enter Your Choice := ";
int ch;
cin>>ch;
switch(ch)
{
case 1:
cout<<" Enter Value to Insert := ";
int val;
cin>>val;
cout<<" Enter Key Value := ";
int key;
cin>>key;
s.insert(root,val,key);
_getch();
break;
case 2:
cout<<" Inorder := ";
s.inorder(root);
cout<<" Preorder := ";
s.preorder(root);
cout<<" Postorder := ";
s.postorder(root);
_getch();
break;
case 3:
exit(0);
default:
cout<<" Invalid Choice";
_getch();
break;
}
}while(1);
}
This above program will make the .cpp files
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.