ÿþD r z e w a w y s z u k i w a D b i n a r n y c h ( B S T )
K r z y s z t o f G r z d z i e l
1 2 c z e r w c a 2 0 0 7 r o k u
1 D r z e w a B i n a r n e
D r z e w a w y s z u k i w a D b i n a r n y c h , w s k r ó c i e B S T ( o d a n g . b i n a r y s e a r c h t r e e s ) , t o s z c z e -
g ó l n y p r z y p a d e k d r z e w b i n a r n y c h . S t o s t r u k t u r y , n a k t ó r y c h m o |n a w y k o n y w a r ó |n e
o p e r a c j e w Ba [c i w e d l a z b i o r ó w d y n a m i c z n y c h , t a k i e j a k S E A R C H , M I N I M U M , M A -
X I M U M , P R E D E C E S S O R , S U C C E S S O R , I N S E R T , D E L E T E . D r z e w o w y s z u -
k i w a D m o |e w i c b y u |y t e z a r ó w n o j a k o s Bo w n i k , j a k i j a k o k o l e j k a p r i o r y t e t o w a .
P o d s t a w o w e o p e r a c j e n a d r z e w a c h w y s z u k i w a D b i n a r n y c h w y m a g a j c z a s u p r o p o r c j o -
n a l n e g o d o w y s o k o [c i d r z e w a . W p e Bn y m d r z e w i e b i n a r n y m o n w z Ba c h t a k i e o p e r a c j e
d z i a Ba j w p r z y p a d k u p e s y m i s t y z c z n y m w c z a s i e ¸( l g n ) . J e [l i j e d n a k d r z e w o s k Ba d a s i z
j e d n e j g a Be z i o d Bu g o [c i n , t o t e s a m e o p e r a c j e w y m a g a j w p r z y p a d k u p e s y m i s t y c z n y m
c z a s u ¸( n ) .
1 . 1 C o t o j e s t d r z e w o w y s z u k i w a D b i n a r n y c h ?
R y s u n e k 1 : D r z e w o p o s z u k i w a D b i n a r n y c h o w a d z e r ó w n e j 9 , a w y s o k o [c i r ó w n e j 3 ; w i e r z c h o Be k
8 j e s t t u k o r z e n i e m , a w i e r z c h o Bk i 1 , 4 , 7 i 1 3 , t o l i [c i e .
D r z e w o w y s z u k i w a D b i n a r n y c h , m a s t r u k t u r d r z e w a b i n a r n e g o . T a k i e d r z e w a m o |n a
z r e a l i z o w a z a p o m o c s t r u k t u r y d a n y c h z d o w i z a n i a m i , w k t ó r e j k a |d y w z e B j e s t o b i e k -
t e m . O p r ó c z p o l a k e y ( e w . d a n y c h d o d a t k o w y c h ) , k a |d y w z e B z a w i e r a p o l a l e f t , r i g h t ,
o r a z p ( p a r e n t ) , k t ó r e w s k a z u j , o d p o w i e d n i o , n a j e g o l e w e g o s y n a , p r a w e g o s y n a , o r a z
r o d z i c a . J e [l i w z e B n i e m a n a s t p n i k a a l b o p o p r z e d n i k a , t o o d p o w i e d n i e p o l e m a w a r t o [
1
N I L . W z e B w k o r z e n i u d r z e w a j e s t j e d y n y m w z Be m , k t ó r e g o p o l e w s k a z u j c e n a o j c a
m a w a r t o [ N I L .
K l u c z e s p r z e c h o w y w a n e w d r z e w i e B S T w t a k i s p o s ó b , a l e s p e Bn i o n a b y Ba w Ba s n o [
d r z e w a B S T :
N i e c h x b d z i e w z Be m d r z e w a B S T . J e [l i y j e s t w z Be m z n a j d u j c y m s i w l e -
w y m p o d d r z e w i e w z Ba x , t o k e y [ y ] k e y [ x ] . J e [l i y j e s t w z Be m z n a j d u j c y m
s i w p r a w y m p o d d r z e w i e w z Ba x , t o k e y [ y ] k e y [ x ] .
1 . 2 W y b r a n e z Bo |o n o [c i
W y p i s a n i e d r z e w a ¸( n )
W y s z u k a n i e O ( h )
Z n a j d o w a n i e m i n i m u m O ( h )
Z n a j d o w a n i e m a k s i m u m O ( h )
Z n a j d o w a n i e p o p r z e d n i k a O ( h )
Z n a j d o w a n i e n a s t p n i k a O ( h )
W s t a w i a n i e O ( h )
U s u w a n i e O ( h )
g d z i e n - i l o [ w z Bó w w d r z e w i e , h - w y s o k o [ d r z e w a
2 F u n k c j e
2 . 1 e c h o
v o i d e c h o ( B S T * r o o t )
W y p i s u j e n a s t a n d a r d o w e w y j [c i e k e y d a n e g o w z Ba .
P a r a m e t r y :
r o o t - w s k a z n i k t o k o r z e n i a
2 . 2 i n o r d e r
v o i d i n o r d e r ( B S T * r o o t )
P r z e c h o d z e n i e d r z e w a B S T m e t o d a i n o r d e r . K l u c z d r z e w a z o s t a j e w y p i s a n y m i -
d z y w a r t o [c i a m i j e g o l e w e g o p o d d r z e w a , a w a r t o [c i a m i z j e g o p r a w e g o p o d d r z e w a .
P a r a m e t r y :
r o o t - w s k a z n i k t o k o r z e n i a
2 . 3 p r e o r d e r
v o i d p r e o r d e r ( B S T * r o o t )
P r z e c h o d z e n i e d r z e w a B S T m e t o d a p r e o r d e r . W y p i s u j e k l u c z k o r z e n i a p r z e d w y -
p i s a n i e m w a r t o [c i z n a j d u c y c h s i w o b u p o d d r z e w a c h .
2
P a r a m e t r y :
r o o t - w s k a z n i k t o k o r z e n i a
2 . 4 p o s t o r d e r
v o i d p o s t o r d e r ( B S T * r o o t )
P r z e c h o d z e n i e d r z e w a B S T m e t o d a p o s t o r d e r . W y p i s u j e k l u c z k o r z e n i a p o w y p i -
s a n i u w a r t o [c i z n a j d u c y c h s i w o b u p o d d r z e w a c h .
P a r a m e t r y :
r o o t - w s k a z n i k t o k o r z e n i a
2 . 5 p o s t o r d e r i n v e r s e
v o i d p o s t o r d e r i n v e r s e ( B S T * r o o t )
P r z e c h o d z e n i e d r z e w a B S T m e t o d a o d w r o t n d o p r e o r d e r . W y p i s u j e k l u c z e k o -
r z e n i a w k o l e j n o [c i o d w r o t n e j d o p r e o r d e r .
P a r a m e t r y :
r o o t - w s k a z n i k t o k o r z e n i a
2 . 6 s e a r c h
B S T * s e a r c h ( B S T * r o o t , i n t v a l )
W y s z u k i w a n i e w z Ba ( r e k u r e n c y j n i e ) , k t ó r y z a w i e r a k l u c z v a l .
P a r a m e t r y :
r o o t - w s k a z n i k t o k o r z e n i a v a l - s z u k a n y k l u c z
2 . 7 i s e a r c h
B S T * i s e a r c h ( B S T * r o o t , i n t v a l )
I t e r a c y j n e w y s z u k i w a n i e w z Ba , k t ó r y z a w i e r a k l u c z v a l .
U w a g a !
E f e k t y w n i e j s z e o d s e r a c h ( B S T * , i n t ) ;
P a r a m e t r y :
r o o t - w s k a z n i k t o k o r z e n i a v a l - s z u k a n y k l u c z
2 . 8 m i n
B S T * m i n ( B S T * r o o t )
Z n a j d o w a n i e n a j m n i e j s z e j w a r t o [c i w d r z e w i e .
P a r a m e t r y :
r o o t - w s k a z n i k t o k o r z e n i a
3
2 . 9 m a x
B S T * m a x ( B S T * r o o t )
Z n a j d o w a n i e n a j w i k s z e j w a r t o [c i w d r z e w i e .
P a r a m e t r y :
r o o t - w s k a z n i k t o k o r z e n i a
2 . 1 0 t r a c e
v o i d t r a c e ( B S T * r o o t , i n t v 1 , i n t v 2 )
Z n a j d u j e d r o g e p o m i e d z y d w o m a k l u c z a m i .
P a r a m e t r y :
r o o t - w s k a z n i k t o k o r z e n i a v 1 - k l u c z p o c z t k o w y v 2 - k l u c z k o Dc o w y
2 . 1 1 d r a w
v o i d d r a w ( B S T * r o o t )
R y s u j e d r z e w o .
P a r a m e t r y :
r o o t - w s k a z n i k t o k o r z e n i a
2 . 1 2 n a s t e p n i k
B S T * n a s t e p n i k ( B S T * r o o t )
Z n a j d u j e n a s t p n i k d a n e g o w z Ba .
P a r a m e t r y :
r o o t - w s k a z n i k t o w z Ba
2 . 1 3 p o p r z e d n i k
B S T * p o p r z e d n i k ( B S T * r o o t )
Z n a j d u j e p o p r z e d n i k a d a n e g o w z Ba .
P a r a m e t r y :
r o o t - w s k a z n i k t o w z Ba
2 . 1 4 d e l
B S T * d e l ( B S T * r o o t , i n t v a l )
U s u w a w z e B o d a n y m k l u c z u v a l .
P a r a m e t r y :
r o o t - w s k a z n i k t o k o r z e n i a v a l - w a r t o [ k l u c z a
4
2 . 1 5 a d d
B S T * a d d ( B S T * r o o t , i n t v a l )
D o d a j e w z e B o k l u c z u v a l d o d r z e w a w y s z u k i w a D b i n a r n y c h .
P a r a m e t r y :
r o o t - w s k a z n i k t o k o r z e n i a v a l - w a r t o [ k l u c z a
2 . 1 6 w a g a
i n t w a g a ( B S T * r o o t )
Z w r a c a i l o [ w z Bó w w d r z e w i e .
P a r a m e t r y :
r o o t - w s k a z n i k t o k o r z e n i a
3 I m p l e m e n t a c j a
3 . 1 P l i k n a g Bó w k o w y
L i s t i n g 1 : b s t . h
1 # i f n d e f I N C B S T H
2 # d e f i n e I N C B S T H
3
4 t y p e d e f s t r u c t d r z e w o B S T ;
5 s t r u c t d r z e w o {
6 i n t k e y ;
7 B S T " l e f t ;
8 B S T " r i g h t ;
9 B S T "p ; / / p a r e n t
1 0 } ;
1 1
1 2 e x t e r n v o i d e c h o ( B S T " r o o t ) ;
1 3 e x t e r n v o i d i n o r d e r ( B S T " r o o t ) ;
1 4 e x t e r n v o i d p r e o r d e r ( B S T " r o o t ) ;
1 5 e x t e r n v o i d p o s t o r d e r ( B S T " r o o t ) ;
1 6 e x t e r n v o i d p o s t o r d e r i n v e r s e ( B S T " r o o t ) ;
1 7 e x t e r n B S T " s e a r c h ( B S T " r o o t , i n t v a l ) ;
1 8 e x t e r n B S T " i s e a r c h ( B S T " r o o t , i n t v a l ) ;
1 9 e x t e r n B S T "m i n ( B S T " r o o t ) ;
2 0 e x t e r n B S T "m a x ( B S T " r o o t ) ;
2 1 e x t e r n v o i d t r a c e ( B S T " r o o t , i n t v 1 , i n t v 2 ) ;
2 2 e x t e r n v o i d d r a w ( B S T " r o o t ) ;
2 3 e x t e r n B S T " n a s t e p n i k ( B S T " r o o t ) ;
2 4 e x t e r n B S T " p o p r z e d n i k ( B S T " r o o t ) ;
2 5 e x t e r n B S T " d e l ( B S T " r o o t , i n t v a l ) ;
2 6 e x t e r n B S T "a d d ( B S T " r o o t , i n t v a l ) ;
2 7 e x t e r n i n t w a g a ( B S T " r o o t ) ;
2 8
2 9 # e n d i f
3 . 2 F u n k c j e d r z e w a B S T
L i s t i n g 2 : I m p l e m e n t a c j a o p e r a c j i n a d r z e w i e B S T ( b s t . c )
1 # i n c l u d e < s t d i o . h >
2 # i n c l u d e < m a l l o c . h >
3 # i n c l u d e b s t . h
4
5 / / w y s w i e t l a k e y z p o d a n e g o w s k a z n i k a
6 v o i d e c h o ( B S T " r o o t ) {
5
7 i f ( r o o t ! = N U L L ) p r i n t f ( % d \ n , r o o t - > k e y ) ;
8 e l s e p r i n t f ( b r a k \ n ) ;
9 r e t u r n ;
1 0 }
1 1
1 2 / / w y p i s u j e d r z e w o w p o r z a d k u i n o d e r ( p o s o r t o w a n e r o s n a c o )
1 3 v o i d i n o r d e r ( B S T " r o o t ) {
1 4 i f ( r o o t ! = N U L L ) {
1 5 i n o r d e r ( r o o t - > l e f t ) ;
1 6 p r i n t f ( % d , r o o t - > k e y ) ;
1 7 i n o r d e r ( r o o t - > r i g h t ) ;
1 8 }
1 9 r e t u r n ;
2 0 }
2 1
2 2 / / w y p i s y w a n i e d r z e w a w p o r z a d k u p r e o r d e r
2 3 v o i d p r e o r d e r ( B S T " r o o t ) {
2 4 i f ( r o o t ! = N U L L ) {
2 5 p r i n t f ( % d , r o o t - > k e y ) ;
2 6 p r e o r d e r ( r o o t - > l e f t ) ;
2 7 p r e o r d e r ( r o o t - > r i g h t ) ;
2 8 }
2 9 r e t u r n ;
3 0 }
3 1
3 2 / / w y p i s y w a n i e d r z e w a w p o r z a d k u p o s t o r d e r
3 3 v o i d p o s t o r d e r ( B S T " r o o t ) {
3 4 i f ( r o o t ! = N U L L ) {
3 5 p o s t o r d e r ( r o o t - > l e f t ) ;
3 6 p o s t o r d e r ( r o o t - > r i g h t ) ;
3 7 p r i n t f ( % d , r o o t - > k e y ) ;
3 8 }
3 9 r e t u r n ;
4 0 }
4 1
4 2 / / w y p i s y w a n i e d r z e w a w p o r z a d k u o d w r o t n y m d o p o s t o r d e r
4 3 v o i d p o s t o r d e r i n v e r s e ( B S T " r o o t ) {
4 4 i f ( r o o t ! = N U L L ) {
4 5 p r i n t f ( % d , r o o t - > k e y ) ;
4 6 p o s t o r d e r i n v e r s e ( r o o t - > r i g h t ) ;
4 7 p o s t o r d e r i n v e r s e ( r o o t - > l e f t ) ;
4 8 }
4 9 r e t u r n ;
5 0 }
5 1
5 2 / / s z u k a n i e r e k u r e n c y j n e
5 3 B S T " s e a r c h ( B S T " r o o t , i n t v a l ) {
5 4 i f ( ( r o o t = = N U L L ) | | ( v a l = = r o o t - > k e y ) ) r e t u r n r o o t ;
5 5 i f ( v a l < r o o t - > k e y ) {
5 6 r e t u r n s e a r c h ( r o o t - > l e f t , v a l ) ;
5 7 }
5 8 e l s e {
5 9 r e t u r n s e a r c h ( r o o t - > r i g h t , v a l ) ;
6 0 }
6 1 r e t u r n r o o t ;
6 2 }
6 3
6 4 / / p r z e s z u k i w a n i e i t e r a c y j n e ( e f e k t y w n i e j s z e )
6 5 B S T " i s e a r c h ( B S T " r o o t , i n t v a l ) {
6 6 w h i l e ( ( r o o t ! = N U L L ) & & ( v a l ! = r o o t - > k e y ) ) {
6 7 i f ( v a l < r o o t - > k e y ) r o o t = r o o t - > l e f t ;
6 8 e l s e r o o t = r o o t - > r i g h t ;
6 9 }
7 0 r e t u r n r o o t ;
7 1 }
7 2
7 3 / / z n a j d o w a n i e m i n i m u m
7 4 B S T "m i n ( B S T " r o o t ) {
7 5 w h i l e ( r o o t - > l e f t ! = N U L L ) {
7 6 r o o t = r o o t - > l e f t ;
7 7 }
7 8 r e t u r n r o o t ;
7 9 }
6
8 0
8 1 / / z n a j d o w a n i e m a k s i m u m
8 2 B S T "m a x ( B S T " r o o t ) {
8 3 w h i l e ( r o o t - > r i g h t ! = N U L L ) {
8 4 r o o t = r o o t - > r i g h t ;
8 5 }
8 6 r e t u r n r o o t ;
8 7 }
8 8
8 9 / / w s k a z y w a n i e d r o g i p o m i e d z y d w o m a e l e m e n t a m i
9 0 v o i d t r a c e ( B S T " r o o t , i n t v 1 , i n t v 2 ) {
9 1 B S T " x = i s e a r c h ( r o o t , v 1 ) ;
9 2 B S T " y = i s e a r c h ( r o o t , v 2 ) ;
9 3
9 4 i f ( v 1 > v 2 ) {
9 5 i n t t m p = v 2 ;
9 6 v 2 = v 1 ;
9 7 v 1 = t m p ;
9 8 }
9 9 / / p r i n t f ( \ t k e y : % d \ n , r o o t - > k e y ) ;
1 0 0 i f ( r o o t = = N U L L | | x = = N U L L | | y = = N U L L ) {
1 0 1 p r i n t f ( b r a k d r o g i ) ;
1 0 2 }
1 0 3 e l s e {
1 0 4 i f ( v 1 < r o o t - > k e y & & v 2 < r o o t - > k e y ) {
1 0 5 t r a c e ( r o o t - > l e f t , v 1 , v 2 ) ;
1 0 6 }
1 0 7 i f ( v 1 > r o o t - > k e y & & v 2 > r o o t - > k e y ) {
1 0 8 t r a c e ( r o o t - > r i g h t , v 1 , v 2 ) ;
1 0 9 }
1 1 0 i f ( v 1 < = r o o t - > k e y & & v 2 > = r o o t - > k e y ) {
1 1 1 w h i l e ( x ! = r o o t ) {
1 1 2 p r i n t f ( % d , x - > k e y ) ;
1 1 3 x = x - > p ;
1 1 4 }
1 1 5 p r i n t f ( % d , x - > k e y ) ;
1 1 6 w h i l e ( r o o t ! = y ) {
1 1 7 i f ( y - > k e y < r o o t - > k e y ) {
1 1 8 r o o t = r o o t - > l e f t ;
1 1 9 p r i n t f ( % d , r o o t - > k e y ) ;
1 2 0 }
1 2 1 i f ( y - > k e y > r o o t - > k e y ) {
1 2 2 r o o t = r o o t - > r i g h t ;
1 2 3 p r i n t f ( % d , r o o t - > k e y ) ;
1 2 4 }
1 2 5 }
1 2 6 }
1 2 7 }
1 2 8 }
1 2 9
1 3 0 / / r y s u j e d r z e w o
1 3 1 v o i d d r a w ( B S T " r o o t ) {
1 3 2 i f ( r o o t ! = N U L L ) {
1 3 3 p r i n t f ( % - 3 d , r o o t - > k e y ) ;
1 3 4 i f ( r o o t - > l e f t = = N U L L & & r o o t - > r i g h t = = N U L L ) ;
1 3 5 e l s e {
1 3 6 p r i n t f ( ( ) ;
1 3 7 i f ( r o o t - > l e f t ! = N U L L ) p r i n t f ( % - 3 d , , r o o t - > l e f t - > k e y ) ; e l s e p r i n t f ( .
, ) ;
1 3 8 i f ( r o o t - > r i g h t ! = N U L L ) p r i n t f ( % 3 d , r o o t - > r i g h t - > k e y ) ; e l s e p r i n t f (
. ) ;
1 3 9 p r i n t f ( ) ) ;
1 4 0 }
1 4 1 p r i n t f ( \ n ) ;
1 4 2 }
1 4 3 i f ( r o o t - > l e f t ! = N U L L ) d r a w ( r o o t - > l e f t ) ;
1 4 4 i f ( r o o t - > r i g h t ! = N U L L ) d r a w ( r o o t - > r i g h t ) ;
1 4 5 }
1 4 6
1 4 7 / / s u c c e s s o r
1 4 8 B S T " n a s t e p n i k ( B S T " r o o t ) {
1 4 9 B S T " y = r o o t ;
1 5 0
7
1 5 1 / / e x c e p t i o n
1 5 2 i f ( r o o t = = N U L L ) r e t u r n y ;
1 5 3
1 5 4 i f ( r o o t - > r i g h t ! = N U L L ) {
1 5 5 r e t u r n m i n ( r o o t - > r i g h t ) ;
1 5 6 }
1 5 7 y = r o o t - > p ;
1 5 8 w h i l e ( y ! = N U L L & & r o o t = = y - > r i g h t ) {
1 5 9 r o o t = y ;
1 6 0 y = y - > p ;
1 6 1 }
1 6 2 r e t u r n y ;
1 6 3 }
1 6 4
1 6 5 / / p r e d e c e s s o r
1 6 6 B S T " p o p r z e d n i k ( B S T " r o o t ) {
1 6 7 B S T " y = r o o t ;
1 6 8
1 6 9 / / e x c e p t i o n
1 7 0 i f ( r o o t = = N U L L ) r e t u r n y ;
1 7 1
1 7 2 i f ( r o o t - > l e f t ! = N U L L ) {
1 7 3 r e t u r n m a x ( r o o t - > l e f t ) ;
1 7 4 }
1 7 5 y = r o o t - > p ;
1 7 6 w h i l e ( y ! = N U L L & & r o o t = = y - > l e f t ) {
1 7 7 r o o t = y ;
1 7 8 y = y - > p ;
1 7 9 }
1 8 0 r e t u r n y ;
1 8 1 }
1 8 2
1 8 3 / / u s u w a n i e
1 8 4 B S T " d e l ( B S T " r o o t , i n t v a l ) {
1 8 5 / / w s k a z n i k i p o m o c n i c z e
1 8 6 B S T " x = r o o t ;
1 8 7 B S T " y = ( B S T ") m a l l o c ( s i z e o f ( B S T ) ) ;
1 8 8 / / t o c o u s u w a m y
1 8 9 B S T " d e l = s e a r c h ( r o o t , v a l ) ;
1 9 0
1 9 1 i f ( d e l = = N U L L ) r e t u r n y ;
1 9 2
1 9 3 i f ( d e l - > l e f t = = N U L L | | d e l - > r i g h t = = N U L L ) y = d e l ;
1 9 4 e l s e y = n a s t e p n i k ( d e l ) ;
1 9 5
1 9 6 i f ( y - > l e f t ! = N U L L ) x = y - > l e f t ;
1 9 7 e l s e x = y - > r i g h t ;
1 9 8
1 9 9 i f ( x ! = N U L L ) x - > p = y - > p ;
2 0 0
2 0 1 i f ( y - > p = = N U L L ) r o o t = x ;
2 0 2 e l s e i f ( y = = y - > p - > l e f t ) y - > p - > l e f t = x ;
2 0 3 e l s e y - > p - > r i g h t = x ;
2 0 4
2 0 5 i f ( y ! = d e l ) {
2 0 6 d e l - > k e y = y - > k e y ;
2 0 7 }
2 0 8 r e t u r n y ;
2 0 9 }
2 1 0
2 1 1 / / d o d a w a n i e
2 1 2 B S T "a d d ( B S T " r o o t , i n t v a l ) {
2 1 3 B S T "x = r o o t ;
2 1 4
2 1 5 / / n o w y o b i e k t , k t o r y w p i n a n y j e s t d o d r z e w a
2 1 6 B S T "n o w e = ( B S T ") m a l l o c ( s i z e o f ( B S T ) ) ;
2 1 7 n o w e - > k e y = v a l ;
2 1 8 n o w e - > p = n o w e - > l e f t = n o w e - > r i g h t = N U L L ;
2 1 9
2 2 0 B S T "y = N U L L ;
2 2 1 w h i l e ( x ! = N U L L ) {
2 2 2 y = x ;
2 2 3 i f ( v a l < x - > k e y ) x = x - > l e f t ;
8
2 2 4 e l s e x = x - > r i g h t ;
2 2 5 }
2 2 6 n o w e - > p = y ;
2 2 7 i f ( y = = N U L L ) r o o t = n o w e ;
2 2 8 e l s e {
2 2 9 i f ( n o w e - > k e y < y - > k e y ) y - > l e f t = n o w e ;
2 3 0 e l s e y - > r i g h t = n o w e ;
2 3 1 }
2 3 2 r e t u r n r o o t ;
2 3 3 }
2 3 4
2 3 5 / / o b l i c z a i l o s c w e z l o w w d r z e w i e
2 3 6 i n t w a g a ( B S T " r o o t ) {
2 3 7 i f ( r o o t = = N U L L ) r e t u r n 0 ;
2 3 8 e l s e r e t u r n w a g a ( r o o t - > l e f t ) + w a g a ( r o o t - > r i g h t ) + 1 ;
2 3 9 }
3 . 3 P r z y k Ba d u |y c i a
L i s t i n g 3 : P r z y k Ba d u |y c i a
1 # i n c l u d e < s t d i o . h >
2 # i n c l u d e < m a l l o c . h >
3 # i n c l u d e b s t . h
4
5 i n t m a i n ( ) {
6 B S T " t r e e = N U L L ;
7
8 t r e e = a d d ( t r e e , 1 5 ) ;
9 t r e e = a d d ( t r e e , 6 ) ;
1 0 t r e e = a d d ( t r e e , 3 ) ;
1 1 t r e e = a d d ( t r e e , 7 ) ;
1 2 t r e e = a d d ( t r e e , 2 ) ;
1 3 t r e e = a d d ( t r e e , 4 ) ;
1 4 t r e e = a d d ( t r e e , 1 3 ) ;
1 5 t r e e = a d d ( t r e e , 9 ) ;
1 6 t r e e = a d d ( t r e e , 1 8 ) ;
1 7 t r e e = a d d ( t r e e , 1 7 ) ;
1 8 t r e e = a d d ( t r e e , 2 0 ) ;
1 9
2 0 p r i n t f ( i n o r d e r ( ) : ) ;
2 1 i n o r d e r ( t r e e ) ;
2 2 p r i n t f ( \ n p o s t o r d e r ( ) : ) ;
2 3 p o s t o r d e r ( t r e e ) ;
2 4 p r i n t f ( \ n p o s t o r d e r i n v e r s e ( ) : ) ;
2 5 p o s t o r d e r i n v e r s e ( t r e e ) ;
2 6 p r i n t f ( \ n p r e o r d e r ( ) : ) ;
2 7 p r e o r d e r ( t r e e ) ;
2 8 p r i n t f ( \ n s e a r c h ( 2 ) : ) ;
2 9 s e a r c h ( t r e e , 2 ) ;
3 0 p r i n t f ( \ n s e a r c h ( 7 ) : ) ;
3 1 s e a r c h ( t r e e , 7 ) ;
3 2 p r i n t f ( \ n m i n ( 7 ) : ) ;
3 3 e c h o ( m i n ( t r e e ) ) ;
3 4 p r i n t f ( m a x ( 7 ) : ) ;
3 5 e c h o ( m a x ( t r e e ) ) ;
3 6 i n t n s t = 1 5 ;
3 7 p r i n t f ( N a s t e p n i k % d : , n s t ) ;
3 8 e c h o ( n a s t e p n i k ( s e a r c h ( t r e e , n s t ) ) ) ;
3 9 p r i n t f ( P o p r z e d n i k % d : , n s t ) ;
4 0 e c h o ( p o p r z e d n i k ( s e a r c h ( t r e e , n s t ) ) ) ;
4 1 d e l ( t r e e , n s t ) ;
4 2 p r i n t f ( W a g a d r z e w a : % d \ n , w a g a ( t r e e ) ) ;
4 3 p r i n t f ( D r o g a ( 1 7 , 2 0 ) : ) ;
4 4 t r a c e ( t r e e , 1 7 , 2 0 ) ;
4 5 p r i n t f ( \ n D r o g a ( 2 0 , 1 7 ) : ) ;
4 6 t r a c e ( t r e e , 2 0 , 1 7 ) ;
4 7 p r i n t f ( \ n D r o g a ( 2 0 , 2 6 ) : ) ;
4 8 t r a c e ( t r e e , 2 0 , 2 6 ) ;
4 9 p r i n t f ( \ n ) ;
5 0 r e t u r n 0 ;
5 1 }
9
L i t e r a t u r a
[ 1 ] T h o m a s H . C o r m e n , C h a r l e s E . L e i s e r s o n , R o n a l d L . R i v e s t , C l i f f o r d S t e i n , W p r o -
w a d z e n i e d o a l g o r y t m ó w , W N T , W a r s z a w a 2 0 0 5 .
1 0
Wyszukiwarka
Podobne podstrony:
Kopia 48 Trójkąt na RodosDziałanie prądu elektrycznego na organizm człowieka KopiaPozwolenie na wycięcie drzewa jak uzyskać, kto wydaje, kiedy nie jest wymaganePozwolenie na wycięcie drzewa jak uzyskać, kto wydaje, kiedy nie jest wymaganeKopia systemu na płycie CD [d 2007]Podanie o zezwolenie na wycięcie drzewaGNN SPRAWOZDANIE NR 2 WNIOSEK O WYDANIE ZEZWOLENIA NA USUNIĘCIE DRZEWA LUB KRZEWÓWChińska kopia Mercedesa wejdzie na rynekzestawy cwiczen przygotowane na podstawie programu Mistrz Klawia 6PKC pytania na egzaminwięcej podobnych podstron