Рекурсивни алгоритми в двоични дървета

Рекурсивни алгоритми в двоични дървета.

Бин.дърв.мд се обхождат по няколко н-на:

• 
  преред – посещ.възела,после лявото и дясното поддърво
  
• 
  поред – посещ.лявото дърво,после възела и накрая дясното поддърво
  
• 
  постред – посещ.лявото и дясното поддърво и после възела
  

-както и в широчина
Често е необх.да намерим стстите на разл. структурни парам.за 1 дърво,само по дадена връзка връзка към дървото.Следв.прог. съдържа рекурс.ф-ии за изчисл.броя на възлите и височината на дадено дърво.

int count (link h)

{ if ( h==NULL ) return 0;

return count (h->l) + count (h->r) + 1;} int height ( link h )

{ int u,v;

if ( h == NULL ) return -1;

u = height ( h->l ); v = height ( h->r);

if ( u > v ) return u+1; else return v+1; }

Др.ф-я ни показва рекурс.алг.за обхождане на дърво е този за отпечатване на дърво. Ако отпеч.елемента преди рекурс.викане,
получаваме прередно обхожд.Тази прог.допуска че елем.в възлите са символи:

void printnode ( char c, int h )

{ int i;

for ( i = 0; i < h; i++) printf (“ ”);

printf (“%c\n”, c); } void show ( link x, int h )

{ if ( x==NULL) {printnode(‘*’,h); return; } show (x -> r, h+1);

printnode (x -> item, h); show (x ->l, h+1); }