Algoritmi lezione 33 - Alberi binari

#include <iostream>
#include <fstream>
#include <cstdlib>

using namespace std;

class Albero_Binario {

  struct Nodo {
    int chiave=0;
    string valore="";

    Nodo *sx = nullptr;
    Nodo *dx = nullptr;

    Nodo(int la_chiave, string il_valore)   {
      chiave=la_chiave;
      valore=il_valore;
    }
  };

public:
  Albero_Binario() {}

  void inserisci(int la_chiave, string il_valore){
    radice = inserisci_nodo(radice, la_chiave, il_valore);
  }

  Nodo* inserisci_nodo(Nodo *nodo, int la_chiave, string il_valore) {
    if (nodo==nullptr)
      return new Nodo(la_chiave, il_valore);
    else
      if (la_chiave < nodo->chiave) //scendi a sinistra
        nodo->sx = inserisci_nodo(nodo->sx, la_chiave, il_valore);
      else  //scendi a destra
        nodo->dx = inserisci_nodo(nodo->dx, la_chiave, il_valore);
    return nodo;
  }

  void stampa_pre_order() { pre_order(radice, "");}

  void pre_order(Nodo *nodo, string spaziatura)
  {
    if (nodo!=nullptr)
    {
       cout << spaziatura << nodo->chiave << ": " << nodo->valore<< endl;
       spaziatura += "   ";

       pre_order(nodo->sx, spaziatura);
       pre_order(nodo->dx, spaziatura);
    }
  }

  void stampa_post_order() { post_order(radice);}

  void post_order(Nodo *nodo)
  {
    if (nodo!=nullptr)
    {
       post_order(nodo->sx);
       post_order(nodo->dx);

       cout << nodo->chiave << ": " << nodo->valore<< endl;
    }
  }

  void stampa_in_order() { in_order(radice);}

  void in_order(Nodo *nodo)
  {
    if (nodo!=nullptr)
    {
       in_order(nodo->dx);
       cout << nodo->chiave << ": " << nodo->valore<< endl;
       in_order(nodo->sx);
    }
  }

  string cerca(int chiave_ricerca) { return cerca_nodo(radice, chiave_ricerca); }

  string cerca_nodo(Nodo *nodo, int chiave_ricerca)
  {

    if (nodo!=nullptr)
      if (chiave_ricerca == nodo->chiave)
        return nodo->valore;
      else
        if (chiave_ricerca < nodo->chiave)
          return cerca_nodo(nodo->sx, chiave_ricerca);
        else
          return cerca_nodo(nodo->dx, chiave_ricerca);
    else
      return "";
  }

  Nodo *radice = nullptr;
private:

};

int main()
{
    Albero_Binario b;
    b.inserisci(100,"Londra");
    b.inserisci(45,"Milano");
    b.inserisci(20,"New Deli");
    b.inserisci(48,"Algeri");
    b.inserisci(200,"Pechino");
    b.inserisci(150,"Accra");
    b.inserisci(220,"Brasilia");

    b.stampa_in_order();




    return 0;
}