Write a C++ program (in UNIX) for traversing a Binary Search Tree in following w
ID: 669644 • Letter: W
Question
Write a C++ program (in UNIX) for traversing a Binary Search Tree in following ways: (use Linked List by Class) ---------- 20 points i) Breadth First Traversal: Top-down, Left-to-right ii) Breadth First Traversal: Top-down, Right-to-Left iii) Breadth First Traversal: Bottom-up, Left-to-right iv) Breadth First Traversal: Bottom-up, Right-to-left v) Depth First Traversal: Inorder, LVR vi) Depth First Traversal: Inorder, RVL vii) Depth First Traversal: Preorder, VLR viii) Depth First Traversal: Preorder, VRL ix) Depth First Traversal: Postorder, LRV x) Depth First Traversal: Postorder, RLV No Choice menu required. Draw 10 NS charts outlining the traversals. Sample Input (taken from keyboard, single line separated nodes shown in BFS: top-down, left to right traversal): 20 10 30 5 15 25 40 2 8 Sample Output (in console or in a file): Breadth First Traversal: Top-down, Left-to-right -> 20 10 30 5 15 25 40 2 8 Breadth First Traversal: Top-down, Right-to-Left -> 20 30 10 40 25 15 5 8 2 Breadth First Traversal: Bottom-up, Left-to-right -> 2 8 5 15 25 40 10 30 20 Breadth First Traversal: Bottom-up, Right-to-left -> 8 2 40 25 15 5 30 10 20 Depth First Traversal: Inorder, LVR -> 2 5 8 10 15 20 25 30 40 Depth First Traversal: Inorder, RVL -> 40 30 25 20 15 10 8 5 2 Depth First Traversal: Preorder, VLR -> 20 10 5 2 8 15 30 25 40 Depth First Traversal: Preorder, VRL -> 20 30 40 25 10 15 5 8 2 Depth First Traversal: Postorder, LRV -> 2 8 5 15 10 25 40 30 20 Depth First Traversal: Postorder, RLV -> 40 25 30 15 8 2 5 10 20 Write a C++ program (in UNIX) for traversing a Binary Search Tree in following ways: (use Linked List by Class) ---------- 20 points i) Breadth First Traversal: Top-down, Left-to-right ii) Breadth First Traversal: Top-down, Right-to-Left iii) Breadth First Traversal: Bottom-up, Left-to-right iv) Breadth First Traversal: Bottom-up, Right-to-left v) Depth First Traversal: Inorder, LVR vi) Depth First Traversal: Inorder, RVL vii) Depth First Traversal: Preorder, VLR viii) Depth First Traversal: Preorder, VRL ix) Depth First Traversal: Postorder, LRV x) Depth First Traversal: Postorder, RLV No Choice menu required. Draw 10 NS charts outlining the traversals. Sample Input (taken from keyboard, single line separated nodes shown in BFS: top-down, left to right traversal): 20 10 30 5 15 25 40 2 8 Sample Output (in console or in a file): Breadth First Traversal: Top-down, Left-to-right -> 20 10 30 5 15 25 40 2 8 Breadth First Traversal: Top-down, Right-to-Left -> 20 30 10 40 25 15 5 8 2 Breadth First Traversal: Bottom-up, Left-to-right -> 2 8 5 15 25 40 10 30 20 Breadth First Traversal: Bottom-up, Right-to-left -> 8 2 40 25 15 5 30 10 20 Depth First Traversal: Inorder, LVR -> 2 5 8 10 15 20 25 30 40 Depth First Traversal: Inorder, RVL -> 40 30 25 20 15 10 8 5 2 Depth First Traversal: Preorder, VLR -> 20 10 5 2 8 15 30 25 40 Depth First Traversal: Preorder, VRL -> 20 30 40 25 10 15 5 8 2 Depth First Traversal: Postorder, LRV -> 2 8 5 15 10 25 40 30 20 Depth First Traversal: Postorder, RLV -> 40 25 30 15 8 2 5 10 20 Write a C++ program (in UNIX) for traversing a Binary Search Tree in following ways: (use Linked List by Class) ---------- 20 points i) Breadth First Traversal: Top-down, Left-to-right ii) Breadth First Traversal: Top-down, Right-to-Left iii) Breadth First Traversal: Bottom-up, Left-to-right iv) Breadth First Traversal: Bottom-up, Right-to-left v) Depth First Traversal: Inorder, LVR vi) Depth First Traversal: Inorder, RVL vii) Depth First Traversal: Preorder, VLR viii) Depth First Traversal: Preorder, VRL ix) Depth First Traversal: Postorder, LRV x) Depth First Traversal: Postorder, RLV No Choice menu required. Draw 10 NS charts outlining the traversals. Sample Input (taken from keyboard, single line separated nodes shown in BFS: top-down, left to right traversal): 20 10 30 5 15 25 40 2 8 Sample Output (in console or in a file): Breadth First Traversal: Top-down, Left-to-right -> 20 10 30 5 15 25 40 2 8 Breadth First Traversal: Top-down, Right-to-Left -> 20 30 10 40 25 15 5 8 2 Breadth First Traversal: Bottom-up, Left-to-right -> 2 8 5 15 25 40 10 30 20 Breadth First Traversal: Bottom-up, Right-to-left -> 8 2 40 25 15 5 30 10 20 Depth First Traversal: Inorder, LVR -> 2 5 8 10 15 20 25 30 40 Depth First Traversal: Inorder, RVL -> 40 30 25 20 15 10 8 5 2 Depth First Traversal: Preorder, VLR -> 20 10 5 2 8 15 30 25 40 Depth First Traversal: Preorder, VRL -> 20 30 40 25 10 15 5 8 2 Depth First Traversal: Postorder, LRV -> 2 8 5 15 10 25 40 30 20 Depth First Traversal: Postorder, RLV -> 40 25 30 15 8 2 5 10 20Explanation / Answer
vi bst.cc
#include<iostream.h>
#include<conio.h>
#include<process.h>
struct tree_node
{
tree_node *left;
tree_node *right;
int data;
} ;
class bst
{
tree_node *root;
public:
bst()
{
root=NULL;
}
int isempty()
{
return(root==NULL);
}
void insert(int item);
void inordertrav();
void inorder(tree_node *);
void postordertrav();
void postorder(tree_node *);
void preordertrav();
void preorder(tree_node *);
};
void bst::insert(int item)
{
tree_node *p=new tree_node;
tree_node *parent;
p->data=item;
p->left=NULL;
p->right=NULL;
parent=NULL;
if(isempty())
root=p;
else
{
tree_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 bst::inordertrav()
{
inorder(root);
}
void bst::inorder(tree_node *ptr)
{
if(ptr!=NULL)
{
inorder(ptr->left);
cout<<" "<<ptr->data<<" ";
inorder(ptr->right);
}
}
void bst::postordertrav()
{
postorder(root);
}
void bst::postorder(tree_node *ptr)
{
if(ptr!=NULL)
{
postorder(ptr->left);
postorder(ptr->right);
cout<<" "<<ptr->data<<" ";
}
}
void bst::preordertrav()
{
preorder(root);
}
void bst::preorder(tree_node *ptr)
{
if(ptr!=NULL)
{
cout<<" "<<ptr->data<<" ";
preorder(ptr->left);
preorder(ptr->right);
}
}
void main()
{
bst b;
b.insert(20);
b.insert(10);
b.insert(30);
b.insert(5);
b.insert(15);
b.insert(25);
b.insert(40);
b.insert(2);
b.insert(8);
cout<<"inorder"<<endl;
b.inordertrav();
cout<<endl<<"postorder"<<endl;
b.postordertrav();
cout<<endl<<"preorder"<<endl;
b.preordertrav();
getch();
}
gcc bst.cc
./a.out
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.