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

int binaireboom::hoogte_p(knoop *ingang) {
  if (ingang == nullptr)  // een boom bestaande uit 1 knoop heeft hoogte 0,
    return -1;         // dus een lege boom heeft hoogte -1
  return max(hoogte_p(ingang->links), hoogte_p(ingang->rechts)) + 1;
}//binaireboom::hoogte_p

void binaireboom::initniveau_p(knoop *ingang) {
  if (ingang != nullptr) {
    ingang->niveau = 0;
    initniveau_p(ingang->links);
    initniveau_p(ingang->rechts);
  }//if
}//binaireboom::initniveau_p

void binaireboom::vulniveau_p(knoop *ingang, int niveau) {
  if (ingang != nullptr) {
    ingang->niveau = niveau;
    vulniveau_p(ingang->links, niveau + 1);
    vulniveau_p(ingang->rechts, niveau + 1);
  }//if
}//binaireboom::vulniveau_p

char binaireboom::maxinfowaarde_p(knoop *ingang) {
  if (ingang == nullptr)
    return '\0'; // De laagste waarde in de ascii tabel, kan ook als "(char)(0)"
  return max(max(maxinfowaarde_p(ingang->links), maxinfowaarde_p(ingang->rechts)), ingang->info);
}//binaireboom::maxinfowaarde_p

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

// Zoek een waarde in een binaire zoekboom.
//
// Argumenten: char waarde   ; De gezochte waarde.
//             knoop *&ouder ; Pointer naar de ouder van de knoop die de waarde
//                             bevat (moet bij aanroep nullptr zijn).
//
// Retourneert: knoop * ; Een pointer naar de knoop die de waarde bevat indien
//                        aanwezig. nullptr als de waarde niet in de boom zit.
//
// Notitie: Als zowel de geretourneerde pointer als de ouder-pointer nullptr
//          zijn, dan is de boom leeg.
//
knoop *binaireboom::bzoek_p(char waarde, knoop *&ouder) {
  knoop *temp = wortel;
  while ((temp != nullptr) && (temp->info != waarde)) {
    ouder = temp;
    if (temp->info < waarde)
      temp = temp->rechts;
    else
      temp = temp->links;
  }//while
  return temp;
}//bzoek_p

// Zoek de grootste kleinere in een binaire zoekboom.
// Om precies te zijn: zoek binnen de subboom met wortel ingang
// naar de knoop met de grootste waarde kleiner dan de waarde van ingang.
// 
// Argumenten: knoop *ingang  ; Pointer naar een knoop (mag geen nullptr zijn).
//                   *&ouder  ; Pointer naar de ouder van de grootste kleinere
//                                (moet bij aanroep nullptr zijn).
//
// Retourneert: knoop * ; Pointer naar de grootste kleinere, als deze 
//                          bestaat binnen de subboom met wortel ingang
//              nullptr ; als er geen grootste kleinere bestaat binnen
//                          de subboom met wortel ingang
//
knoop *binaireboom::grootstekleinere(knoop *ingang, knoop *&ouder) {
  knoop *temp = ingang; 
  if (ingang->links == nullptr)       // Er is geen grootste kleinere.
    return nullptr;
  ouder = temp;
  temp = ingang->links;            // Een stap naar links.
  while (temp->rechts != nullptr) {// En dan zo ver mogelijk naar rechts.
    ouder = temp;
    temp = temp->rechts;
  }//while
  return temp;
}//binaireboom::grootstekleinere

// Zoek de kleinste grotere in een binaire zoekboom.
// Om precies te zijn: zoek binnen de subboom met wortel ingang
// naar de knoop met de kleinste waarde groter dan de waarde van ingang.
// 
// Argumenten: knoop *ingang  ; Pointer naar een knoop (mag geen nullptr zijn).
//                   *&ouder  ; Pointer naar de ouder van de kleinste grotere
//                                (moet bij aanroep nullptr zijn).
//
// Retourneert: knoop * ; Pointer naar de kleinste grotere, als deze 
//                          bestaat binnen de subboom met wortel ingang
//              nullptr ; als er geen kleinste grotere bestaat binnen
//                          de subboom met wortel ingang
//
knoop *binaireboom::kleinstegrotere(knoop *ingang, knoop *&ouder) {
  knoop *temp = ingang;
  if (ingang->rechts == nullptr)     // Er is geen kleinste grotere.
    return nullptr;
  ouder = temp;
  temp = ingang->rechts;           // Een stap naar rechts.
  while (temp->links != nullptr) { // En dan zo ver mogelijk naar links.
    ouder = temp;
    temp = temp->links;
  }//while
  return temp;
}//binaireboom::kleinstegrotere

