MUstar

IoT C++ 09/24 - Binary Search Tree Example (String)

Sep 24th, 2017
83
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<iostream>
  2. #include<cstdlib>
  3. #include<cstring>
  4. #define NULL __null
  5.  
  6. using namespace std;
  7.  
  8. typedef struct treenode {
  9.     string data;
  10.     struct treenode* left;
  11.     struct treenode* right;
  12. } treenode;
  13.  
  14. treenode* input(treenode* node, char* data)
  15. {
  16.     if(node == NULL){
  17.         treenode* word;
  18.         cout<<"[node] ";
  19.         word = new treenode[100];
  20.         word->data = data;
  21.         word->left = NULL;
  22.         word->right = NULL;
  23.         return word;
  24.     }
  25.     else if(node->data.compare(data) > 0){
  26.     //else if (data < node->data){
  27.         cout<<"[left] ";
  28.         node->left = input(node->left,data);
  29.     }
  30.     else if(node->data.compare(data) < 0){
  31.         cout<<"[right] ";
  32.         node->right = input(node->right,data);
  33.     }
  34.     else{
  35.         cout<<endl<<"ERROR>Already Reegistered";
  36.         return node;
  37.     }
  38. }
  39.  
  40. void preorder(treenode* node)
  41. {
  42.     cout<<node->data<<" ";
  43.     if (node->left) preorder(node->left);
  44.     if (node->right) preorder(node->right);
  45. }
  46.  
  47. void ctrorder(treenode* node)
  48. {
  49.     if (node->left) ctrorder(node->left);
  50.     cout<<node->data<<" ";
  51.     if (node->right) ctrorder(node->right);
  52. }
  53.  
  54. void lstorder(treenode* node)
  55. {
  56.     if (node->right) lstorder(node->right);
  57.     cout<<node->data<<" ";
  58.     if (node->left) lstorder(node->left);
  59.     /*
  60.     if (node->left) lstorder(node->left);
  61.     if (node->right) lstorder(node->right);
  62.     cout<<node->data<<" ";*/
  63. }
  64.  
  65. void search(treenode* node , char* data)
  66. {
  67.     if(node == NULL){
  68.         cout<<"ERROR>NOT FOUND!"<<endl;
  69.         return;
  70.     }
  71.     else if(data == node->data) {
  72.         cout<<"CENTRE WORD>"<<node->data<<endl;
  73.         cout<<"LEFT WORD>";
  74.         if(node->left!=NULL) cout<<node->left->data<<endl;
  75.         else cout<<"!None?"<<endl;
  76.         cout<<"RIGHT WORD>";
  77.         if(node->right!=NULL) cout<<node->right->data<<endl;
  78.         else cout<<"!None?"<<endl;
  79.         //return;
  80.     }
  81.     else if (data < node->data) {
  82.         search(node->left,data);
  83.     }
  84.     else if (data > node->data) {
  85.         search(node->right,data);
  86.     }
  87.     else {
  88.       cout<<"Error>SEARCH ERROR!"<<endl;
  89.     }
  90. }
  91. void delnum(treenode* node , char* data, char* key)
  92. {
  93.     if(node->data.compare(data) == 0) {
  94.         if(strcmp(data,key)==0){
  95.             cout<<"ERROR>NO! DEL 1STCTR WORD"<<endl;
  96.         }
  97.         else{
  98.             //node->data = "/0";
  99.             node->data = "";
  100.             if(node->left!=NULL) node->left = NULL;
  101.             if(node->right!=NULL) node->right = NULL;
  102.             if(node->data.empty())
  103.                 cout<<"Msg>DELETE OK!"<<endl;
  104.             else
  105.                 cout<<"Error>NUMDEL ERROR!"<<endl;
  106.         }
  107.     }
  108.     else if (node->data.empty()){
  109.         cout<<"Error>NOT FOUND!"<<endl;
  110.         return;
  111.     }
  112.     else if (node->data.compare(data) > 0) {
  113.         delnum(node->left,data,key);
  114.     }
  115.     else if (node->data.compare(data) < 0) {
  116.         delnum(node->right,data,key);
  117.     }
  118.     else {
  119.      cout<<"Error>NUMDEL ERROR!"<<endl;
  120.     }
  121. }
  122.  
  123.  
  124. int main(void)
  125. {
  126.     char word[100]; int select;
  127.     treenode* node;
  128.     node=NULL;
  129.     cout<<"1STCTR>"; cin>>word;
  130.     char key[100]; strcpy(key,word);
  131.     cout<<"Process>";
  132.     node = input(node,word);
  133.     //cout<<endl;
  134.     while(1)
  135.     {
  136.         cout<<endl<<"Input(OUT:-1)>"; cin>>word;
  137.         if(strcmp(word,"-1")==0) break;
  138.         cout<<"Process>";
  139.         input(node,word);
  140.     }
  141.     while(2)
  142.     {
  143.         cout<<"Menu> 1)ALLVIEW, 2)SELECT_VIEW, 3)ADDSTR, 4)DELETE, 5)EXIT"<<endl;
  144.         cout<<"Select>"; cin>>select;
  145.         if(cin.fail())
  146.         {
  147.             cout<<"ERROR>Invalid Select"<<endl;
  148.             //cout<<"Error>PLZ ENTER NUM! NOT CHAR!"<<endl;
  149.             cin.clear(); cin.ignore(256,'\n');
  150.         }
  151.         else if(select==5) break;
  152.         else{
  153.             cin.clear(); cin.ignore(256,'\n');
  154.             switch(select)
  155.             {
  156.                 case 1:
  157.                     cout<<"pre>"; preorder(node); cout<<endl;
  158.                     cout<<"ctr>"; ctrorder(node); cout<<endl;
  159.                     cout<<"lst>"; lstorder(node); cout<<endl;
  160.                     break;
  161.                 case 2:
  162.                     cout<<"Msg>ENTER U WANT VIEW WORD"<<endl;
  163.                     cout<<"Input>"; cin>>word;
  164.                     search(node , word); break;
  165.                 case 3:
  166.                     cout<<"Input>"; cin>>word;
  167.                     cout<<"Process>";
  168.                     input(node,word); cout<<endl; break;
  169.                 case 4:
  170.                     cout<<"Msg>ENTER U WANT DEL WORD"<<endl;
  171.                     cout<<"Input>"; cin>>word;
  172.                     delnum(node , word, key); break;
  173.                 default:
  174.                     cout<<"ERROR>Invalid Select"<<endl;
  175.                     break;
  176.             }
  177.         }
  178.         cout<<endl;
  179.     }
  180.     delete[] node; node=NULL;
  181.     cout<<"byebye"<<endl;
  182.     return 0;
  183. }
RAW Paste Data