void binaireboom::initextra_p(knoop *k) {
  if (k != NULL) {
    k->extra = 0;
    initextra_p(k->links);
    initextra_p(k->rechts);
  }//if
}//binaireboom::initextra_p

void binaireboom::vulextra_p(knoop *k, int niveau) {
  if (k != NULL) {
    k->extra = niveau + 1;
    vulextra_p(k->links, niveau + 1);
    vulextra_p(k->rechts, niveau + 1);
  }//if
}//binaireboom::vulextra_p

int binaireboom::aantalbladeren_p(knoop *k) {
  if (k == NULL)
    return 0;
  if ((k->links == NULL) && (k->rechts == NULL))
    return 1;
  return aantalbladeren_p(k->links) + aantalbladeren_p(k->rechts);
}//binaireboom::aantalbladeren_p

int binaireboom::hoogte_p(knoop *k) {
  if (k == NULL)
    return 0;
  return max(hoogte_p(k->links), hoogte_p(k->rechts)) + 1;
}//binaireboom::hoogte_p

char binaireboom::maxinfowaarde_p(knoop *k) {
  if (k == NULL)
    return '\0'; // De laagste waarde in de ascii tabel.
  return max(max(maxinfowaarde_p(k->links), maxinfowaarde_p(k->rechts)), k->info);
}//binaireboom::maxinfowaarde_p

void binaireboom::doepostorde_p(knoop *k) {
  if (k != NULL) {
    doepostorde_p(k->links);
    doepostorde_p(k->rechts);
    cout << k->info << ", " << k->extra << endl;
  }//if
}//binaireboom::doepostorde_p

// Zoek de grootste kleinere in een binaire zoekboom.
// 
// Argumenten: knoop *k  ; Pointer naar een knoop (mag geen NULL zijn).
//                   *&o ; Pointer naar de ouder van de grootste kleinere
//                         (moet bij aanroep NULL zijn).
//
// Retourneert: knoop * ; Pointer naar de grootste kleinere.
//
knoop *binaireboom::grootstekleinere(knoop *k, knoop *&o) {
  knoop *t = k;
  
  if (k->links == NULL)       // Er is geen grootste kleinere.
    return NULL;

  o = t;
  t = k->links;               // Een stap naar links.
  while (t->rechts != NULL) { // En dan zo ver mogelijk naar rechts.
    o = t;
    t = t->rechts;
  }//while

  return t;
}//binaireboom::grootstekleinere

// Zoek de kleinste grotere in een binaire zoekboom.
// 
// Argumenten: knoop *k  ; Pointer naar een knoop (mag geen NULL zijn).
//                   *&o ; Pointer naar de ouder van de kleinste grotere
//                         (moet bij aanroep NULL zijn).
//
// Retourneert: knoop * ; Pointer naar de kleinste grotere.
//
knoop *binaireboom::kleinstegrotere(knoop *k, knoop *&o) {
  knoop *t = k;
  
  if (k->rechts == NULL)     // Er is geen kleinste grotere.
    return NULL;

  o = t;
  t = k->rechts;             // Een stap naar rechts.
  while (t->links != NULL) { // En dan zo ver mogelijk naar links.
    o = t;
    t = t->links;
  }//while

  return t;
}//binaireboom::kleinstegrotere

// Controleer of een binaire boom een binaire zoekboom is.
//
// Argumenten: knoop *k ; Pointer naar een knoop (bij de 1e aanroep de wortel).
//
// Retourneert: bool ; TRUE als de boom met k als wortel een binaire zoekboom
//                     is, FALSE als dit niet zo is.
//
bool binaireboom::isbzboom_p(knoop *k) {
  knoop *gk,
        *kg,
        *o = NULL;

  if (k == NULL) // Een lege boom is een binaire zoekboom.
    return true;

  gk = grootstekleinere(k, o);
  if ((gk != NULL) && (gk->info >= k->info)) // De gk is te groot.
    return false;
  kg = kleinstegrotere(k, o);
  if ((kg != NULL) && (kg->info <= k->info)) // De kg is te klein.
    return false;

  if ((isbzboom_p(k->links)) && (isbzboom_p(k->rechts)))
    return true;

  return false;
}//binaireboom::isbzboom_p

// Zoek een waarde in een binaire zoekboom.
//
// Argumenten: char waarde ; De gezochte waarde.
//             knoop *&o   ; Pointer naar de ouder van de knoop die de waarde
//                           bevat (moet bij aanroep NULL zijn).
//
// Retourneert: knoop * ; Een pointer naar de knoop die de waarde bevat indien
//                        aanwezig. NULL als de waarde niet in de boom zit.
//
// Notitie: Als zowel de geretourneerde pointer als de o pointer NULL zijn,
//          dan is de boom leeg.
//
knoop *binaireboom::bzoek_p(char waarde, knoop *&o) {
  knoop *t = wortel;

  while ((t != NULL) && (t->info != waarde)) {
    o = t;
    if (t->info < waarde)
      t = t->rechts;
    else
      t = t->links;
  }//while
  return t;
}//bzoek_p

// Voeg een waarde toe aan een binaire zoekboom.
//
// Argumenten: char waarde ; De toe te voegen waarde.
//
// Globale veranderingen: De wortel of een van de subbomen kan veranderen.
//
void binaireboom::bzvoegtoe_p(char waarde) {
  knoop *o = NULL,
        *k = bzoek_p(waarde, o);

  if (k == NULL) {   // De waarde was niet gevonden.
    if (o != NULL) { // De boom is niet leeg.
      if (waarde < o->info) {
        o->links = maakknoop();
        o->links->info = waarde;
      }//if
      else {
        o->rechts = maakknoop();
        o->rechts->info = waarde;
      }//else
    }//if
    else {           // De boom is leeg.
      wortel = maakknoop();
      wortel->info = waarde;
    }//else
  }//if
}//binaireboom::bzvoegtoe_p

// Verwijder een waarde uit een binaire zoekboom.
//
// Argumenten: char waarde ; De te verwijderen waarde.
//
// Globale veranderingen: De wortel of een van de subbomen kan veranderen.
//
void binaireboom::bzverwijder_p(char waarde) {
  knoop *t,
        *o,
        *k = bzoek_p(waarde, o);

  if (k != NULL) {
    if ((k->links != NULL) || (k->rechts != NULL)) {   // Interne knoop.
      if ((k->rechts != NULL) && (k->links != NULL)) { // En ook 2 kinderen.
        t = kleinstegrotere(k, o);
        k->info = t->info;
        k = t;
      }//if
      // Vanaf dit punt is er nog maar 1 kind.
      if (k != wortel) {
        if (k->rechts != NULL) {
          if (o->links == k)
            o->links = k->rechts;
          else // (o->rechts == k)
            o->rechts = k->rechts;
        }//if
        else { // (k->links != NULL)
          if (o->links == k)
            o->links = k->links;
          else // (o->rechts == k)
            o->rechts = k->links;
        }//else
      }//if
      else {
        if (k->rechts != NULL)
          wortel = wortel->rechts;
        else // (k->links != NULL)
          wortel = wortel->links;
      }//else
    }//if
    else { // ((k->links == NULL) && (k->rechts == NULL))
      if (k != wortel) {
        if (o->links == k)
          o->links = NULL;
        else // (o->rechts == k)
          o->rechts = NULL;
      }//if
      else 
        wortel = NULL;
    }//else
    delete k;
  }//if
}//binaireboom::bzverwijder_p