StringSearchTree.cpp

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

class Node {
    /*
    Táknar hnút í tvíleitartré sem inniheldur strengi
    */
   public:
    string data;
    Node* left;
    Node* right;

    Node(string data) {
        /*
        Býr til nýjan barnlausan hnút sem inniheldur strenginn <data>
        */
        this->data = data;
        this->left = nullptr;
        this->right = nullptr;
    }

    ~Node() {
        /*
        Passar endurkvæmt upp á að engin börn séu skilin eftir í reiðileysi
        */
        delete this->left;
        delete this->right;
    }
};

class StringSearchTree {
    /*
    Táknar tvíleitartré sem inniheldur strengi.
    Samanburðir fara fram á strengjunum sjálfum.
    Einu aðgerðirnar sem eru studdar eru innsetning (put) og uppfletting (contains)
    */
   public:
    StringSearchTree() {
        /*
        Upphafsstillir tómt (hnútalaust) tvíleitartré.
        */
        this->root = nullptr;
    };

    ~StringSearchTree() {
        /*
        Eyðingu úthlutað til klasans Node.
         */
        delete this->root;
    }

    void put(string data) {
        /*
        Býr til hnút utan um strenginn <data> og setur hann á réttan stað í tvíleitartréð.
        Sé hnútur með sömu gögn þegar í trénu er þeim ekki bætt við aftur.
        Strengurinn <data> þarf að vera skilgreindur, ekki þarf að meðhöndla nullptr.
        */

      if (contains(data)) return; // bætum ekki við ef strengurinn er nú þegar í trénu

      Node* n = new Node(data); // búum til hnút með strengnum
      Node* temp = this->root;
      int size = 0;

      if (temp == nullptr) { // ef tómt tré
          this->root = n;
          return;
      }

      if (n->data.compare(this->root->data) < 0) { // ef n á að koma á undan rót
          this->root->left = n;
          n->right = this->root;
          this->root = n;
          return;
      }

      while (temp != nullptr) { // stærð trés
          size++;
          temp = temp->right;
      }

      temp = this->root; // endurstillum
      Node* tempL = temp->left; // vinstri við temp

      for (int i=0; i<size; i++) {

         if (n->data.compare(temp->data) < 0) { // n á undan temp
             n->right = temp;
             n->left = temp->left;
             tempL->right = n;
             temp->left = n;
         }

         if (n->data.compare(temp->data) > 0) { // n á eftir temp
             if (i == size-1) { // þegar n fer út á enda
                 n->left = temp;
                 temp->right = n;
             }
             tempL = temp;
             temp = temp->right;
         }

      }

    }

    bool contains(string data) {

        Node* temp = this->root;

        while (temp != nullptr) {
            // skilum true ef data er þegar í trénu:
            if (data.compare(temp->data) == 0) return true;
            temp = temp->right;
        }

        // ef ekki skilum við false;
        return false;
    }

   private:
    Node* root;

    friend ostream& operator<<(std::ostream& os, StringSearchTree& tree);
};

ostream& operator<<(ostream& os, StringSearchTree& tree) {
    Node* temp = tree.root;
    while (temp != nullptr) {
        os << temp->data << " ";
        temp = temp->right;
    }
    return os;
};

int main() {
    /*
    Tvíleitartréð prófað með því að setja í það ávexti.
    */

    StringSearchTree tree;

    // Skilgreinum ávextina okkar
    vector<string> fruits = {"Ananas", "Banani", "Epli",    "Greip",          "Mandarína",
                             "Mangó",  "Melóna", "Sítróna", "Stjörnuávöxtur", "Súraldin"};
    // Innsetningin á að virka óháð innsetningarröð
    random_shuffle(fruits.begin(), fruits.end());
    cout << "Setjum ávexti í tréð í eftirfarandi röð:" << endl;
    for (string fruit : fruits) {
        cout << fruit << " ";
        tree.put(fruit);
    }
    cout << endl << endl;

    // Athugum hvort tréð innihaldi ávextina
    int missing = 0;
    for (string fruit : fruits) {
        if (!tree.contains(fruit)) {
            missing++;
        }
    }
    if (0 < missing) {
        cout << missing << " ávextir skiluðu sér ekki í tréð.";
    } else {
        cout << "Allir ávextirnir lentu í trénu." << endl;
    }
    if (tree.contains("Ferskja")) {
        cout << "Ferskja fannst í trénu sem ekki var sett þangað. Þetta er villa." << endl << endl;
    } else {
        cout << "Engin ferskja er í trénu, sem er eðlilegt." << endl << endl;
    }

    cout << "Skrifum út ávextina í trénu í réttri röð:" << endl;
    cout << tree << endl;
}