Rotiraj podstabla ako je levo podstablo više od desnog

Napisati funkciju koja rotira podstabla svakog čvora binarnog stabla ukoliko je visina njegovog levog podstabla veća od visine desnog podstabla.

void stablo_rotiraj_vise(Cvor* koren);

Ulaz

Sa standardnog ulaza se, sve do kraja ulaza (EOF), unosi niz celih brojeva koji se ubacuju u binarno stablo.

Izlaz

Na standardni izlaz ispisati infiksni obilazak stabla nakon rotacije podstabala.

Primer

stdin

5 3 8 1 4 7 9

stdout

1 3 4 5 7 8 9

Primer

stdin

10 5 15 3 7 12 18 1

stdout

12 15 18 10 7 5 3 1

Primer

stdin

20 10 30 5 15 25 35 2 7

stdout

25 30 35 20 15 10 2 5 7

Rešenje

stablo.h

#ifndef STABLO_H
#define STABLO_H

#include <stddef.h>

typedef struct Cvor {
    int vrednost;
    struct Cvor* levo;
    struct Cvor* desno;
} Cvor;

/* Ubacivanje */
int stablo_ubaci(Cvor** koren, int x);

/* Uništavanje */
void stablo_unisti(Cvor* koren);

/* Obilasci */
void stablo_infiksno(Cvor* koren, void (*visit)(int));
void stablo_prefiksno(Cvor* koren, void (*visit)(int));
void stablo_postfiksno(Cvor* koren, void (*visit)(int));

/* Pretraga */
Cvor* stablo_pretrazi(Cvor* koren, int x);

/* Brisanje */
void stablo_obrisi(Cvor** koren, int x);

/* Analiza */
size_t stablo_velicina(Cvor* koren);
size_t stablo_visina(Cvor* koren);

#endif

main.c

#include <stdio.h>
#include <stdlib.h>
#include "stablo.h"

void print_int(int x)
{
	printf("%d ", x);
}

void stablo_rotiraj_vise_pomocna(Cvor** koren, int* visina)
{
	if (!koren || !*koren) {
		*visina = 0;
		return;
	}

	int visina_levo = 0, visina_desno = 0;

	stablo_rotiraj_vise_pomocna(&(*koren)->levo, &visina_levo);
	stablo_rotiraj_vise_pomocna(&(*koren)->desno, &visina_desno);

	// Provera da li je levo podstablo više od desnog
	if (visina_levo > visina_desno) {
		// Rotacija podstabala
		Cvor* temp = (*koren)->levo;
		(*koren)->levo = (*koren)->desno;
		(*koren)->desno = temp;
	}

	*visina = 1 + (visina_levo > visina_desno ? visina_levo : visina_desno);
}

void stablo_rotiraj_vise(Cvor** koren)
{
	int visina;
	stablo_rotiraj_vise_pomocna(koren, &visina);
}

int main(void)
{
	Cvor *koren = NULL;

	int x;
	while (scanf("%d", &x) != EOF) {
		stablo_ubaci(&koren, x);
	}

	stablo_rotiraj_vise(&koren);

	stablo_infiksno(koren, print_int);
	printf("\n");

	stablo_unisti(koren);

	return 0;
}

stablo.c

#include "stablo.h"
#include <stdlib.h>

/* ---------- pomoćne ---------- */

static Cvor* cvor_novi(int x) {
    Cvor* n = (Cvor*)malloc(sizeof(Cvor));
    if (!n) return NULL;
    n->vrednost = x;
    n->levo = NULL;
    n->desno = NULL;
    return n;
}

/* ---------- uništavanje ---------- */

void stablo_unisti(Cvor* koren) {
    if (!koren) return;
    stablo_unisti(koren->levo);
    stablo_unisti(koren->desno);
    free(koren);
}

/* ---------- ubacivanje: BST ---------- */
/* Dogovor: x < vrednost ide levo, inače desno */

int stablo_ubaci(Cvor** koren, int x) {
    if (!koren) return 0;

    while (*koren) {
        if (x < (*koren)->vrednost)
            koren = &(*koren)->levo;
        else
            koren = &(*koren)->desno;
    }

    *koren = cvor_novi(x);
    return (*koren != NULL);
}

/* ---------- obilasci ---------- */

void stablo_infiksno(Cvor* koren, void (*visit)(int)) {
    if (!koren) return;
    stablo_infiksno(koren->levo, visit);
    visit(koren->vrednost);
    stablo_infiksno(koren->desno, visit);
}

void stablo_prefiksno(Cvor* koren, void (*visit)(int)) {
    if (!koren) return;
    visit(koren->vrednost);
    stablo_prefiksno(koren->levo, visit);
    stablo_prefiksno(koren->desno, visit);
}

void stablo_postfiksno(Cvor* koren, void (*visit)(int)) {
    if (!koren) return;
    stablo_postfiksno(koren->levo, visit);
    stablo_postfiksno(koren->desno, visit);
    visit(koren->vrednost);
}

Cvor *stablo_pretrazi(Cvor *koren, int x)
{
    if (!koren) return NULL;

    if (koren->vrednost == x)
        return koren;
    else if (x < koren->vrednost)
        return stablo_pretrazi(koren->levo, x);
    else
        return stablo_pretrazi(koren->desno, x);
}

void stablo_obrisi(Cvor **koren, int x)
{
    if (!koren || !*koren) return;

    if (x < (*koren)->vrednost) {
        stablo_obrisi(&(*koren)->levo, x);
        return;
    } 
    
    if (x > (*koren)->vrednost) {
        stablo_obrisi(&(*koren)->desno, x);
        return;
    }

    // Čvor za brisanje pronađen
    if (!(*koren)->levo) {
        Cvor *temp = (*koren)->desno;
        free(*koren);
        *koren = temp;
        return;
    }
    
    if (!(*koren)->desno) {
        Cvor *temp = (*koren)->levo;
        free(*koren);
        *koren = temp;
        return;
    }

    // Čvor sa dva deteta: nađi najmanji u desnom podstablu
    Cvor *parent = *koren;
    Cvor *successor = (*koren)->desno;
    while (successor->levo) {
        parent = successor;
        successor = successor->levo;
    }

    // Kopiraj vrednost naslednika
    (*koren)->vrednost = successor->vrednost;

    // Obriši naslednika
    if (parent->levo == successor)
        parent->levo = successor->desno;
    else
        parent->desno = successor->desno;
    free(successor);
}

/* ---------- size / height ---------- */

size_t stablo_velicina(Cvor* koren) {
    if (!koren) return 0;
    return 1
         + stablo_velicina(koren->levo)
         + stablo_velicina(koren->desno);
}

size_t stablo_visina(Cvor* koren) {
    if (!koren) return 0;
    size_t hl = stablo_visina(koren->levo);
    size_t hr = stablo_visina(koren->desno);
    return 1 + (hl > hr ? hl : hr);
}