#include <iostream>
#include <string>
#include <sstream>
using namespace std;
struct node {
string key;
string letter;
struct node *left;
struct node *right;
};
struct tree{
struct node *root;
long size;
};
void insert_morse(string expr,string letter,struct node *&n){
if(expr.length()<1)
{
if(n==NULL){
n=new struct node;
n->left=NULL;
n->right=NULL;
}
n->letter=letter;
}
else
if(n!=NULL && n->letter=="START")
{
if(expr[0]=='.')
{
insert_morse(expr.substr(1,expr.length()),letter,n->left);
n->left->key=expr[0];
}
else{
insert_morse(expr.substr(1,expr.length()),letter,n->right);
n->right->key=expr[0];
}
}
else{
if(n==NULL){
n=new struct node;
n->left=NULL;
n->right=NULL;
}
if(expr[0]=='.')
{
insert_morse(expr.substr(1,expr.length()),letter,n->left);
n->left->key=expr[0];
}
else{
insert_morse(expr.substr(1,expr.length()),letter,n->right);
n->right->key=expr[0];
}
}
}
void explore(struct node *n){
if(n!=NULL){
cout<<n->letter<<endl;
explore(n->left);
explore(n->right);
}
}
string translate(string letter,struct node *n){
if(n==NULL){
return "STOP";
}
else
if(n->letter==letter){
return n->key;
}
else
{
string key=translate(letter,n->left);
if(key=="STOP")
key=translate(letter,n->right);
if(key=="STOP")
return "STOP";
else
return ((n->key!="|")?n->key:"")+key;
}
}
int main(){
struct tree t;
t.root=new struct node;
t.root->letter="START";
t.root->key="|";
t.root->left=NULL;
t.root->right=NULL;
insert_morse(".-","A",t.root);
insert_morse("-...","B",t.root);
insert_morse("-.-.","C",t.root);
insert_morse("-..","D",t.root);
insert_morse(".","E",t.root);
insert_morse("..-.","F",t.root);
insert_morse("--.","G",t.root);
insert_morse("....","H",t.root);
insert_morse("..","I",t.root);
insert_morse(".---","J",t.root);
insert_morse("-.-","K",t.root);
insert_morse(".-..","L",t.root);
insert_morse("--","M",t.root);
insert_morse("-.","N",t.root);
insert_morse("--.--","Ñ",t.root);
insert_morse("---","O",t.root);
insert_morse(".--.","P",t.root);
insert_morse("--.-","Q",t.root);
insert_morse(".-.","R",t.root);
insert_morse("...","S",t.root);
insert_morse("-","T",t.root);
insert_morse("..-","U",t.root);
insert_morse("...-","V",t.root);
insert_morse(".--","W",t.root);
insert_morse("-..-","X",t.root);
insert_morse("-.--","Y",t.root);
insert_morse("--..","Z",t.root);
insert_morse("----","CH",t.root);
explore(t.root);
cout<<"A:"<<translate("A",t.root)<<endl;
cout<<"B:"<<translate("B",t.root)<<endl;
cout<<"C:"<<translate("C",t.root)<<endl;
cout<<"D:"<<translate("D",t.root)<<endl;
cout<<"E:"<<translate("E",t.root)<<endl;
cout<<"F:"<<translate("F",t.root)<<endl;
cout<<"G:"<<translate("G",t.root)<<endl;
cout<<"H:"<<translate("H",t.root)<<endl;
cout<<"I:"<<translate("I",t.root)<<endl;
cout<<"J:"<<translate("J",t.root)<<endl;
cout<<"K:"<<translate("K",t.root)<<endl;
cout<<"L:"<<translate("L",t.root)<<endl;
cout<<"M:"<<translate("M",t.root)<<endl;
cout<<"N"<<translate("N",t.root);
cout<<"Ñ:"<<translate("Ñ",t.root)<<endl;
cout<<"O:"<<translate("O",t.root)<<endl;
cout<<"P:"<<translate("P",t.root)<<endl;
cout<<"Q:"<<translate("Q",t.root)<<endl;
cout<<"R:"<<translate("R",t.root)<<endl;
cout<<"S:"<<translate("S",t.root)<<endl;
cout<<"T:"<<translate("T",t.root)<<endl;
cout<<"U:"<<translate("U",t.root)<<endl;
cout<<"V:"<<translate("V",t.root)<<endl;
cout<<"W:"<<translate("W",t.root)<<endl;
cout<<"X:"<<translate("X",t.root)<<endl;
cout<<"Y:"<<translate("Y",t.root)<<endl;
cout<<"Z:"<<translate("Z",t.root)<<endl;
}
This implementation ilustrate how to build a binary tree that record morse code.
Be the first to comment
You can use [html][/html], [css][/css], [php][/php] and more to embed the code. Urls are automatically hyperlinked. Line breaks and paragraphs are automatically generated.