Struktury danych - drzewa
wat-wdp@wp.pl
typedef int Telem;
typedef struct Telem_drzewa {
Telem_drzewa* lewy;
Telem_drzewa* prawy;
Telem elem;
};
typedef Telem_drzewa* Tdrzewo;
main() {
Tdrzewo dr = NULL;
wstaw_do_drzewa(&dr,10);
wstaw_do_drzewa(&dr, 5);
wstaw_do_drzewa(&dr, 3);
wstaw_do_drzewa(&dr, 7);
wstaw_do_drzewa(&dr,15);
wypisz_drzewo(dr,_skok);
if (usun_z_drzewa(&dr,5)) {
wypisz_drzewo(dr,_skok);
}
usun_drzewo(&dr);
}
dr
typedef int Telem;
typedef struct Telem_drzewa {
Telem_drzewa* lewy;
Telem_drzewa* prawy;
Telem elem;
};
typedef Telem_drzewa* Tdrzewo;
main() {
Tdrzewo dr = NULL;
wstaw_do_drzewa(&dr,10);
wstaw_do_drzewa(&dr, 5);
wstaw_do_drzewa(&dr, 3);
wstaw_do_drzewa(&dr, 7);
wstaw_do_drzewa(&dr,15);
wypisz_drzewo(dr,_skok);
if (usun_z_drzewa(&dr,5)) {
wypisz_drzewo(dr,_skok);
}
usun_drzewo(&dr);
}
null
dr
Struktury danych - drzewa
Wstawianie elementów do
drzewa
null
dr
typedef int Telem;
typedef struct Telem_drzewa {
Telem_drzewa* lewy;
Telem_drzewa* prawy;
Telem elem;
};
typedef Telem_drzewa* Tdrzewo;
main() {
Tdrzewo dr = NULL;
wstaw_do_drzewa(&dr,10);
wstaw_do_drzewa(&dr,10);
wstaw_do_drzewa(&dr, 5);
wstaw_do_drzewa(&dr, 3);
wstaw_do_drzewa(&dr, 7);
wstaw_do_drzewa(&dr,15);
wypisz_drzewo(dr,_skok);
if (usun_z_drzewa(&dr,5)) {
wypisz_drzewo(dr,_skok);
}
usun_drzewo(&dr);
}
void wstaw_do_drzewa (Tdrzewo* d, Telem e) {
if (*d == NULL) {
*d = (Tdrzewo)malloc(sizeof(Telem_drzewa));
(**d).lewy = NULL;
(**d).prawy = NULL;
(**d).elem = e;
} else {
if ((**d).elem > e) {
wstaw_do_drzewa(&(**d).lewy,e);
} else {
wstaw_do_drzewa(&(**d).prawy,e);
}
}
}
null
dr
typedef int Telem;
typedef struct Telem_drzewa {
Telem_drzewa* lewy;
Telem_drzewa* prawy;
Telem elem;
};
typedef Telem_drzewa* Tdrzewo;
main() {
Tdrzewo dr = NULL;
wstaw_do_drzewa(&dr,10);
wstaw_do_drzewa(&dr,10);
wstaw_do_drzewa(&dr, 5);
wstaw_do_drzewa(&dr, 3);
wstaw_do_drzewa(&dr, 7);
wstaw_do_drzewa(&dr,15);
wypisz_drzewo(dr,_skok);
if (usun_z_drzewa(&dr,5)) {
wypisz_drzewo(dr,_skok);
}
usun_drzewo(&dr);
}
void wstaw_do_drzewa (Tdrzewo* d, Telem e) {
if (*d == NULL) {
*d = (Tdrzewo)malloc(sizeof(Telem_drzewa));
(**d).lewy = NULL;
(**d).prawy = NULL;
(**d).elem = e;
} else {
if ((**d).elem > e) {
wstaw_do_drzewa(&(**d).lewy,e);
} else {
wstaw_do_drzewa(&(**d).prawy,e);
}
}
}
Pod adres przekazany przez parametr d
zapisz adres (wskaźnik) zwrócony przez
funkcję malloc;
*d jest adresem obiektu typu Tdrzewo
(wskaźnika)
dr
typedef int Telem;
typedef struct Telem_drzewa {
Telem_drzewa* lewy;
Telem_drzewa* prawy;
Telem elem;
};
typedef Telem_drzewa* Tdrzewo;
main() {
Tdrzewo dr = NULL;
wstaw_do_drzewa(&dr,10);
wstaw_do_drzewa(&dr,10);
wstaw_do_drzewa(&dr, 5);
wstaw_do_drzewa(&dr, 3);
wstaw_do_drzewa(&dr, 7);
wstaw_do_drzewa(&dr,15);
wypisz_drzewo(dr,_skok);
if (usun_z_drzewa(&dr,5)) {
wypisz_drzewo(dr,_skok);
}
usun_drzewo(&dr);
}
void wstaw_do_drzewa (Tdrzewo* d, Telem e) {
if (*d == NULL) {
*d = (Tdrzewo)malloc(sizeof(Telem_drzewa));
(**d).lewy = NULL;
(**d).prawy = NULL;
(**d).elem = e;
} else {
if ((**d).elem > e) {
wstaw_do_drzewa(&(**d).lewy,e);
} else {
wstaw_do_drzewa(&(**d).prawy,e);
}
}
}
*d – adres wskaźnika (Tdrzewo jest
wskaźnikiem)
**d – struktura wskazywana przez
wskaźnik *r
(**d).prawy – pole struktury
&(**d).prawy – adres pola struktury
(wskaźnik)
dr
prawy null
lewy null
elem 10
typedef int Telem;
typedef struct Telem_drzewa {
Telem_drzewa* lewy;
Telem_drzewa* prawy;
Telem elem;
};
typedef Telem_drzewa* Tdrzewo;
main() {
Tdrzewo dr = NULL;
wstaw_do_drzewa(&dr,10);
wstaw_do_drzewa(&dr,10);
wstaw_do_drzewa(&dr, 5);
wstaw_do_drzewa(&dr, 3);
wstaw_do_drzewa(&dr, 7);
wstaw_do_drzewa(&dr,15);
wypisz_drzewo(dr,_skok);
if (usun_z_drzewa(&dr,5)) {
wypisz_drzewo(dr,_skok);
}
usun_drzewo(&dr);
}
void wstaw_do_drzewa (Tdrzewo* d, Telem e) {
if (*d == NULL) {
*d = (Tdrzewo)malloc(sizeof(Telem_drzewa));
(**d).lewy = NULL;
(**d).prawy = NULL;
(**d).elem = e;
} else {
if ((**d).elem > e) {
wstaw_do_drzewa(&(**d).lewy,e);
} else {
wstaw_do_drzewa(&(**d).prawy,e);
}
}
}
dr
prawy null
lewy null
elem 10
typedef int Telem;
typedef struct Telem_drzewa {
Telem_drzewa* lewy;
Telem_drzewa* prawy;
Telem elem;
};
typedef Telem_drzewa* Tdrzewo;
main() {
Tdrzewo dr = NULL;
wstaw_do_drzewa(&dr,10);
wstaw_do_drzewa(&dr, 5);
wstaw_do_drzewa(&dr, 3);
wstaw_do_drzewa(&dr, 7);
wstaw_do_drzewa(&dr,15);
wypisz_drzewo(dr,_skok);
if (usun_z_drzewa(&dr,5)) {
wypisz_drzewo(dr,_skok);
}
usun_drzewo(&dr);
}
dr
prawy null
lewy null
elem 10
typedef int Telem;
typedef struct Telem_drzewa {
Telem_drzewa* lewy;
Telem_drzewa* prawy;
Telem elem;
};
typedef Telem_drzewa* Tdrzewo;
main() {
Tdrzewo dr = NULL;
wstaw_do_drzewa(&dr,10);
wstaw_do_drzewa(&dr, 5);
wstaw_do_drzewa(&dr, 5);
wstaw_do_drzewa(&dr, 3);
wstaw_do_drzewa(&dr, 7);
wstaw_do_drzewa(&dr,15);
wypisz_drzewo(dr,_skok);
if (usun_z_drzewa(&dr,5)) {
wypisz_drzewo(dr,_skok);
}
usun_drzewo(&dr);
}
void wstaw_do_drzewa (Tdrzewo* d, Telem e) {
if (*d == NULL) {
*d = (Tdrzewo)malloc(sizeof(Telem_drzewa));
(**d).lewy = NULL;
(**d).prawy = NULL;
(**d).elem = e;
} else {
if ((**d).elem > e) {
wstaw_do_drzewa(&(**d).lewy,e);
} else {
wstaw_do_drzewa(&(**d).prawy,e);
}
}
}
dr
prawy null
lewy null
elem 10
typedef int Telem;
typedef struct Telem_drzewa {
Telem_drzewa* lewy;
Telem_drzewa* prawy;
Telem elem;
};
typedef Telem_drzewa* Tdrzewo;
main() {
Tdrzewo dr = NULL;
wstaw_do_drzewa(&dr,10);
wstaw_do_drzewa(&dr, 5);
wstaw_do_drzewa(&dr, 5);
wstaw_do_drzewa(&dr, 3);
wstaw_do_drzewa(&dr, 7);
wstaw_do_drzewa(&dr,15);
wypisz_drzewo(dr,_skok);
if (usun_z_drzewa(&dr,5)) {
wypisz_drzewo(dr,_skok);
}
usun_drzewo(&dr);
}
void wstaw_do_drzewa (Tdrzewo* d, Telem e) {
if (*d == NULL) {
*d = (Tdrzewo)malloc(sizeof(Telem_drzewa));
(**d).lewy = NULL;
(**d).prawy = NULL;
(**d).elem = e;
} else {
if ((**d).elem > e) {
wstaw_do_drzewa(&(**d).lewy,e);
} else {
wstaw_do_drzewa(&(**d).prawy,e);
}
}
}
dr
prawy null
lewy null
elem 10
typedef int Telem;
typedef struct Telem_drzewa {
Telem_drzewa* lewy;
Telem_drzewa* prawy;
Telem elem;
};
typedef Telem_drzewa* Tdrzewo;
main() {
Tdrzewo dr = NULL;
wstaw_do_drzewa(&dr,10);
wstaw_do_drzewa(&dr, 5);
wstaw_do_drzewa(&dr, 5);
wstaw_do_drzewa(&dr, 3);
wstaw_do_drzewa(&dr, 7);
wstaw_do_drzewa(&dr,15);
wypisz_drzewo(dr,_skok);
if (usun_z_drzewa(&dr,5)) {
wypisz_drzewo(dr,_skok);
}
usun_drzewo(&dr);
}
void wstaw_do_drzewa (Tdrzewo* d, Telem e) {
if (*d == NULL) {
*d = (Tdrzewo)malloc(sizeof(Telem_drzewa));
(**d).lewy = NULL;
(**d).prawy = NULL;
(**d).elem = e;
} else {
if ((**d).elem > e) {
wstaw_do_drzewa(&(**d).lewy,e);
} else {
wstaw_do_drzewa(&(**d).prawy,e);
}
}
}
d
dr
prawy null
lewy null
elem 10
typedef int Telem;
typedef struct Telem_drzewa {
Telem_drzewa* lewy;
Telem_drzewa* prawy;
Telem elem;
};
typedef Telem_drzewa* Tdrzewo;
main() {
Tdrzewo dr = NULL;
wstaw_do_drzewa(&dr,10);
wstaw_do_drzewa(&dr, 5);
wstaw_do_drzewa(&dr, 5);
wstaw_do_drzewa(&dr, 3);
wstaw_do_drzewa(&dr, 7);
wstaw_do_drzewa(&dr,15);
wypisz_drzewo(dr,_skok);
if (usun_z_drzewa(&dr,5)) {
wypisz_drzewo(dr,_skok);
}
usun_drzewo(&dr);
}
void wstaw_do_drzewa (Tdrzewo* d, Telem e) {
if (*d == NULL) {
*d = (Tdrzewo)malloc(sizeof(Telem_drzewa));
(**d).lewy = NULL;
(**d).prawy = NULL;
(**d).elem = e;
} else {
if ((**d).elem > e) {
wstaw_do_drzewa(&(**d).lewy,e);
} else {
wstaw_do_drzewa(&(**d).prawy,e);
}
}
}
void wstaw_do_drzewa (Tdrzewo* d, Telem e) {
if (*d == NULL) {
*d = (Tdrzewo)malloc(sizeof(Telem_drzewa));
(**d).lewy = NULL;
(**d).prawy = NULL;
(**d).elem = e;
} else {
if ((**d).elem > e) {
wstaw_do_drzewa(&(**d).lewy,e);
} else {
wstaw_do_drzewa(&(**d).prawy,e);
}
}
}
d
dr
prawy null
lewy null
elem 10
typedef int Telem;
typedef struct Telem_drzewa {
Telem_drzewa* lewy;
Telem_drzewa* prawy;
Telem elem;
};
typedef Telem_drzewa* Tdrzewo;
main() {
Tdrzewo dr = NULL;
wstaw_do_drzewa(&dr,10);
wstaw_do_drzewa(&dr, 5);
wstaw_do_drzewa(&dr, 5);
wstaw_do_drzewa(&dr, 3);
wstaw_do_drzewa(&dr, 7);
wstaw_do_drzewa(&dr,15);
wypisz_drzewo(dr,_skok);
if (usun_z_drzewa(&dr,5)) {
wypisz_drzewo(dr,_skok);
}
usun_drzewo(&dr);
}
void wstaw_do_drzewa (Tdrzewo* d, Telem e) {
if (*d == NULL) {
*d = (Tdrzewo)malloc(sizeof(Telem_drzewa));
(**d).lewy = NULL;
(**d).prawy = NULL;
(**d).elem = e;
} else {
if ((**d).elem > e) {
wstaw_do_drzewa(&(**d).lewy,e);
} else {
wstaw_do_drzewa(&(**d).prawy,e);
}
}
}
void wstaw_do_drzewa (Tdrzewo* d, Telem e) {
if (*d == NULL) {
*d = (Tdrzewo)malloc(sizeof(Telem_drzewa));
(**d).lewy = NULL;
(**d).prawy = NULL;
(**d).elem = e;
} else {
if ((**d).elem > e) {
wstaw_do_drzewa(&(**d).lewy,e);
} else {
wstaw_do_drzewa(&(**d).prawy,e);
}
}
}
d
dr
prawy null
lewy
elem 10
prawy null
lewy null
elem 5
typedef int Telem;
typedef struct Telem_drzewa {
Telem_drzewa* lewy;
Telem_drzewa* prawy;
Telem elem;
};
typedef Telem_drzewa* Tdrzewo;
main() {
Tdrzewo dr = NULL;
wstaw_do_drzewa(&dr,10);
wstaw_do_drzewa(&dr, 5);
wstaw_do_drzewa(&dr, 5);
wstaw_do_drzewa(&dr, 3);
wstaw_do_drzewa(&dr, 7);
wstaw_do_drzewa(&dr,15);
wypisz_drzewo(dr,_skok);
if (usun_z_drzewa(&dr,5)) {
wypisz_drzewo(dr,_skok);
}
usun_drzewo(&dr);
}
void wstaw_do_drzewa (Tdrzewo* d, Telem e) {
if (*d == NULL) {
*d = (Tdrzewo)malloc(sizeof(Telem_drzewa));
(**d).lewy = NULL;
(**d).prawy = NULL;
(**d).elem = e;
} else {
if ((**d).elem > e) {
wstaw_do_drzewa(&(**d).lewy,e);
} else {
wstaw_do_drzewa(&(**d).prawy,e);
}
}
}
void wstaw_do_drzewa (Tdrzewo* d, Telem e) {
if (*d == NULL) {
*d = (Tdrzewo)malloc(sizeof(Telem_drzewa));
(**d).lewy = NULL;
(**d).prawy = NULL;
(**d).elem = e;
} else {
if ((**d).elem > e) {
wstaw_do_drzewa(&(**d).lewy,e);
} else {
wstaw_do_drzewa(&(**d).prawy,e);
}
}
}
dr
prawy null
lewy
elem 10
prawy null
lewy null
elem 5
typedef int Telem;
typedef struct Telem_drzewa {
Telem_drzewa* lewy;
Telem_drzewa* prawy;
Telem elem;
};
typedef Telem_drzewa* Tdrzewo;
main() {
Tdrzewo dr = NULL;
wstaw_do_drzewa(&dr,10);
wstaw_do_drzewa(&dr, 5);
wstaw_do_drzewa(&dr, 5);
wstaw_do_drzewa(&dr, 3);
wstaw_do_drzewa(&dr, 7);
wstaw_do_drzewa(&dr,15);
wypisz_drzewo(dr,_skok);
if (usun_z_drzewa(&dr,5)) {
wypisz_drzewo(dr,_skok);
}
usun_drzewo(&dr);
}
void wstaw_do_drzewa (Tdrzewo* d, Telem e) {
if (*d == NULL) {
*d = (Tdrzewo)malloc(sizeof(Telem_drzewa));
(**d).lewy = NULL;
(**d).prawy = NULL;
(**d).elem = e;
} else {
if ((**d).elem > e) {
wstaw_do_drzewa(&(**d).lewy,e);
} else {
wstaw_do_drzewa(&(**d).prawy,e);
}
}
}
dr
prawy null
lewy
elem 10
prawy null
lewy null
elem 5
typedef int Telem;
typedef struct Telem_drzewa {
Telem_drzewa* lewy;
Telem_drzewa* prawy;
Telem elem;
};
typedef Telem_drzewa* Tdrzewo;
main() {
Tdrzewo dr = NULL;
wstaw_do_drzewa(&dr,10);
wstaw_do_drzewa(&dr, 5);
wstaw_do_drzewa(&dr, 3);
wstaw_do_drzewa(&dr, 7);
wstaw_do_drzewa(&dr,15);
wypisz_drzewo(dr,_skok);
if (usun_z_drzewa(&dr,5)) {
wypisz_drzewo(dr,_skok);
}
usun_drzewo(&dr);
}
dr
prawy null
lewy
elem 10
prawy null
lewy
elem 5
prawy null
lewy null
elem 3
typedef int Telem;
typedef struct Telem_drzewa {
Telem_drzewa* lewy;
Telem_drzewa* prawy;
Telem elem;
};
typedef Telem_drzewa* Tdrzewo;
main() {
Tdrzewo dr = NULL;
wstaw_do_drzewa(&dr,10);
wstaw_do_drzewa(&dr, 5);
wstaw_do_drzewa(&dr, 3);
wstaw_do_drzewa(&dr, 7);
wstaw_do_drzewa(&dr,15);
wypisz_drzewo(dr,_skok);
if (usun_z_drzewa(&dr,5)) {
wypisz_drzewo(dr,_skok);
}
usun_drzewo(&dr);
}
dr
prawy null
lewy
elem 10
prawy
lewy
elem 5
prawy null
lewy null
elem 3
prawy null
lewy null
el 7
typedef int Telem;
typedef struct Telem_drzewa {
Telem_drzewa* lewy;
Telem_drzewa* prawy;
Telem elem;
};
typedef Telem_drzewa* Tdrzewo;
main() {
Tdrzewo dr = NULL;
wstaw_do_drzewa(&dr,10);
wstaw_do_drzewa(&dr, 5);
wstaw_do_drzewa(&dr, 3);
wstaw_do_drzewa(&dr, 7);
wstaw_do_drzewa(&dr,15);
wypisz_drzewo(dr,_skok);
if (usun_z_drzewa(&dr,5)) {
wypisz_drzewo(dr,_skok);
}
usun_drzewo(&dr);
}
dr
prawy
lewy
elem 10
prawy
lewy
elem 5
prawy null
lewy null
elem 3
prawy null
lewy null
elem 7
prawy null
lewy null
elem 15
typedef int Telem;
typedef struct Telem_drzewa {
Telem_drzewa* lewy;
Telem_drzewa* prawy;
Telem elem;
};
typedef Telem_drzewa* Tdrzewo;
main() {
Tdrzewo dr = NULL;
wstaw_do_drzewa(&dr,10);
wstaw_do_drzewa(&dr, 5);
wstaw_do_drzewa(&dr, 3);
wstaw_do_drzewa(&dr, 7);
wstaw_do_drzewa(&dr,15);
wypisz_drzewo(dr,_skok);
if (usun_z_drzewa(&dr,5)) {
wypisz_drzewo(dr,_skok);
}
usun_drzewo(&dr);
}
Struktury danych - drzewa
Drukowanie struktury drzewa
d
r
p
ra
w
y
le
w
y
e
le
m
1
0
p
ra
w
y
le
w
y
e
le
m
5
p
ra
w
y
n
u
ll
le
w
y
n
u
ll
e
le
m
3
p
ra
w
y
n
u
ll
le
w
y
n
u
ll
e
le
m
7
p
ra
w
y
n
u
ll
le
w
y
n
u
ll
e
le
m
1
5
typedef int Telem;
typedef struct Telem_drzewa {
Telem_drzewa* lewy;
Telem_drzewa* prawy;
Telem elem;
};
typedef Telem_drzewa* Tdrzewo;
main() {
Tdrzewo dr = NULL;
wstaw_do_drzewa(&dr,10);
wstaw_do_drzewa(&dr, 5);
wstaw_do_drzewa(&dr, 3);
wstaw_do_drzewa(&dr, 7);
wstaw_do_drzewa(&dr,15);
wypisz_drzewo(dr,_skok);
wypisz_drzewo(dr,_skok);
if (usun_z_drzewa(&dr,5)) {
wypisz_drzewo(dr,_skok);
}
usun_drzewo(&dr);
}
void wypisz_drzewo (Tdrzewo d, int odl) {
if (d != NULL) {
wypisz_drzewo((*d).prawy,odl+_skok);
printf("\n");
for (int i = 0; i < odl; printf(" "), i++);
wypisz_elem((*d).elem);
wypisz_drzewo((*d).lewy,odl+_skok);
}
}
d
r
p
ra
w
y
le
w
y
e
le
m
1
0
p
ra
w
y
le
w
y
e
le
m
5
e
le
m
3
e
le
m
7
p
ra
w
y
n
u
ll
le
w
y
n
u
ll
e
le
m
1
5
typedef int Telem;
typedef struct Telem_drzewa {
Telem_drzewa* lewy;
Telem_drzewa* prawy;
Telem elem;
};
typedef Telem_drzewa* Tdrzewo;
main() {
Tdrzewo dr = NULL;
wstaw_do_drzewa(&dr,10);
wstaw_do_drzewa(&dr, 5);
wstaw_do_drzewa(&dr, 3);
wstaw_do_drzewa(&dr, 7);
wstaw_do_drzewa(&dr,15);
wypisz_drzewo(dr,_skok);
wypisz_drzewo(dr,_skok);
if (usun_z_drzewa(&dr,5)) {
wypisz_drzewo(dr,_skok);
}
usun_drzewo(&dr);
}
void wypisz_drzewo (Tdrzewo d, int odl) {
if (d != NULL) {
wypisz_drzewo((*d).prawy,odl+_skok);
printf("\n");
for (int i = 0; i < odl; printf(" "), i++);
wypisz_elem((*d).elem);
wypisz_drzewo((*d).lewy,odl+_skok);
}
}
d
r
p
ra
w
y
le
w
y
e
le
m
1
0
p
ra
w
y
le
w
y
e
le
m
5
p
ra
w
y
n
u
ll
le
w
y
n
u
ll
e
le
m
3
p
ra
w
y
n
u
ll
le
w
y
n
u
ll
e
le
m
7
p
ra
w
y
n
u
ll
le
w
y
n
u
ll
e
le
m
1
5
typedef int Telem;
typedef struct Telem_drzewa {
Telem_drzewa* lewy;
Telem_drzewa* prawy;
Telem elem;
};
typedef Telem_drzewa* Tdrzewo;
main() {
Tdrzewo dr = NULL;
wstaw_do_drzewa(&dr,10);
wstaw_do_drzewa(&dr, 5);
wstaw_do_drzewa(&dr, 3);
wstaw_do_drzewa(&dr, 7);
wstaw_do_drzewa(&dr,15);
wypisz_drzewo(dr,_skok);
wypisz_drzewo(dr,_skok);
if (usun_z_drzewa(&dr,5)) {
wypisz_drzewo(dr,_skok);
}
usun_drzewo(&dr);
}
void wypisz_drzewo (Tdrzewo d, int odl) {
if (d != NULL) {
wypisz_drzewo((*d).prawy,odl+_skok);
printf("\n");
for (int i = 0; i < odl; printf(" "), i++);
wypisz_elem((*d).elem);
wypisz_drzewo((*d).lewy,odl+_skok);
}
}
d
r
p
ra
w
y
le
w
y
e
le
m
1
0
p
ra
w
y
le
w
y
e
le
m
5
p
ra
w
y
n
u
ll
le
w
y
n
u
ll
e
le
m
3
p
ra
w
y
n
u
ll
le
w
y
n
u
ll
e
le
m
7
p
ra
w
y
n
u
ll
le
w
y
n
u
ll
e
le
m
1
5
typedef int Telem;
typedef struct Telem_drzewa {
Telem_drzewa* lewy;
Telem_drzewa* prawy;
Telem elem;
};
typedef Telem_drzewa* Tdrzewo;
main() {
Tdrzewo dr = NULL;
wstaw_do_drzewa(&dr,10);
wstaw_do_drzewa(&dr, 5);
wstaw_do_drzewa(&dr, 3);
wstaw_do_drzewa(&dr, 7);
wstaw_do_drzewa(&dr,15);
wypisz_drzewo(dr,_skok);
wypisz_drzewo(dr,_skok);
if (usun_z_drzewa(&dr,5)) {
wypisz_drzewo(dr,_skok);
}
usun_drzewo(&dr);
}
void wypisz_drzewo (Tdrzewo d, int odl) {
if (d != NULL) {
wypisz_drzewo((*d).prawy,odl+_skok);
printf("\n");
for (int i = 0; i < odl; printf(" "), i++);
wypisz_elem((*d).elem);
wypisz_drzewo((*d).lewy,odl+_skok);
}
}
dr
prawy
lewy
elem 10
prawy
lewy
elem 5
prawy null
lewy null
elem 3
prawy null
lewy null
elem 7
prawy null
lewy null
elem 15
typedef int Telem;
typedef struct Telem_drzewa {
Telem_drzewa* lewy;
Telem_drzewa* prawy;
Telem elem;
};
typedef Telem_drzewa* Tdrzewo;
main() {
Tdrzewo dr = NULL;
wstaw_do_drzewa(&dr,10);
wstaw_do_drzewa(&dr, 5);
wstaw_do_drzewa(&dr, 3);
wstaw_do_drzewa(&dr, 7);
wstaw_do_drzewa(&dr,15);
wypisz_drzewo(dr,_skok);
if (usun_z_drzewa(&dr,5)) {
wypisz_drzewo(dr,_skok);
}
usun_drzewo(&dr);
}
na później
dr
prawy
lewy
elem 10
prawy
lewy
elem 5
prawy null
lewy null
elem 3
prawy null
lewy null
elem 7
typedef int Telem;
typedef struct Telem_drzewa {
Telem_drzewa* lewy;
Telem_drzewa* prawy;
Telem elem;
};
typedef Telem_drzewa* Tdrzewo;
main() {
Tdrzewo dr = NULL;
wstaw_do_drzewa(&dr,10);
wstaw_do_drzewa(&dr, 5);
wstaw_do_drzewa(&dr, 3);
wstaw_do_drzewa(&dr, 7);
wstaw_do_drzewa(&dr,15);
wypisz_drzewo(dr,_skok);
if (usun_z_drzewa(&dr,5)) {
wypisz_drzewo(dr,_skok);
}
usun_drzewo(&dr);
}
prawy null
lewy null
elem 15
Struktury danych - drzewa
Usuwanie drzewa
dr
prawy
lewy
elem 10
prawy
lewy
elem 5
prawy null
lewy null
elem 3
prawy null
lewy null
elem 7
typedef int Telem;
typedef struct Telem_drzewa {
Telem_drzewa* lewy;
Telem_drzewa* prawy;
Telem elem;
};
typedef Telem_drzewa* Tdrzewo;
main() {
Tdrzewo dr = NULL;
wstaw_do_drzewa(&dr,10);
wstaw_do_drzewa(&dr, 5);
wstaw_do_drzewa(&dr, 3);
wstaw_do_drzewa(&dr, 7);
wstaw_do_drzewa(&dr,15);
wypisz_drzewo(dr,_skok);
if (usun_z_drzewa(&dr,5)) {
wypisz_drzewo(dr,_skok);
}
usun_drzewo(&dr);
usun_drzewo(&dr);
}
prawy null
lewy null
elem 15
void usun_drzewo (Tdrzewo* d) {
if (*d != NULL) {
usun_drzewo(&(**d).lewy);
usun_drzewo(&(**d).prawy);
free(*d);
*d = NULL;
}
}
dr
prawy
lewy
elem 10
prawy
lewy
elem 5
prawy null
lewy null
elem 3
prawy null
lewy null
elem 7
typedef int Telem;
typedef struct Telem_drzewa {
Telem_drzewa* lewy;
Telem_drzewa* prawy;
Telem elem;
};
typedef Telem_drzewa* Tdrzewo;
main() {
Tdrzewo dr = NULL;
wstaw_do_drzewa(&dr,10);
wstaw_do_drzewa(&dr, 5);
wstaw_do_drzewa(&dr, 3);
wstaw_do_drzewa(&dr, 7);
wstaw_do_drzewa(&dr,15);
wypisz_drzewo(dr,_skok);
if (usun_z_drzewa(&dr,5)) {
wypisz_drzewo(dr,_skok);
}
usun_drzewo(&dr);
usun_drzewo(&dr);
}
void usun_drzewo (Tdrzewo* d) {
if (*d != NULL) {
usun_drzewo(&(**d).lewy);
usun_drzewo(&(**d).prawy);
free(*d);
*d = NULL;
}
}
prawy null
lewy null
elem 15
dr
prawy
lewy null
elem 10
prawy null
lewy null
elem 15
typedef int Telem;
typedef struct Telem_drzewa {
Telem_drzewa* lewy;
Telem_drzewa* prawy;
Telem elem;
};
typedef Telem_drzewa* Tdrzewo;
main() {
Tdrzewo dr = NULL;
wstaw_do_drzewa(&dr,10);
wstaw_do_drzewa(&dr, 5);
wstaw_do_drzewa(&dr, 3);
wstaw_do_drzewa(&dr, 7);
wstaw_do_drzewa(&dr,15);
wypisz_drzewo(dr,_skok);
if (usun_z_drzewa(&dr,5)) {
wypisz_drzewo(dr,_skok);
}
usun_drzewo(&dr);
usun_drzewo(&dr);
}
void usun_drzewo (Tdrzewo* d) {
if (*d != NULL) {
usun_drzewo(&(**d).lewy);
usun_drzewo(&(**d).prawy);
free(*d);
*d = NULL;
}
}
dr
prawy null
lewy null
elem 10
typedef int Telem;
typedef struct Telem_drzewa {
Telem_drzewa* lewy;
Telem_drzewa* prawy;
Telem elem;
};
typedef Telem_drzewa* Tdrzewo;
main() {
Tdrzewo dr = NULL;
wstaw_do_drzewa(&dr,10);
wstaw_do_drzewa(&dr, 5);
wstaw_do_drzewa(&dr, 3);
wstaw_do_drzewa(&dr, 7);
wstaw_do_drzewa(&dr,15);
wypisz_drzewo(dr,_skok);
if (usun_z_drzewa(&dr,5)) {
wypisz_drzewo(dr,_skok);
}
usun_drzewo(&dr);
usun_drzewo(&dr);
}
void usun_drzewo (Tdrzewo* d) {
if (*d != NULL) {
usun_drzewo(&(**d).lewy);
usun_drzewo(&(**d).prawy);
free(*d);
*d = NULL;
}
}
???
dr
typedef int Telem;
typedef struct Telem_drzewa {
Telem_drzewa* lewy;
Telem_drzewa* prawy;
Telem elem;
};
typedef Telem_drzewa* Tdrzewo;
main() {
Tdrzewo dr = NULL;
wstaw_do_drzewa(&dr,10);
wstaw_do_drzewa(&dr, 5);
wstaw_do_drzewa(&dr, 3);
wstaw_do_drzewa(&dr, 7);
wstaw_do_drzewa(&dr,15);
wypisz_drzewo(dr,_skok);
if (usun_z_drzewa(&dr,5)) {
wypisz_drzewo(dr,_skok);
}
usun_drzewo(&dr);
usun_drzewo(&dr);
}
void usun_drzewo (Tdrzewo* d) {
if (*d != NULL) {
usun_drzewo(&(**d).lewy);
usun_drzewo(&(**d).prawy);
free(*d);
*d = NULL;
}
}
null
dr
typedef int Telem;
typedef struct Telem_drzewa {
Telem_drzewa* lewy;
Telem_drzewa* prawy;
Telem elem;
};
typedef Telem_drzewa* Tdrzewo;
main() {
Tdrzewo dr = NULL;
wstaw_do_drzewa(&dr,10);
wstaw_do_drzewa(&dr, 5);
wstaw_do_drzewa(&dr, 3);
wstaw_do_drzewa(&dr, 7);
wstaw_do_drzewa(&dr,15);
wypisz_drzewo(dr,_skok);
if (usun_z_drzewa(&dr,5)) {
wypisz_drzewo(dr,_skok);
}
usun_drzewo(&dr);
usun_drzewo(&dr);
}
void usun_drzewo (Tdrzewo* d) {
if (*d != NULL) {
usun_drzewo(&(**d).lewy);
usun_drzewo(&(**d).prawy);
free(*d);
*d = NULL;
}
}
null
dr
typedef int Telem;
typedef struct Telem_drzewa {
Telem_drzewa* lewy;
Telem_drzewa* prawy;
Telem elem;
};
typedef Telem_drzewa* Tdrzewo;
main() {
Tdrzewo dr = NULL;
wstaw_do_drzewa(&dr,10);
wstaw_do_drzewa(&dr, 5);
wstaw_do_drzewa(&dr, 3);
wstaw_do_drzewa(&dr, 7);
wstaw_do_drzewa(&dr,15);
wypisz_drzewo(dr,_skok);
if (usun_z_drzewa(&dr,5)) {
wypisz_drzewo(dr,_skok);
}
usun_drzewo(&dr);
}
Struktury danych - drzewa
Usuwanie elementów struktury
drzewa
dr
prawy
lewy
elem 10
prawy
lewy
elem 5
prawy null
lewy null
elem 3
prawy null
lewy null
elem 7
prawy null
lewy null
elem 15
typedef int Telem;
typedef struct Telem_drzewa {
Telem_drzewa* lewy;
Telem_drzewa* prawy;
Telem elem;
};
typedef Telem_drzewa* Tdrzewo;
main() {
Tdrzewo dr = NULL;
wstaw_do_drzewa(&dr,10);
wstaw_do_drzewa(&dr, 5);
wstaw_do_drzewa(&dr, 3);
wstaw_do_drzewa(&dr, 7);
wstaw_do_drzewa(&dr,15);
wypisz_drzewo(dr,_skok);
if (usun_z_drzewa(&dr,5)) {
wypisz_drzewo(dr,_skok);
}
usun_drzewo(&dr);
}
teraz
dr
50
25
75
10
60
28
65
30
20
7
29
15
22
27
21
brak następników
jeden następnik
dwa następniki
Usuwanie elementów z drzewa
int usun_z_drzewa (Tdrzewo* d, Telem e)
{
if (*d != NULL) {
if ((**d).elem > e)
usun_z_drzewa(&(**d).lewy,e);
else {
if ((**d).elem < e)
usun_z_drzewa(&(**d).prawy,e);
else {
q = *d;
if ((*q).lewy == NULL)
*d = (*q).prawy;
else {
if ((*q).prawy == NULL)
*d = (*q).lewy;
else
usun(&(*q).lewy);
}
free(q);
return(1);
}
}
} else
return(0);
}
dr
50
25
75
10
60
28
65
30
20
7
29
15
22
27
21
wyszukanie elementu
do usunięcia
sprawdzenie, czy
jest jeden lub brak
następnika
usunięcie, jeśli są
dwa następniki
int usun_z_drzewa (Tdrzewo* d, Telem e)
{
if (*d != NULL) {
if ((**d).elem > e)
usun_z_drzewa(&(**d).lewy,e);
else {
if ((**d).elem < e)
usun_z_drzewa(&(**d).prawy,e);
else {
q = *d;
if ((*q).lewy == NULL)
*d = (*q).prawy;
else {
if ((*q).prawy == NULL)
*d = (*q).lewy;
else
usun(&(*q).lewy);
}
free(q);
return(1);
}
}
} else
return(0);
}
dr
50
25
75
10
60
28
65
30
20
7
29
15
22
27
21
np.: usun_z_drzewa (dr, 75);
q
int usun_z_drzewa (Tdrzewo* d, Telem e)
{
if (*d != NULL) {
if ((**d).elem > e)
usun_z_drzewa(&(**d).lewy,e);
else {
if ((**d).elem < e)
usun_z_drzewa(&(**d).prawy,e);
else {
q = *d;
if ((*q).lewy == NULL)
*d = (*q).prawy;
else {
if ((*q).prawy == NULL)
*d = (*q).lewy;
else
usun(&(*q).lewy);
}
free(q);
return(1);
}
}
} else
return(0);
}
r
dr
50
25
10
60
28
65
30
20
7
29
15
22
27
21
void usun(Tdrzewo* r) {
if ((**r).prawy != NULL)
usun(&(**r).prawy);
else {
(*q).elem = (**r).elem;
q = *r;
*r = (**r).lewy;
}
}
znalezienie skrajnego
prawego w lewym
poddrzewie
kopiowanie
znalezionego do
usuwanego
q
np.: usun_z_drzewa (dr, 25);
*r – adres wskaźnika (Tdrzewo jest
wskaźnikiem)
**r – struktura wskazywana przez
wskaźnik *r
(**r).prawy – pole struktury
&(**r).prawy – adres pola struktury
(wskaźnik)
r
dr
50
25
10
60
28
65
30
20
7
29
15
22
27
21
q
int usun_z_drzewa (Tdrzewo* d, Telem e)
{
if (*d != NULL) {
if ((**d).elem > e)
usun_z_drzewa(&(**d).lewy,e);
else {
if ((**d).elem < e)
usun_z_drzewa(&(**d).prawy,e);
else {
q = *d;
if ((*q).lewy == NULL)
*d = (*q).prawy;
else {
if ((*q).prawy == NULL)
*d = (*q).lewy;
else
usun(&(*q).lewy);
}
free(q);
return(1);
}
}
} else
return(0);
}
void usun(Tdrzewo* r) {
if ((**r).prawy != NULL)
usun(&(**r).prawy);
else {
(*q).elem = (**r).elem;
q = *r;
*r = (**r).lewy;
}
}
np.: usun_z_drzewa (dr, 25);
r
dr
50
22
10
60
28
65
30
20
7
29
15
22
27
21
q
int usun_z_drzewa (Tdrzewo* d, Telem e)
{
if (*d != NULL) {
if ((**d).elem > e)
usun_z_drzewa(&(**d).lewy,e);
else {
if ((**d).elem < e)
usun_z_drzewa(&(**d).prawy,e);
else {
q = *d;
if ((*q).lewy == NULL)
*d = (*q).prawy;
else {
if ((*q).prawy == NULL)
*d = (*q).lewy;
else
usun(&(*q).lewy);
}
free(q);
return(1);
}
}
} else
return(0);
}
void usun(Tdrzewo* r) {
if ((**r).prawy != NULL)
usun(&(**r).prawy);
else {
(*q).elem = (**r).elem;
q = *r;
*r = (**r).lewy;
}
}
np.: usun_z_drzewa (dr, 25);
r
dr
50
22
10
60
28
65
30
20
7
29
15
22
27
21
q
int usun_z_drzewa (Tdrzewo* d, Telem e)
{
if (*d != NULL) {
if ((**d).elem > e)
usun_z_drzewa(&(**d).lewy,e);
else {
if ((**d).elem < e)
usun_z_drzewa(&(**d).prawy,e);
else {
q = *d;
if ((*q).lewy == NULL)
*d = (*q).prawy;
else {
if ((*q).prawy == NULL)
*d = (*q).lewy;
else
usun(&(*q).lewy);
}
free(q);
return(1);
}
}
} else
return(0);
}
void usun(Tdrzewo* r) {
if ((**r).prawy != NULL)
usun(&(**r).prawy);
else {
(*q).elem = (**r).elem;
q = *r;
*r = (**r).lewy;
}
}
np.: usun_z_drzewa (dr, 25);
dr
50
22
10
60
28
65
30
20
7
29
15
22
27
21
q
int usun_z_drzewa (Tdrzewo* d, Telem e)
{
if (*d != NULL) {
if ((**d).elem > e)
usun_z_drzewa(&(**d).lewy,e);
else {
if ((**d).elem < e)
usun_z_drzewa(&(**d).prawy,e);
else {
q = *d;
if ((*q).lewy == NULL)
*d = (*q).prawy;
else {
if ((*q).prawy == NULL)
*d = (*q).lewy;
else
usun(&(*q).lewy);
}
free(q);
return(1);
}
}
} else
return(0);
}
void usun(Tdrzewo* r) {
if ((**r).prawy != NULL)
usun(&(**r).prawy);
else {
(*q).elem = (**r).elem;
q = *r;
*r = (**r).lewy;
}
}
np.: usun_z_drzewa (dr, 25);
dr
50
22
10
60
28
65
30
20
7
29
15
22
27
21
q
int usun_z_drzewa (Tdrzewo* d, Telem e)
{
if (*d != NULL) {
if ((**d).elem > e)
usun_z_drzewa(&(**d).lewy,e);
else {
if ((**d).elem < e)
usun_z_drzewa(&(**d).prawy,e);
else {
q = *d;
if ((*q).lewy == NULL)
*d = (*q).prawy;
else {
if ((*q).prawy == NULL)
*d = (*q).lewy;
else
usun(&(*q).lewy);
}
free(q);
return(1);
}
}
} else
return(0);
}
np.: usun_z_drzewa (dr, 25);
dr
50
22
10
60
28
65
30
20
7
29
15
27
21
q
int usun_z_drzewa (Tdrzewo* d, Telem e)
{
if (*d != NULL) {
if ((**d).elem > e)
usun_z_drzewa(&(**d).lewy,e);
else {
if ((**d).elem < e)
usun_z_drzewa(&(**d).prawy,e);
else {
q = *d;
if ((*q).lewy == NULL)
*d = (*q).prawy;
else {
if ((*q).prawy == NULL)
*d = (*q).lewy;
else
usun(&(*q).lewy);
}
free(q);
return(1);
}
}
} else
return(0);
}
np.: usun_z_drzewa (dr, 25);
dr
50
22
10
60
28
65
30
20
7
29
15
27
21
Struktury danych - drzewa
Pakiet przykładowych
operacji
/* drzewo.h */
#if !defined(__drzewo_H)
#define __drzewo_H
typedef int Telem;
typedef struct Telem_drzewa {
Telem_drzewa* lewy;
Telem_drzewa* prawy;
Telem elem;
};
typedef Telem_drzewa* Tdrzewo;
void wstaw_do_drzewa (Tdrzewo* d, Telem e);
void usun_drzewo (Tdrzewo* d);
int usun_z_drzewa (Tdrzewo* d, Telem e);
#define _skok 4
void wypisz_drzewo (Tdrzewo d, int odl);
void wypisz_elem (Telem e);
#endif /* __drzewo_H */
Document Outline
- Slide 1
- Slide 2
- Slide 3
- Slide 4
- Slide 5
- Slide 6
- Slide 7
- Slide 8
- Slide 9
- Slide 10
- Slide 11
- Slide 12
- Slide 13
- Slide 14
- Slide 15
- Slide 16
- Slide 17
- Slide 18
- Slide 19
- Slide 20
- Slide 21
- Slide 22
- Slide 23
- Slide 24
- Slide 25
- Slide 26
- Slide 27
- Slide 28
- Slide 29
- Slide 30
- Slide 31
- Slide 32
- Slide 33
- Slide 34
- Slide 35
- Slide 36
- Slide 37
- Slide 38
- Slide 39
- Slide 40
- Slide 41
- Slide 42
- Slide 43
- Slide 44
- Slide 45
- Slide 46
- Slide 47
- Slide 48
- Slide 49
- Slide 50
Wyszukiwarka
Podobne podstrony:
AiSD wykład listy (procedury)
AiSD Wyklad4 dzienne id 53497 Nieznany (2)
AiSD wyklad 3
AiSD Wyklad9 dzienne id 53501 Nieznany
AiSD Wyklad2 dzienne
AiSD Wyklad1 dzienne
AiSD wyklad 1 id 53489 Nieznany
AiSD Wyklad11 dzienne id 53494 Nieznany
Wykład 4 Alarmy i procedury SAR na statku AAA
Algorytmy i struktury danych AiSD-C-Wyklad05
AiSD wyklad 5
AiSD Wyklad1 dzienne
AiSD Wyklad6 dzienne id 53499 Nieznany (2)
AiSD Wyklad7 dzienne id 53500 Nieznany (2)
AiSD wyklad 9 id 53492 Nieznany (2)
AiSD Wyklad3 dzienne id 53496 Nieznany (2)
Algorytmy i struktury danych, AiSD C Wyklad04 2
procedury budżetowe wykłady, FiR, Procedury Budżetowe
więcej podobnych podstron