// Controleer of een binaire boom een binaire zoekboom is.
//
// Argumenten: knoop *ingang ; Pointer naar een knoop (bij de 1e aanroep de wortel).
//
// Retourneert: bool ; TRUE als de boom met ingang als wortel een binaire zoekboom
//                     is, FALSE als dit niet zo is.
//
bool binaireboom::isbzboom_p(knoop *ingang) {
  knoop *temp,
        *ouder = nullptr;
  // Een lege boom is een binaire zoekboom, dus dan TRUE retourneren.
  if (ingang == nullptr)
    return true;
  // Als linker subboom geen binaire zoekboom dan sowieso niet, dus FALSE.
  if (!isbzboom_p(ingang->links))
    return false;
  // Als rechter subboom geen binaire zoekboom dan sowieso niet, dus FALSE.
  if (!isbzboom_p(ingang->rechts))
    return false;
  // Beide subbomen zijn dus binaire zoekbomen. 
  // Als de subboom met 'ingang' als wortel ook een binaire zoekboom is, moet de 
  // grootste waarde in de linker subboom kleiner zijn dan de waarde van ingang.
  temp = grootstekleinere(ingang, ouder);
  if ((temp != nullptr) && (temp->info >= ingang->info)) // De grootste kleinere is te groot.
    return false;
  // Als de subboom met 'ingang' als wortel een binaire zoekboom is, moet de 
  // kleinste waarde in de rechter subboom groter zijn dan de waarde van ingang.
  temp = kleinstegrotere(ingang, ouder);
  if ((temp != nullptr) && (temp->info <= ingang->info)) // De kg is te klein.
    return false;
  // Er is geen onvolkomenheid gevonden. De subboom met 'ingang' als wortel
  // is een binaire zoekboom
  return true;
}//binaireboom::isbzboom_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 *ouder = nullptr,
        *temp = bzoek_p(waarde, ouder);

  if (temp == nullptr) {   // De waarde was niet gevonden.
    if (ouder != nullptr) { // De boom is niet leeg.
      if (waarde < ouder->info) {
        ouder->links = new knoop(waarde, ouder->niveau+1);
      }//if
      else {
        ouder->rechts = new knoop(waarde, ouder->niveau+1);
      }//else
    }//if
    else {           // De boom is leeg.
      wortel = new knoop(waarde, 0);
    }//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 *temp,
        *ouder = nullptr,
        *ingang = bzoek_p(waarde, ouder);

  if (ingang != nullptr) { // er valt iets te verwijderen
    if ((ingang->links != nullptr) || (ingang->rechts != nullptr)) {   // interne knoop.
      if ((ingang->rechts != nullptr) && (ingang->links != nullptr)) { // met 2 kinderen.
        temp = kleinstegrotere(ingang, ouder);
        ingang->info = temp->info;
        ingang = temp;
	// kleinstegrotere heeft hooguit 1 kind (geen linkerkind)
	// kleinstegrotere bestaat hier zeker, dus ouder != nullptr
      }//if
      // vanaf dit punt is er dus nog maar hooguit 1 kind.
      if (ingang != wortel) {
        if (ingang->rechts != nullptr) { // je hebt alleen een rechterkind
          if (ouder->links == ingang)  // je bent een linkerkind
            ouder->links = ingang->rechts;
          else // ouder->rechts == ingang: je bent een rechterkind
            ouder->rechts = ingang->rechts;
        }//if
        else { // je hebt alleen een linkerkind of geen kinderen
          // onderstaande gaat ook goed als ingang->links == nullptr
          if (ouder->links == ingang)
            ouder->links = ingang->links;
          else // ouder->rechts == ingang
            ouder->rechts = ingang->links;
        }//else
      }//if
      else { // ingang == wortel en hooguit 1 kind
        if (ingang->rechts != nullptr)
          wortel = wortel->rechts;
        else // je hebt alleen een linkerkind of geen kinderen
          wortel = wortel->links;
      }//else
    }//if
    else { // ((ingang->links == nullptr) && (ingang->rechts == nullptr))
    // blad: kan gewoon verwijderd worden; wel e.e.a. nullptr maken
      if (ingang != wortel) {
        if (ouder->links == ingang)
          ouder->links = nullptr;
        else // (ouder->rechts == ingang)
          ouder->rechts = nullptr;
      }//if
      else 
        wortel = nullptr;
    }//else
    delete ingang;
  }//if
}//binaireboom::bzverwijder_p