Question

Mógłbym ktoś napisać funkcje obliczająca wysokość drzewa BST? Ważne żeby była void( void Wysokosc(BST*start) ). Poniżej dodaje moja klase i zrobione juz funkcje(moze sie przydadzą).


class BST{
public:

BST* p,*lewy,*prawy;
int klucz;
};


int Dodaj(int n, BST *start);
BST* Znajdz( BST *start, int n);
BST* poprzednik( BST *start);
void Usun( BST*start);
void InOrder( BST*start);
void PreOrder(BST*start);
void PostOrder(BST*start);
void Wysokosc(BST*start);?????????????
void losowe();
void menu();

#endif

Answer 1

//tutaj rozwiazanie
//nie testowalem tego, bo widze, ze piszesz, wiec pewnie potrzebujesz tylko zobaczyc algorytm jak sie znajduje ta wysokosc
//po prostu przechodzi sie drzewo, kontrolujac wysokosc i zapisujac najwyzsza napotkana wartosc:
//w razie pytan pisz

void Odwiedz(BST *p, int &aktualna_wysokosc, int &max_wysokosc)
{
  if (p == NULL) return;
  aktualna_wysokosc++;
  if (max_wysokosc < aktualna_wysokosc) max_wysokosc = aktualna_wysokosc;
  Odwiedz(p->lewy, aktualna_wysokosc, max_wysokosc);
  Odwiedz(p->prawy, aktualna_wysokosc, max_wysokosc);
  aktualna_wysokosc--;
  return;
}


void Wysokosc(BST *start)
{
  int pomocnicza = 0;
  int wynik = 0;

  Odwiedz(start->lewy, pomocnicza, wynik);
  Odwiedz(start->prawy, pomocnicza, wynik);

  cout << "Wysokosc wynosi " << wynik << endl;
  return;
}