Write a program that creates and traverses a binary search tree. This program ma

Question

Write a program that creates and traverses a binary search tree. This program may be written in C or C++.

The goal of this project is to write a program that reads the words the user types at the command prompt (using the 'int argc, char * argv[]) and store each unique letter in a Binary Search Tree. When a duplicate is encountered do not store the letter again and instead keep track of the count in the tree. Once the Binary Search tree has been created print out the tree both in in-order and reverse-order. Then print the highest and lowest letters in the (alphabetically) in the Binary Search Tree. Lastly by processing the tree print the total sum of the letters in the words. Example of

Example of running the program from the command line: tree-example.exe tulsa community college

The resulting output should be:

In Order: a,1 c, 2 ?,2 g, 1 1, 3 i,1 m, 2 n, 1 o, 2 s, 1 t, 2 u, 2 y, 1

Explanation / Answer

#include<iostream>

using namespace std;

#define Max 100000

struct node{

char l;

int count;

struct node *left,*right;

};

typedef struct node node;

void insertnode(node* &t, char c);

void inorder(node* t);

void reverseorder(node* t);

char lowest,highest;

//function for inserting a new node. The function accepts an alias pointer and a character

void insertnode(node* &t, char c) {

if(t == NULL){

node *n = new node;

n->l = c;

n->count = 1;

n->left = NULL;

n->right = NULL;

t = n;

}

else if(t->l == c)

(t->count)++;

else if(t->l < c)

insertnode(t->right,c);

else

insertnode(t->left,c);

}

//function for reverse order.Traversal: right root left

void reverseorder(node *t){

if(t==NULL)

return;

reverseorder(t->right);

cout<<t->l<<", "<<t->count<<endl;

lowest = t->l; // last node of reverse order traversal is the lowest letter. The value gets overwritten every time till the last node.

reverseorder(t->left);

}

//function for in order order.Traversal: left root right

void inorder(node *t){

if(t==NULL)

return;

inorder(t->left);

cout<<t->l<<", "<<t->count<<endl;

highest = t->l; //last node of in order traversal is the highest letter. The values gets overwritten every time till the last node

inorder(t->right);

}

int main(int argc, char* argv[]){

char letters[Max];//Max is a macro defined as 100000

int totalnumofletters=0;

//reading the command line argument and storing each letter in letter[] array.

for(int i=1;i<argc;i++){

int j=0;

while(argv[i][j])

letters[totalnumofletters++] = argv[i][j++];

}

node *head = NULL;

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

insertnode(head,letters[i]);

cout<<"In Order: ";

inorder(head);

cout<<endl;

cout<<"Reverse Order: ";

reverseorder(head);

cout<<endl;

cout<<"Total number of letter: "<<totalnumofletters<<endl;

cout<<"Lowest letter value: "<< lowest<<endl;

cout<<"Highest letter value: "<< highest<<endl;

return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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