Trees and Binary Trees in Data Structures
UNIT-III
D
e
finition
o
f
T
r
ee
A
t
r
ee
is
a
f
i
n
i
t
e
s
e
t
of
one
or
m
o
r
e
nodes
such
t
h
a
t
:
The
r
e
is
a
spe
c
i
a
l
l
y
d
e
si
g
n
at
ed
node
c
a
l
led
t
he
r
oot.
T
h
e
r
e
m
a
i
n
i
ng
nodes
a
r
e
p
a
r
t
i
t
i
oned
i
n
t
o
n>=0
d
i
sjo
i
n
t
s
e
t
s
T1,
...
,
T
n
,
w
he
r
e
each
of
t
hese
s
e
t
s
is
a
t
r
e
e
.
W
e
c
a
l
l
T1,
...
,
T
n
t
he
su
b
t
r
e
e
s
of
t
he
r
oot.
139
R
ep
r
ese
n
t
a
t
i
on
T
0
of
T
r
ee
Le
v
el
1
T
1
2
T
2
T
3
T
4
T
T
3
5
6
F
ig
.
T
r
e
e
1
140
T
ermin
o
l
o
gy
A
D
B
C
E
F
G
H
F
ig
.
T
r
e
e
2
141
R
O
O
T
:
T
h
is
is
t
h
e
un
i
qu
e
n
o
d
e
in
t
h
e
t
r
ee
t
o
w
h
i
c
h
f
u
r
t
h
er
s
ub
t
r
e
e
s
a
r
e
a
tt
ac
h
e
d
.in
th
e
a
b
o
v
e
f
ig
n
o
d
e
A
is
a
r
oo
t
n
o
d
e.
Deg
r
ee
of
t
h
e
n
ode:
T
h
e
t
o
t
al
nu
m
b
er
o
f
s
u
b
-t
r
e
e
s
a
tt
ac
h
ed
t
o
th
e
n
o
d
e
is
c
all
e
d
th
e
d
eg
r
ee
o
f
N
o
d
e
A
E
th
e
n
o
d
e.
d
eg
r
ee
3
0
Le
a
v
es:
T
h
ese
a
r
e
t
erm
i
n
al
n
o
d
es
of
t
h
e
t
r
e
e
.
T
h
e
n
o
d
es
w
i
t
h
d
eg
r
ee
0
a
r
e
al
w
a
y
s
th
e
le
a
f
n
o
d
es.
I
n
a
b
o
v
e
gi
v
en
t
r
ee
E,
F
,G,C
a
n
d
H
a
r
e
th
e
le
a
f
n
o
d
es.
I
n
t
er
n
al
n
o
d
es:
T
h
e
n
o
d
es
o
th
er
th
an
th
e
r
oo
t
n
o
d
e
a
n
d
th
e
le
a
v
es
a
r
e
c
all
e
d
th
e
i
n
t
er
n
al
n
o
d
es.
H
e
r
e
B
a
n
d
D
a
r
e
i
n
t
er
n
al
n
o
d
es.
142
P
a
r
e
n
t
n
o
d
es:
T
h
e
n
o
d
e
w
h
i
c
h
is
h
a
ving
f
u
r
t
h
er
s
u
b
-t
r
e
e
s
(
b
r
a
n
c
h
es
)
is
c
alled
t
h
e
p
a
r
e
n
t
n
o
d
e
o
f
th
o
se
s
u
b
-t
r
e
e
s.
In
th
e
gi
v
en
e
x
am
p
le
n
o
d
e
B
is
p
a
r
e
n
t
n
o
d
e
of
E,F
a
n
d
G
n
o
d
es.
P
r
e
d
e
c
essor:
W
h
ile
d
is
p
l
a
y
i
n
g
th
e
t
r
ee
,if
so
m
e
p
ar
t
i
c
u
lar
n
o
d
e
o
cc
u
r
s
p
r
ev
i
o
u
s
t
o
some
o
t
h
er
n
o
d
e
t
h
en
t
h
a
t
n
o
d
e
is
c
alled
t
h
e
p
r
e
d
eces
s
or
of
t
h
e
o
t
h
er
n
o
d
e.In
a
b
o
v
e
f
ig
u
r
e
E
is
a
p
r
e
d
ecessor
o
f
th
e
n
o
d
e
B
.
s
u
c
c
essor:
T
h
e
n
o
d
e
w
h
i
c
h
o
cc
u
r
s
n
e
x
t
t
o
so
m
e
o
th
er
n
o
d
e
is
a
s
u
cc
ess
o
r
a
b
o
v
e
f
igu
r
e
B
is
s
u
cc
essor
of
F
a
n
d
G.
L
e
v
el
o
f
t
h
e
t
r
ee:
n
o
d
e.In
T
h
e
r
oo
t
n
o
d
e
is
al
w
a
y
s
c
o
n
si
d
e
r
ed
a
t
le
v
el
0
,
th
en
i
t
s
a
d
jace
n
t
c
h
il
d
r
en
a
r
e
s
upp
osed
t
o
b
e
a
t
le
v
el
1
a
n
d
so
o
n
.
I
n
a
b
o
v
e
f
igu
r
e
t
h
e
n
o
d
e
A
is
a
t
le
v
el
0
,
th
e
n
o
d
es
B
,C
,
D
a
r
e
a
t
le
v
el
1
,
th
e
n
o
d
es
E,
F
,G,H
a
r
e
a
t
le
v
el
2.
143
Heig
h
t
of
t
h
e
t
r
ee:
T
h
e
m
a
x
im
u
m
le
v
el
is
th
e
h
eig
h
t
o
f
th
e
t
r
e
e
.
H
e
r
e
h
eig
h
t
o
f
th
e
t
r
ee
is
3
.
T
h
e
h
eig
h
t
of
t
h
e
t
r
ee
is
also
c
alled
d
e
pt
h
of
t
h
e
t
r
e
e
.
Deg
r
ee
o
f
t
r
ee:
T
h
e
m
a
x
im
u
m
d
eg
r
ee
o
f
th
e
n
o
d
e
is
c
all
e
d
th
e
d
eg
r
ee
o
f
th
e
t
r
e
e
.
T
h
e
d
eg
r
ee
o
f
a
n
o
d
e
is
th
e
nu
m
b
er
o
f
s
u
bt
r
e
e
s
o
f
–
T
h
e
d
eg
r
ee
of
A
is
3
;
t
h
e
d
eg
r
ee
of
C
is
1
.
T
h
e
n
o
d
e
w
i
t
h
d
eg
r
ee
0
is
a
le
a
f
o
r
t
er
m
i
n
al
n
o
de
.
A
n
o
d
e
th
a
t
h
as
s
u
bt
r
e
e
s
is
th
e
pa
re
n
t
o
f
th
e
r
o
ot
s
of
t
h
e
s
ub
t
r
e
e
s.
T
h
e
r
oo
t
s
o
f
th
ese
s
u
bt
r
e
e
s
a
r
e
th
e
c
h
il
d
ren
o
f
t
h
e
n
o
d
e.
Chil
d
r
en
o
f
th
e
same
p
a
r
e
n
t
a
r
e
si
b
li
ng
s
.
T
h
e
an
c
e
s
to
rs
o
f
a
n
o
d
e
a
r
e
all
th
e
n
o
d
es
al
o
n
g
th
e
p
a
t
h
f
r
o
m
th
e
r
oo
t
t
o
th
e
n
o
d
e.
th
e
n
o
d
e
144
Bina
r
y
T
r
ees
A
b
i
n
ar
y
t
r
ee
i
s
a
f
i
n
i
t
e
s
e
t
of
n
odes
t
h
a
t
is
e
i
t
her
e
m
p
t
y
or
c
ons
i
s
t
s
of
a
r
oot
a
n
d
t
w
o
d
i
sjoi
n
t
b
i
na
r
y
t
r
e
e
s
c
a
l
led
t
h
e
l
e
f
t
su
b
t
r
e
e
and
t
h
e
r
ig
h
t
su
b
t
r
e
e
.
A
n
y
t
r
ee
c
an
be
t
r
a
n
s
f
o
r
m
e
d
i
n
t
o
b
i
n
ar
y
t
r
e
e
.
–
b
y
l
e
f
t
chi
l
d
-
r
i
g
h
t
sib
l
i
n
g
r
ep
r
es
e
n
t
a
t
ion
The
l
e
f
t
su
b
t
r
ee
and
t
he
r
i
g
h
t
su
b
t
r
ee
a
r
e
d
i
s
t
i
n
g
u
i
shed.
145
T
ypes
Of
Bi
n
ary
T
r
ees
T
h
e
r
e
a
r
e
t
h
r
ee
t
ypes
of
b
i
n
ar
y
t
r
e
e
s
•
L
e
f
t
s
k
ew
ed
b
i
n
ar
y
t
r
ee
•
Ri
g
h
t
s
k
ew
ed
b
i
na
r
y
t
r
ee
•
Compl
e
t
e
b
i
n
ar
y
t
r
ee
146
L
e
ft
s
k
e
w
ed
bina
r
y
t
r
ee
•
I
f
t
h
e
r
ig
h
t
su
b
t
r
ee
is
m
is
s
i
n
g
in
e
v
e
r
y
n
ode
of
a
t
r
ee
w
e
c
al
it
as
l
e
ft
s
k
e
w
ed
t
r
e
e
.
A
B
C
147
Rig
h
t
s
k
e
w
ed
bina
r
y
t
r
ee
•
I
f
t
he
l
e
f
t
su
b
t
r
ee
is
miss
i
ng
in
ev
ery
node
of
a
t
r
ee
w
e
c
a
l
l
i
t
as
r
i
g
h
t
su
b
t
r
e
e
.
A
B
C
148
C
o
mpl
e
t
e
bina
r
y
t
r
ee
•
T
h
e
t
r
ee
in
w
h
i
c
h
d
eg
r
ee
o
f
e
a
c
h
n
o
d
e
is
a
t
th
e
m
o
s
t
t
w
o
is
c
all
e
d
a
c
o
m
p
l
e
t
e
b
i
n
ary
t
r
e
e
.
I
n
a
c
o
m
p
l
e
t
e
b
i
n
ary
t
r
ee
th
e
r
e
is
e
x
ac
t
ly
o
n
e
n
o
d
e
a
t
le
v
el
0
,
t
w
o
n
o
d
es
a
t
le
v
el
1
a
n
d
f
o
u
r
n
o
d
es
a
t
le
v
el
2
a
n
d
so
o
n
.
s
o
w
e
c
an
s
a
y
th
a
t
a
c
o
m
p
l
e
t
e
2
l
b
i
n
ary
t
r
ee
of
d
e
pt
h
d
w
ill
c
o
nt
ai
n
s
e
x
actly
n
o
d
es
a
t
each
le
v
el
l,
w
h
e
r
e
l
is
f
r
o
m
0
t
o
d
.
A
C
B
D
E
F
G
149
A
b
s
t
r
act
D
a
t
a
T
ype
Bina
r
y_
T
r
ee
s
t
r
uctu
r
e
B
in
a
r
y
_
T
r
e
e
(abb
r
e
v
ia
t
ed
B
in
T
r
ee
)
is
obje
c
t
s:
a
f
i
n
i
t
e
s
e
t
of
nodes
e
i
t
her
e
m
p
t
y
or
c
onsi
s
t
i
n
g
of
a
r
oot
node,
l
e
f
t
B
in
a
r
y
_
T
r
e
e
,
a
n
d
r
i
g
h
t
Bin
a
r
y
_
T
r
e
e
.
f
unct
i
ons:
f
or
a
l
l
b
t
,
b
t
1
,
b
t
2
B
in
T
r
e
e
,
item
e
l
em
e
n
t
B
i
n
t
r
e
e
C
r
e
a
t
e
(
)::=
c
r
e
a
t
es
an
e
m
p
t
y
b
i
na
r
y
t
r
ee
B
o
ol
e
an
I
sEm
p
t
y(
b
t
):
:
=
i
f
(
b
t
=
=
e
m
p
t
y
b
i
n
ar
y
t
r
e
e
)
r
e
t
urn
TRUE
e
l
se
r
e
t
urn
F
ALSE
150
Bin
T
r
e
e
M
a
k
e
B
T
(
b
t
1
,
i
t
e
m
,
b
t
2
):
:
=
r
e
t
urn
a
b
i
n
a
r
y
t
r
ee
whose
l
e
f
t
su
b
t
r
ee
i
s
b
t
1
,
whose
r
i
g
h
t
su
b
t
r
ee
b
t
2
,
i
s
a
n
d
whose
r
oot
Bi
n
t
r
e
e
Lch
il
d
(
b
t
):
:
=
e
l
se
ele
m
e
n
t
Da
t
a
(
b
t
):
:
=
e
l
s
e
of
bt
no
d
e
c
o
n
t
a
i
ns
t
he
d
a
t
a
i
t
e
m
i
f
(I
s
Em
p
t
y
(
b
t
)
)
r
e
t
urn
e
r
r
or
r
e
t
urn
t
he
l
e
f
t
su
b
t
r
ee
of
bt
i
f
(I
s
Em
p
t
y(
b
t
)
)
r
e
t
urn
e
r
r
or
r
e
t
urn
t
he
da
t
a
i
n
t
he
r
oot
no
d
e
Bi
n
t
r
e
e
Rchi
l
d
(
b
t
):
:
=
i
f
(I
s
Em
p
t
y
(
b
t
)
)
r
e
t
urn
e
r
r
or
e
l
s
e
r
e
t
urn
t
he
r
i
g
h
t
s
u
b
t
r
ee
of
bt
151
M
a
xi
m
um
Nu
m
ber
T
h
e
m
a
x
i
mum
number
of
of
Nodes
in
B
T
nodes
on
l
ev
el
i
of
a
2
i
-1
,
b
i
na
r
y
t
r
ee
is
i>=
1
.
The
m
a
x
i
mum
nubmer
of
of
de
p
t
h
k
is
2
k
-
1
,
k
>
=
1
.
nodes
in
a
b
i
na
r
y
t
r
ee
P
r
o
v
e
b
y
ind
u
c
ti
o
n.
k
2
i
1
i
1
2
k
1
152
Bin
a
r
y
T
r
ee
R
ep
r
ese
n
t
a
tion
•
Sequ
e
n
t
i
a
l(A
r
r
a
y
s)
r
ep
r
es
e
n
t
a
t
ion
•
L
i
n
k
ed
r
ep
r
es
e
n
t
a
t
i
on
153
Ar
r
a
y
R
ep
r
ese
n
t
a
tion
of
Bina
r
y
T
r
ee
T
h
i
s
r
ep
r
es
e
n
t
a
t
i
on
uses
on
l
y
a
s
i
n
gl
e
l
i
near
ar
r
a
y
t
r
ee
as
f
ol
l
ow
s:
i
)The
r
oot
of
t
he
t
r
ee
is
s
t
o
r
ed
in
t
r
e
e
[0].
i
i
)if
a
node
o
c
cupies
t
r
e
e
[
i
]
,
t
hen
i
t
s
l
e
f
t
chi
l
d
is
s
t
o
r
ed
i
n
t
r
e
e
[2
*
i
+
1
],
i
t
s
r
i
g
h
t
t
r
e
e
[2
*
i
+
2
],and
t
he
pa
r
e
n
t
i
s
1
)
/
2
].
chi
l
d
i
s
s
t
o
r
ed
i
n
s
t
o
r
ed
i
n
t
r
e
e
[(
i
-
154
Sequ
e
n
tial
R
ep
r
ese
n
t
a
tion
[1]
[2]
[
3
]
[4]
[
5
]
[6]
[7]
[8]
[9]
.
.
.
.
A
B
C
E
G
D
F
H
I
155
A
B
C
D
E
F
G
H
I
.
.
.
.
Sequ
e
n
tial
R
ep
r
ese
n
t
a
tion
[0]
[1]
[
2
]
[3]
[
4
]
[5]
[6]
[7]
[8]
55
44
66
50
33
22
156
55
44
66
33
50
22
Ad
v
a
n
t
a
g
es
of
s
eq
u
e
n
t
i
al
r
ep
r
e
s
e
n
t
a
t
i
on
T
h
e
o
n
ly
a
d
v
a
n
t
a
g
e
w
i
t
h
t
h
is
t
y
p
e
of
r
e
p
r
ese
nt
a
t
ion
is
t
h
a
t
th
e
d
i
r
ect
ac
c
ess
t
o
a
n
y
n
o
d
e
c
an
b
e
p
o
ssi
b
le
a
n
d
f
i
nd
i
n
g
th
e
p
a
r
e
n
t
or
l
e
f
t
rig
h
t
c
h
il
d
r
en
of
a
n
y
p
ar
t
i
c
u
lar
n
o
d
e
is
f
a
s
t
b
e
c
a
u
se
o
f
th
e
r
a
nd
o
m
ac
c
ess.
157
D
i
sa
d
v
a
n
t
a
g
es
of
s
eq
u
e
n
t
i
al
r
ep
r
e
s
e
n
t
a
t
i
on
•
The
m
a
j
or
d
i
sad
v
a
n
t
a
g
e
wi
t
h
t
h
i
s
type
of
r
ep
r
es
e
n
t
a
t
ion
is
w
a
s
t
a
g
e
of
m
e
m
o
r
y
.
T
h
e
m
a
x
i
mum
de
p
t
h
of
t
he
t
r
ee
h
a
s
t
o
be
f
i
x
ed.
The
i
n
se
r
t
ions
and
del
e
t
ion
of
a
n
y
node
in
•
•
t
h
e
t
r
ee
wi
l
l
b
e
a
d
ju
s
t
ed
a
t
m
e
a
ni
ng
of
c
o
s
t
l
i
er
as
other
nodes
has
t
o
be
a
p
p
r
op
r
a
i
t
e
pos
i
t
i
ons
so
t
h
a
t
t
h
e
b
i
n
ar
y
t
r
ee
c
an
be
p
r
es
e
r
v
ed.
158
Lin
k
ed
s
t
r
uct
node
{i
n
t
d
a
t
a;
R
ep
r
ese
n
t
a
tion
s
t
r
uct
};
node
*
l
e
ft
_
c
h
il
d,
*
r
i
g
h
t
_
c
h
il
d
;
d
a
t
a
rig
h
t
_c
h
ild
l
e
ft
_child
159
l
e
ft
_child
d
a
t
a
rig
h
t
_child
Lin
k
ed
R
ep
r
ese
n
t
a
tion
root
5
5
,4
4
,6
6
,3
3
,5
0
,22
160
X
2
2
X
3
3
X
X
5
0
X
X
6
6
X
44
55
Ad
v
a
n
t
a
g
es
of Lin
k
ed
r
ep
r
ese
n
t
a
tion
•
Th
i
s
r
ep
r
es
e
n
t
a
t
ion
is
su
p
e
r
ior
t
o
our
r
ep
r
es
e
n
t
a
t
ion
as
t
he
r
e
is
no
w
a
s
t
a
g
e
of
me
m
o
r
y
.
•
I
nse
r
t
i
ons
a
n
d
del
e
t
i
ons
wh
i
ch
a
r
e
t
he
mo
s
t
c
om
m
on
ope
r
a
t
i
ons
other
nodes.
c
an
be
done
w
i
t
hout
m
o
v
i
n
g
t
he
161
D
i
sad
v
a
n
t
a
g
e
s
of lin
k
e
d
r
e
p
r
e
s
e
n
t
a
tion
•
Th
i
s
r
ep
r
es
e
n
t
a
t
ion
does
not
p
r
o
v
i
de
d
i
r
e
c
t
acc
e
ss
t
o
a
node
and
spe
c
i
a
l
a
lg
or
i
t
hms
a
r
e
r
equ
i
r
ed.
Th
i
s
r
ep
r
es
e
n
t
a
t
ion
ne
e
ds
ad
d
i
t
ion
a
l
space
in
•
each
node
t
r
e
e
s.
f
or
s
t
o
r
i
n
g
t
he
l
e
f
t
and
r
i
g
h
t
su
b
-
162
Full
B
T
V
S
C
o
mpl
e
t
e
B
T
A
b
i
n
ar
y
t
r
ee
wi
t
h
n
nodes
a
n
d
de
p
t
h
k
i
s
c
o
m
p
l
e
t
e
if
f
i
t
s
nodes
c
o
r
r
espond
t
o
the
nodes
numbe
r
ed
f
r
om
1
t
o
n
in
t
h
e
f
u
l
l
b
i
na
r
y
t
r
ee
of
de
p
t
h
k
.
k
A
f
u
l
l
b
i
n
a
r
y
t
r
ee
of
de
p
t
h
k
is
a
b
i
na
r
y
t
r
ee
of
de
p
t
h
k
h
a
v
i
ng
A
2
-
1
nodes,
k
>
=
0
.
A
B
C
B
C
G
D
F
E
F
G
D
E
H
I
M
N
163
O
L
I
J
K
H
C
o
m
p
l
e
t
e
b
i
n
ary
t
r
e
e
Fu
l
l
b
i
n
ary
t
r
e
e
o
f
dep
th
4
Bin
a
r
y
T
r
ee
T
r
a
v
e
r
s
a
ls
The
p
r
o
ce
ss
of
g
oing thro
u
g
h
a
tr
e
e
in su
c
h a
w
a
y
th
a
t
eac
h
node
is
vis
t
e
d
on
c
e
is
t
r
e
e tr
a
v
e
rs
a
l.sev
e
r
a
l
method
a
re used
for
tr
e
e
tr
a
v
e
r
s
a
l.
t
he tr
a
v
e
r
s
a
l
i
n a
bin
a
r
y
ac
t
i
vi
t
ies
such
a
s:
V
isiti
n
g
t
h
e
r
oo
t
T
r
a
verse
left
s
u
b
t
r
ee
tr
e
e
involves
thr
e
e
kinds
of
b
a
sic
T
r
a
verse
rig
h
t
s
u
b
t
r
ee
164
W
e
w
i
l
l
u
se
so
m
e
no
t
a
t
ions
t
o
t
r
a
v
e
r
se
a
g
i
v
en
bin
ar
y
t
r
ee
as
f
ol
l
ow
s:
L
m
e
ans
m
o
v
e
t
o
the
L
e
f
t
chi
l
d.
R
m
eans
m
o
v
e
t
o
the
Ri
g
h
t
chi
l
d.
D
means
t
he
r
oot/pa
r
e
n
t
node.
The
only
d
i
f
f
e
r
en
c
e
a
m
ong
t
he
m
e
t
hods
is
t
he
o
r
der
in
which
t
hese
t
h
r
ee
ope
r
a
t
ions
a
r
e
pe
r
f
o
r
m
e
d.
T
h
e
r
e
a
r
e
t
h
r
ee
s
t
a
n
d
a
r
d
w
a
y
s
e
m
p
t
y
b
i
n
ar
y
t
r
ee
n
a
m
e
l
y
:
P
r
eo
r
d
er
I
n
order
P
o
s
t
order
of
t
r
a
v
e
r
s
i
ng
a
non
165
P
r
e
o
r
de
r
(also
k
n
o
wn
as
de
p
t
h
-f
i
rs
t
o
r
de
r
)
1
.
V
is
i
t
t
h
e
2
.
T
r
a
v
e
r
se
3
.
T
r
a
v
e
r
se
r
oot(D)
t
he
t
he
l
e
f
t
su
b
t
r
ee
i
n
p
r
eo
r
de
r
(L)
r
i
g
h
t
su
b
t
r
ee
in
p
r
e
o
r
de
r
(
R
)
P
r
i
n
t
1
s
t
A
P
r
i
n
t
2
nd
P
r
i
n
t
4
th
B
D
P
r
i
n
t
3
r
d
E
C
P
r
i
n
t
a
t
t
h
e
l
a
s
t
A
-
B
-
C
-D
-
E
i
s
t
h
e
p
r
eo
r
der
t
r
a
v
e
r
sal
of
t
he
ab
o
v
e
f
i
g
u
r
e.
166
I
no
r
de
r
(also
k
n
o
wn
as
s
y
m
m
e
t
r
ic
o
r
de
r
)
1
.
T
r
a
v
e
r
se
2
.
V
i
s
i
t
t
h
e
3
.
T
r
a
v
e
r
se
t
he
l
e
f
t
su
b
t
r
ee
in
I
no
r
de
r
(L)
r
oot(D)
t
he
r
i
g
h
t
A
su
b
t
r
ee
i
n
I
no
r
der(
R
)
P
r
i
n
t
3
r
d
P
r
i
n
t
2
nd
P
r
i
n
t
4
th
B
D
P
r
i
n
t
1
s
t
E
C
P
r
i
n
t
a
t
t
h
e
l
a
s
t
C
-
B
-
A
-D
-
E
f
i
g
u
r
e.
i
s
t
h
e
I
no
r
der
t
r
a
v
e
r
sal
of
t
he
a
b
ov
e
167
P
o
s
t
o
r
der
1
.
T
r
a
v
e
r
se
2
.
T
r
a
v
e
r
se
3
.
V
i
s
i
t
t
h
e
t
he
l
e
f
t
su
b
t
r
ee
in
po
s
t
o
r
de
r
(L)
t
he
r
i
g
h
t
r
oot(D)
su
b
t
r
ee
i
n
po
s
t
o
r
de
r
(
R
)
P
r
i
n
t
a
t
t
h
e
l
a
s
t
A
P
r
i
n
t
3
r
d
P
r
i
n
t
4
th
B
D
P
r
i
n
t
1
s
t
E
C
P
r
i
n
t
2
nd
C
-D-
B
-
E
-
A
i
s
t
h
e
po
s
t
o
r
der
t
r
a
v
e
r
sal
of
t
he
a
b
ov
e
f
i
g
u
r
e.
168
Bina
r
y
A
t
r
ee
t
r
a
v
e
r
s
a
ls
A
B
C
B
C
G
D
F
E
G
D
F
E
J
H
I
K
H
I
J
F
I
G
(
a)
F
I
G
(
b
)
P
r
e
o
r
de
r
:
A
BDH
I
E
C
F
J
K
G
I
n
o
r
de
r
:
H
DIB
E
A
J
F
K
C
G
P
o
s
t
o
r
de
r
:
H
I
DE
B
JK
F
G
CA
p
r
e
o
r
de
r
i
n
o
r
de
r:
:
A
BDH
IE
JC
F
G
H
DIB
J
E
A
F
C
G
p
o
s
t
o
r
de
r
:
H
I
D
J
E
B
F
G
CA
169
Ar
i
th
m
e
tic
E
x
p
r
es
s
ion
U
sing
B
T
i
n
o
r
d
er
t
ra
v
e
r
sal
A
/
B
*
C
*
D
+
E
+
i
n
f
ix
e
x
p
r
essi
o
n
p
r
e
o
r
d
er
t
ra
v
e
r
sal
+
*
*
/
A
B
C
D
E
p
re
f
ix
e
x
p
r
essi
o
n
p
o
s
t
o
r
d
er
t
ra
v
e
r
sal
A
B
/
C
*
D
*
E
+
p
o
s
tf
ix
e
x
p
r
ession
le
v
el
o
r
d
er
t
ra
v
e
r
sal
+
*
E
*
D
/
C
A
B
*
E
*
D
C
/
A
B
170
Ino
r
der
T
r
a
v
e
r
s
a
l
(
r
ecu
r
si
v
e
v
e
r
sio
n
)
v
o
id
i
n
o
r
d
e
r
(
t
r
e
e
_
p
o
i
n
t
er
p
t
r)
*/
/*
{i
n
o
r
d
e
r
t
r
ee
t
r
a
v
e
r
s
a
l
if
(ptr)
{inorder(ptr
-
>left_child
)
;
printf(“%d”,
pt
r
->data);
indorder(ptr->right_chi
l
d);
}
}
171
A
/
B
*
C
*
D
+
E
P
r
eo
r
der
T
r
a
v
e
r
s
a
l
(
r
ecu
r
si
v
e
v
oid
p
r
e
o
r
de
r
(t
r
e
e
_
poi
nt
er
p
t
r
)
v
e
r
sion)
/*
p
r
e
o
r
der
t
r
ee
{t
r
a
v
e
r
sal
*/
i
f
(
p
t
r
)
{pr
i
n
tf
(“%d
”
,
p
t
r
-
>d
a
t
a);
p
r
e
o
r
de
r
(
p
t
r
-
>l
e
ft
_
c
h
i
l
d
);
p
r
edo
r
de
r
(
p
t
r
-
>
r
i
g
h
t
_
c
h
i
l
d
);
}
}
172
+
*
*
/
A
B
C
D
E
P
o
s
t
o
r
der
T
r
a
v
e
r
s
a
l
(
r
ecu
r
si
v
e
v
oid
po
s
t
o
r
de
r
(t
r
e
e
_
p
oi
nt
er
p
t
r
)
/*
po
s
t
o
r
der
t
r
ee
t
r
a
v
e
r
sal
*/
v
e
r
sio
n
)
{i
f
(
p
t
r
)
{po
s
t
o
r
de
r
(
p
t
r
-
>l
e
ft
_
c
h
il
d
);
po
s
t
do
r
de
r
(
p
t
r
-
>
r
i
g
h
t
_
c
h
il
d
);
pr
i
n
tf
(“%d
”
,
p
tr-
>d
a
t
a);
}
173
}
A
B
/
C
*
D
*
E
+
I
t
e
r
a
ti
v
e
Ino
r
der
T
r
a
v
e
r
s
a
l
(
u
si
n
g
s
t
ac
k
)
v
o
id
{i
t
e
r
_
i
n
o
r
d
e
r
(
t
r
e
e
_
p
o
i
n
t
e
r
n
o
d
e
)
i
n
t
t
o
p=
-
1;
/*
i
n
i
t
i
a
l
i
ze
s
t
a
c
k
*/
tree_pointer
stack[MAX_STACK_SIZE];
f
o
r
(
;
;)
{f
o
r
(;
n
o
d
e
;
n
o
d
e
=
n
o
d
e->left_chil
d
)
add(&top,
node);/*
a
d
d
to
s
t
a
ck
*/
n
o
d
e
=
d
e
l
e
t
e
(
&
t
o
p
)
;
/*
d
e
l
e
te
f
r
om
s
t
a
c
k
*/
if
(!node)
break;
/*
e
m
p
t
y
s
t
a
c
k
*/
printf(“%D”,
nod
e
->data);
n
o
de
=
n
o
d
e
->right_child;
}
}
O
(n
)
174
T
r
ace
Ope
r
a
tions
o
f
Ino
r
der
T
r
a
v
e
r
s
a
l
175
C
a
ll
o
f
i
n
o
r
d
e
r
Va
l
u
e
in
r
oo
t
A
c
ti
o
n
C
a
l
l
o
f
i
n
o
rd
e
r
Va
l
u
e
in
r
o
o
t
A
c
ti
o
n
1
2
3
4
5
6
5
7
4
8
9
8
1
0
3
+
*
*
/
A
NU
L
L
A
NU
L
L
/
B
NU
L
L
B
NU
L
L
*
p
r
i
n
t
f
p
r
i
n
t
f
p
r
i
n
t
f
p
r
i
n
t
f
1
1
1
2
1
1
1
3
2
1
4
1
5
1
4
1
6
1
1
7
1
8
1
7
1
9
C
NU
L
L
C
NU
L
L
*
D
NU
L
L
D
NU
L
L
+
E
NU
L
L
E
NU
L
L
p
r
i
n
tf
p
r
i
n
tf
p
r
i
n
tf
p
r
i
n
tf
p
r
i
n
tf
L
e
v
el
O
r
der
T
r
a
v
e
r
s
a
l
(
u
si
n
g
qu
e
u
e
)
v
o
id
l
e
v
e
l
_
o
r
d
e
r
(
t
r
e
e
_
p
o
i
n
t
er
p
t
r)
*/
/*
{l
e
v
e
l
o
r
d
e
r
t
r
ee
t
r
a
v
e
r
s
a
l
i
n
t
f
r
o
n
t
=
r
e
ar
=
0;
tree_pointer
queue[MAX_QUEUE_SIZE];
if
(
!
p
t
r)
r
e
t
u
r
n
;
/*
e
m
p
t
y
q
u
e
u
e
*/
addq(front,
&rear,
ptr);
f
o
r
(
;
;)
{p
t
r
=
d
e
l
e
t
e
q
(
&
f
r
o
n
t
,
r
e
a
r
);
176
if
(ptr)
{printf(“%d”,
pt
r
->data);
if
(
p
t
r
->left_child)
addq(front,
&rear,
ptr->left_child);
if
(
p
t
r
->right_child)
addq(front,
&rear,
ptr->right_child);
}
e
l
se
b
r
e
a
k;
}
}
177
+
*
E
*
D
/
C
A
B
C
o
p
y
i
ng
B
ina
r
y
T
r
ees
tree_poointer
{copy(tree_pointer
original)
tree_pointer
temp;
if
(original)
{temp=(tree_pointer)
malloc(sizeof(node));
if
(IS_FULL(temp))
{fprintf(stderr,
exit(1);
“the
memory
is
ful
l
\n”);
}
temp->left_child=copy(origina
l
->left_child
)
;
temp->right_child=copy(origina
l
->right_chi
l
d
temp->data=origina
l
->data;
return
}
temp;
return
}
NULL;
178
p
o
s
t
o
r
d
er
P
o
s
t
-
o
r
de
r
-
e
v
al
f
unc
ti
on
v
oid
p
o
s
t_
o
r
d
er_
e
v
a
l
(
t
r
e
e
_
p
oi
n
t
er
n
o
d
e)
{/*
mod
i
fi
e
d
p
o
s
t
o
r
d
er
t
r
a
v
e
r
s
a
l
t
o
e
v
al
u
at
e
a
p
r
o
p
o
s
iti
on
al
c
alc
u
l
u
s
t
r
ee
*/
if
(
n
o
d
e)
{p
o
s
t
_
o
r
d
er_
e
v
a
l
(
n
o
de
-
>l
e
f
t
_c
h
il
d)
;
p
o
s
t
_
o
r
d
er_
e
v
a
l
(
n
o
d
e
-
>rig
h
t
_
c
h
il
d)
;
s
w
i
t
c
h
(
n
o
d
e
-
>
d
at
a)
{c
a
s
e
no
t
:
n
o
d
e
-
>
v
al
u
e
=
!
n
o
de
-
>rig
h
t_c
h
il
d
-
>
v
al
u
e;
b
r
e
a
k
;
179
c
ase
a
n
d
:
n
o
d
e
-
>
v
al
u
e
=
n
o
d
e
-
>
rig
h
t
_c
h
il
d
-
>
v
al
u
e
&&
n
o
de
-
>
l
e
ft
_chil
d
-
>
v
al
u
e;
b
r
e
a
k
;
c
ase
o
r:
n
o
d
e
-
>
v
al
u
e
=
n
o
d
e
-
>
rig
h
t
_c
h
il
d
-
>
v
al
u
e
|
|
n
o
d
e
-
>
l
e
ft
_c
h
il
d
-
>
v
al
u
e;
b
r
e
a
k
;
c
ase
t
r
u
e:
b
r
ea
k
;
c
ase
f
alse:
}
n
o
d
e
-
>
v
al
u
e
=
T
R
U
E;
n
o
d
e
-
>
v
al
u
e
=
F
AL
S
E;
}
}
180
Th
r
eaded
Bin
a
r
y
T
r
ees
T
w
o
m
a
n
y
nu
l
l
po
i
n
t
e
r
s
in
cu
r
r
e
n
t
of
b
i
na
r
y
t
r
e
e
s
n:
number
of
nodes
number
of
n
o
n-
nu
l
l
li
n
k
s:
n
-
1
t
o
t
al
l
i
n
k
s:
2n
nu
l
l
l
i
n
k
s:
2
n
-
(
n
-
1
)
=
n
+1
r
ep
r
es
e
n
t
a
t
i
o
R
epl
a
ce
t
h
ese
“t
h
r
eads
”
.
nu
l
l
po
i
n
t
e
r
s
wi
t
h
some
us
e
f
ul
181
Th
r
eaded
B
ina
r
y
T
r
ees
(
C
o
n
t
i
nu
ed
)
I
f
ptr->left_chil
d
is
r
e
p
la
c
e
i
t
w
i
th
a
p
o
i
n
t
er
vi
s
i
t
ed
be
f
ore
pt
r
in
an
n
u
ll,
t
o
t
h
e
node
t
h
a
t
w
ould
ino
r
der
t
r
a
v
ersal
b
e
I
f
ptr->right_chil
d
is
nu
ll,
r
e
p
la
c
e
it
with
a
p
o
i
n
t
er
t
o
th
e
no
d
e
t
h
a
t
vi
s
i
t
ed
af
t
er
pt
r
in
an
inorder
tr
a
versal
w
ould
b
e
182
A
Th
r
eaded
r
oo
t
Bin
a
r
y
T
r
ee
A
d
a
n
gli
n
g
C
B
d
a
n
gling
G
F
E
D
i
n
o
r
d
er
t
ra
v
e
r
sal:
H
,
D
,
I,
B
,
E,
A
,
F
,
C,
G
I
H
183
D
a
t
a
S
t
ru
c
tu
r
es
f
or
Th
r
eaded
B
T
rig
h
t
_c
h
ild
rig
h
t
_
t
h
r
e
a
d
l
e
ft
_
t
h
r
e
a
d
l
e
ft
_c
h
ild
d
a
t
a
F
ALS
E
:
c
h
ild
T
R
U
E:
th
r
e
a
d
ty
p
e
d
e
f
s
tr
uc
t
t
h
r
e
a
d
e
d
_
t
r
ee
*
t
h
r
e
a
d
e
d
_
p
o
i
n
t
e
r
;
ty
p
e
d
e
f
s
tr
uc
t
t
h
r
e
a
d
e
d
_
t
r
ee
{short
i
n
t
l
e
ft_t
h
r
ea
d
;
t
h
r
e
a
d
e
d
_
p
o
i
n
t
er
l
e
ft_
c
h
ild;
c
h
ar
d
a
t
a;
t
h
r
ea
d
e
d
_
p
o
i
n
t
er
rig
h
t
_ch
ild;
short
i
n
t
rig
h
t
_
t
h
r
ea
d
;
};
184
T
R
UE
F
A
L
S
E
Memo
r
y
R
ep
r
e
s
e
n
t
a
t
i
on
of
A
Th
r
ea
d
ed
B
T
r
oo
t
H
I
t
t
t
t
185
t
F
t
t
E
t
f
D
f
t
G
f
C
f
f
B
f
f
A
f
f
--
f
N
e
x
t
Node
in
Th
r
eaded
B
T
threaded_pointer
tree)
{insuc
c
(threaded_pointer
threaded_pointer
temp;
temp
=
tre
e
-
>right_child;
if
(!t
r
e
e
->
right_threa
d
)
wh
i
le
(!
t
em
p
->left_threa
d
)
te
m
p
=
te
m
p
->left_child;
ret
u
rn
tem
p
;
}
186
Ino
r
der
T
r
a
v
e
r
s
a
l
o
f
Th
r
eaded
B
T
void
{tinorde
r
(threaded_poi
n
ter
tree)
/*
t
r
a
v
e
r
se
t
h
e
t
h
r
e
a
d
ed
b
i
n
a
ry
t
r
ee
inorder
*/
threaded_pointer
t
e
mp
=
t
r
e
e
;
f
o
r
(
;
;)
t
e
mp
{=
insucc(temp);
if
(temp==tree)
break;
printf(“%3c”,
tem
p-
>data);
}
O(
n)
(
t
i
m
e
c
ompl
e
x
i
t
y
)
}
187
Insert
i
ng
Nodes
i
nt
o
Th
r
eaded
B
T
s
I
nse
r
t
chil
d
as
t
he
r
i
g
h
t
chi
l
d
of
node
parent
–
–
c
h
a
n
g
e
parent->right_thread
t
o
F
ALSE
s
e
t
child->left_thread
a
n
d
child->right_thread
t
o
T
R
UE
–
–
–
s
e
t
s
e
t
child->left_child
t
o
p
o
i
n
t
t
o
parent
child->right_child
t
o
paren
t
->right_child
ch
a
n
g
e
parent->right_child
t
o
p
o
i
n
t
t
o
child
188
E
x
amples
In
sert
r
oo
t
a
n
ode
D
as
a
rig
h
t
ch
ild
r
oo
t
o
f
B.
A
A
(
1)
p
a
r
e
n
t
p
a
r
e
n
t
B
B
(3)
c
h
il
d
c
h
il
d
C
C
D
D
(2)
e
m
p
ty
189
*Fi
g
u
r
e
5.2
4
:
I
nse
r
t
i
o
n
o
f
c
h
il
d
as
a r
i
g
h
t
c
h
il
d
o
f
p
a
r
e
n
t
i
n
a t
h
r
e
a
de
d
b
i
n
ary
t
r
e
e
(
p
.217)
(3)
(
1)
(2)
(
4)
n
o
n
e
m
pt
y
190
Ri
g
h
t
Insert
i
on
in
Th
r
eaded
B
T
s
void
insert_right
(
threaded_pointer
threaded_pointer
parent,
child)
{threaded_pointer
temp;
(
1
)
chil
d
->right_child
=
paren
t
->right_child;
child->right_thread
=
paren
t
->right_threa
d
;
chil
d
->left_child
=
parent;
case
(a)
(
2
)
child->left_thread
=
TRUE;
child;
(
3
)
parent->right_child
=
parent->right_thread
=
FALSE;
if
(!chi
l
d->right_thread)
{case
(b)
(
4
)
temp
=
insucc(child);
temp->left_child
=
child;
}
}
191
Heap
A
m
a
x
t
r
e
e
i
s
a
t
r
ee
i
n
wh
i
ch
t
he
k
e
y
v
a
l
ue
i
n
each
node
is
no
smal
l
er
t
han
t
he
k
e
y
v
a
l
ues
in
i
t
s
chi
l
d
r
en.
A
m
a
x
h
eap
is
a
c
o
m
p
l
e
t
e
b
i
na
r
y
t
r
ee
t
h
a
t
is
al
so
a
m
a
x
t
r
e
e
.
A
min
t
r
e
e
i
s
a
t
r
ee
i
n
wh
i
ch
t
he
k
e
y
v
a
l
ue
i
n
each
node
is
no
l
a
r
g
er
t
han
t
he
k
e
y
v
a
l
ues
in
i
t
s
chi
l
d
r
en.
A
min
h
eap
is
a
c
o
m
p
l
e
t
e
b
i
na
r
y
t
r
ee
t
h
a
t
is
al
so
a
min
t
r
e
e
.
Ope
r
a
t
ions
on
hea
p
s
–
–
–
c
r
e
a
tion
of
an
e
m
p
ty
h
e
a
p
i
n
sert
i
on
of
a
n
e
w
e
l
em
e
n
t
i
n
t
o
th
e
h
e
a
p
;
d
e
l
e
tion
of
t
h
e
la
r
g
e
s
t
e
l
em
e
n
t
f
r
om
t
h
e
h
e
ap
192
Sam
p
le
m
a
x
h
ea
p
s
[
1]
[
1]
9
[
1]
14
30
[
2]
[
2]
[
3]
[
2]
[
3]
3
6
7
25
12
[
5]
[
6]
6
[
4]
[
4]
5
10
8
P
r
ope
r
t
y:
T
h
e
r
o
o
t
of
m
a
x
h
e
a
p
c
o
nt
ai
n
s
t
h
e
la
r
g
e
s
t
.
193
Sa
m
p
le
min
h
e
a
p
s
[
1]
[
1]
10
[
1]
2
11
[
2]
[
2]
[
3]
[
2]
[
3]
83
20
4
21
7
[
5]
[
6]
6
[
4]
[
4]
50
10
8
P
r
ope
r
t
y:
T
h
e
r
o
o
t
of
m
in
h
e
a
p
c
o
nt
ai
n
s
t
h
e
small
e
s
t
.
194
A
D
T
f
or
M
a
x
Heap
s
t
r
u
c
tu
r
e
M
a
xH
e
a
p
o
b
j
e
c
t
s:
a
c
o
m
p
l
e
t
e
b
i
n
ary
t
r
ee
o
f
n
>
0
el
e
ments
o
r
g
a
n
i
z
ed
so
th
a
t
th
e
v
al
u
e
in
e
a
c
h
n
o
d
e
is
a
t
le
a
s
t
as
la
r
g
e
as
th
o
se
in
i
t
s
c
h
il
d
r
en
fun
c
t
io
n
s:
f
o
r
all
h
eap
b
el
on
g
t
o
M
a
xH
ea
p
,
i
t
em
b
el
on
g
t
o
El
e
me
n
t
,
n
,
m
a
x
_
s
i
z
e
b
el
on
g
t
o
i
n
t
e
g
er
M
a
xH
e
a
p
C
r
e
a
t
e(m
a
x
_si
z
e
)
:
:
=
c
r
e
a
t
e
an
e
m
pt
y
h
e
a
p
th
a
t
c
an
h
o
ld
a
m
a
x
im
u
m
o
f
m
a
x
_si
z
e
el
e
ments
B
o
o
lean
H
ea
p
F
u
l
l
(
h
ea
p
,
n
)
:
:
=
if
(
n
=
=
m
a
x
_si
z
e
)
re
t
u
rn
TR
U
E
else
re
tu
rn
F
ALSE
M
a
x
H
eap
Inser
t
(
h
ea
p
,
i
t
em,
n
)
:
:
=
if
(
!
H
ea
p
F
u
l
l
(
h
ea
p
,
n
)
)
i
n
sert
i
t
em
i
n
t
o
h
e
a
p
a
n
d
re
tu
rn
th
e
r
es
u
l
t
i
n
g
h
e
a
p
else
re
t
u
rn
er
r
or
B
oo
le
a
n
H
e
a
p
E
m
pty
(
h
e
a
p
,
n
)
:
:
=
if
(
n
>
0
)
re
tu
rn
F
ALSE
else
re
t
u
rn
TR
U
E
El
e
ment
D
el
e
t
e
(h
e
a
p
,
n
)
:
:
=
if
(
!
H
e
a
p
E
m
pty
(
h
e
a
p
,
n
)
)
re
tu
rn
o
n
e
i
n
s
t
a
n
c
e
of
t
h
e
la
r
g
e
s
t
elem
e
n
t
in
t
h
e
h
eap
a
n
d
r
e
mo
v
e
it
f
r
o
m
th
e
h
e
a
p
else
re
t
u
rn
er
r
or
195
E
x
ample
o
f
Insert
i
on
t
o
M
a
x
Heap
21
20
20
20
15
5
2
15
15
2
2
14
10
14
10
14
10
i
n
s
e
rt
21
i
n
t
o
h
e
ap
i
n
s
e
rt
5
i
n
t
o
he
ap
i
n
i
t
i
al
l
o
ca
t
i
o
n
o
f
n
e
w
n
o
d
e
196
Insert
i
o
n
i
nt
o
a
M
a
x
Heap
void
{insert_max_heap(element
item,
int
*n)
int
i;
if
(HEAP_FULL(*n))
{fprintf(stderr,
exit(1);
“the
heap
i
s
ful
l
.\n”);
}
i
=
++(*n);
while
((i!=
1
)&&(item.key>heap[i/2].key))
{heap[i]
=
heap[i/2];
2
k
-
1
=
n
==>
k
=
lo
g
2
(n+1
)
i
/=
2;
}
heap[i]=
O(lo
g
2
n)
item;
}
197
E
x
amp
l
e
of
D
e
l
e
tion
f
r
om
M
a
x
Heap
r
e
m
o
v
e
20
10
15
2
2
2
15
14
15
14
14
10
10
198
De
l
e
tion
f
r
om
a
M
a
x
Heap
element
{delete_max_hea
p
(int
*n)
int
parent,
child;
element
item,
temp;
if
(HEAP_EMPTY(*n))
{fprintf(stderr,
exit(1);
“The
heap
i
s
emp
t
y
\n”);
}
/*
save
value
of
the
element
with
the
highest
key
*/
item
=
heap[1];
/*
use
l
a
st
el
e
ment
in
heap
t
o
adj
u
st
heap
temp
=
heap[(*n
)
--];
parent
=
1;
child
=
2;
199
while
(child
<=
*n)
{/*
find
the
larger
child
of
the
current
parent
*/
if
((child
<
*n)&&
(heap[child].key<heap[child+1].key))
child++;
if
(temp.key
>=
heap[child].key)
break;
/*
move
to
the
next
lower
level
*/
heap[parent]
=
heap[child];
child
*=
2;
}
heap[parent]
return
item;
=
temp;
}
200
G
r
a
p
hs
201
W
h
a
t
is
a
g
r
ap
h
?
A
d
a
t
a
s
tr
uc
t
u
r
e
t
h
a
t
c
onsi
s
ts
of
a
s
e
t
of
n
od
e
s
(
ver
t
i
c
e
s
)
a
n
d
a
s
e
t
of
e
d
g
es
t
h
a
t
r
e
l
at
e
t
h
e
n
odes
t
o
e
a
c
h
ot
h
er
•
•
T
h
e
s
e
t
of
e
d
g
es
d
es
c
rib
e
s
r
e
l
a
tions
h
i
p
s
a
m
ong
t
h
e
v
ert
i
c
es
202
F
o
r
mal
d
e
finit
i
on
of
g
r
aph
G
is
d
e
f
i
n
ed
as
f
ol
l
ow
s:
G=
(
V
,E)
g
r
aphs
•
A
V
(G
)
:
E(G
)
:
a
f
i
n
i
t
e,
nonem
p
t
y
s
e
t
of
v
e
r
t
i
c
e
s
v
e
r
t
i
c
e
s)
a
s
e
t
of
ed
g
es
(pa
i
r
s
of
203
Di
r
e
c
t
ed
vs.
und
i
r
e
c
t
ed
g
r
aphs
•
Wh
e
n
t
he
ed
g
es
i
n
a
g
r
a
p
h
h
a
v
e
no
d
i
r
e
c
t
i
on,
t
he
g
r
a
p
h
i
s
c
a
l
l
ed
u
n
di
r
e
c
t
e
d
204
Di
r
ec
t
ed
v
s.
un
d
i
r
ec
t
ed
g
r
ap
h
s
(co
n
t.)
•
When
t
h
e
ed
g
es
in
a
g
r
a
p
h
h
a
v
e
a
d
i
r
ect
ion
,
t
h
e
g
r
a
p
h
is
c
a
l
led
direc
t
ed
(or
digr
a
p
h
)
E
(
G
r
a
ph
2
)
=
{(
1,3
)
(
3,1
)
(
5,9
)
(
9,11
)
(
5,7
)
205
T
r
ees
v
s
g
r
aphs
•
T
r
e
e
s
a
r
e
special
c
ases
of
g
r
a
p
hs!!
206
G
r
aph
t
e
rm
ino
l
ogy
A
d
j
ace
n
t
n
o
de
s
:
t
w
o
n
o
des
a
r
e
a
d
jace
n
t
•
if
t
h
e
y
a
r
e
c
o
nn
ec
t
ed
b
y
an
e
d
g
e
5
i
s
a
d
ja
c
e
n
t
t
o
7
7
i
s
a
d
ja
c
e
n
t
f
r
o
m
5
•
P
a
t
h
:
a
seq
u
ence
of
v
ert
i
ces
t
h
a
t
c
o
nn
ect
t
w
o
n
o
d
es
in
a
g
r
a
p
h
C
o
mp
l
e
t
e
g
r
a
p
h
:
a
g
r
a
p
h
in
w
h
i
ch
e
v
e
r
y
v
er
t
e
x
•
is
d
i
r
ect
l
y
c
o
nn
ec
t
ed
t
o
e
v
e
r
y
ot
h
er
v
er
t
e
x
207
G
r
aph
t
erm
i
nol
o
gy
(
c
o
n
t.)
•
W
h
a
t
is
th
e
n
u
mb
er
o
f
e
d
g
es
in
a
c
o
mp
l
et
e
di
r
e
c
t
ed
g
r
a
p
h
N
*
(
N
-
1)
w
ith
N
v
ert
i
c
es?
2
O
(
N
)
208
G
r
aph
t
erm
i
nol
o
gy
(
c
o
n
t.)
W
h
a
t
is
th
e
n
u
m
b
er
of
e
d
g
es
in
a
c
om
p
l
et
e
•
und
i
r
e
c
t
ed
g
r
a
p
h
w
i
th
N
v
ert
i
c
es?
N
*
(N
-
1)
/
2
2
)
O
(
N
209
G
r
aph
t
erm
i
nol
o
gy
(
c
o
n
t.)
•
W
e
i
g
h
t
ed
g
r
a
p
h
:
a
g
r
a
p
h
in
whi
c
h
e
a
c
h
e
d
g
e
c
arr
i
es
a
v
al
u
e
210
G
r
aph
imp
l
em
e
nt
a
tion
A
r
r
a
y
-
based
imp
l
e
m
e
n
t
a
t
ion
•
–
–
A
1D
a
r
r
a
y
is
u
sed
t
o
r
e
p
r
ese
n
t
t
h
e
v
ert
i
c
es
A
2D
a
r
r
a
y
(
a
d
ja
c
e
n
c
y
m
a
tr
ix
)
is
u
sed
t
o
r
e
p
r
es
e
n
t
t
h
e
e
d
g
es
211
212
G
r
aph
imp
l
em
e
nt
a
tion
(
c
o
n
t.)
L
i
n
k
ed
-
l
i
s
t
imp
l
e
m
e
n
t
a
t
ion
•
–
–
A
1D
a
r
ra
y
is
used
t
o
r
e
p
r
ese
n
t
the
v
e
r
tic
e
s
A
li
s
t
is
used
f
or
e
a
ch
v
e
r
t
e
x
v
whi
c
h
c
o
n
t
a
i
ns
the
v
e
r
tic
e
s
whi
c
h
a
r
e
a
d
j
a
c
e
n
t
f
r
om
v
(
a
d
j
a
c
e
n
cy
li
s
t)
213
214
A
d
jace
n
cy
m
a
tr
i
x
v
s.
adja
c
en
c
y
r
ep
r
e
s
e
nta
tion
l
i
s
t
•
A
d
ja
c
ency
m
a
trix
–
–
–
G
o
od
f
or
d
e
n
se
g
r
a
ph
s
--|
E
|
~
O
(
|
V
|
2
)
M
e
m
o
r
y
r
e
q
u
i
r
e
m
e
n
ts:
O
(
|V|
+
|
E
|
)
=
O
(
|
V
|
2
)
C
on
n
e
c
tivity
b
e
t
w
e
e
n
t
w
o
v
ert
i
c
es
c
an
b
e
t
e
s
t
ed
qu
i
c
k
l
y
•
Adja
c
e
n
cy
l
i
s
t
–
–
–
G
o
od
f
or
spa
r
se
g
r
a
ph
s
-
-
|
E
|
~
O
(
|
V
|)
M
e
m
o
r
y
r
e
q
u
i
r
e
m
e
n
ts:
O
(
|V|
+
|
E|
)
=O
(
|V|)
V
ert
i
c
es
a
d
ja
c
e
n
t
t
o
a
n
oth
e
r
v
er
t
e
x
c
an
b
e
f
ou
n
d
qu
i
c
k
l
y
215
De
p
t
h
-Fi
r
s
t-Sea
r
ch
(D
F
S)
W
h
a
t
is
t
he
idea
behi
n
d
D
F
S?
–
T
r
a
v
el
as
f
ar
as
y
ou
c
an
d
o
w
n
a
p
a
th
–
B
a
c
k
u
p
as
li
t
tle
as
pos
s
ible
when
y
ou
r
ea
c
h
•
a
"d
e
ad
e
n
d
"
(
i
.
e.,
n
e
xt
v
er
t
e
x
h
as
b
e
e
n
"
m
ar
k
e
d
"
or
t
h
e
r
e
is
n
o
n
e
xt
v
er
t
e
x)
•
D
F
S
c
an
be
i
mplem
e
n
t
ed
e
f
f
i
cie
n
t
l
y
us
i
ng
a
st
a
c
k
216
De
p
t
h
-Fi
r
s
t
-Sea
r
ch
S
e
t
f
oun
d
to
f
a
lse
st
a
ck.
P
u
s
h
(
st
a
rt
V
e
rte
x
)
DO
st
a
ck.
P
o
p
(
v
e
rte
x
)
IF
v
e
r
t
e
x
=
=
end
V
e
r
t
e
x
Se
t
f
oun
d
to
true
E
L
SE
(D
F
S)
(
c
o
n
t.)
Pu
sh
a
ll
a
d
jac
e
n
t
v
e
rtices
on
to
st
a
ck
W
HILE
!
st
a
ck.Is
Em
p
t
y(
)
AND
!
f
oun
d
IF(!
f
ound
)
W
r
i
te
"
Pa
th
doe
s
no
t
e
x
ist"
217
(
i
n
i
t
i
al
i
z
a
t
i
o
n
)
218
219
220
te
m
p
l
ate
<
c
l
a
s
s
It
e
m
T
y
p
e
>
v
o
i
d
De
p
t
h
Fir
s
t
S
e
a
r
c
h
(Gr
a
p
h
T
y
p
e<
V
erte
x
T
y
p
e
>
s
tart
V
erte
x
,
V
erte
x
T
y
pe
e
n
d
V
erte
x
)
{S
ta
c
k
T
y
p
e<
V
erte
x
T
y
p
e
>
s
ta
c
k
;
Q
u
e
T
y
p
e
<
V
erte
x
T
y
p
e
>
v
erte
xQ
;
b
o
ol
f
o
u
nd
=
f
a
l
s
e;
V
erte
x
T
y
pe
v
erte
x
;
V
erte
x
T
y
pe
i
te
m
;
gra
p
h
.
C
l
e
a
r
M
a
r
k
s
()
;
s
ta
c
k
.
P
u
s
h(
s
tart
V
erte
x
)
;
do
{s
ta
c
k
.
P
o
p
(
v
erte
x
)
;
i
f
(
v
ertex
=
=
e
n
d
V
erte
x
)
f
o
u
nd
=
tru
e
;
gra
p
h,
V
erte
x
T
y
pe
(
c
o
n
t
inue
s
)
221
e
l
s
e
{i
f
(
!
gra
p
h
.
I
s
M
a
r
k
e
d
(
v
erte
x)
)
{graph
.
M
a
r
k
V
erte
x
(
v
erte
x
)
;
gra
p
h
.
G
e
t
T
o
V
ert
i
c
es
(
v
erte
x
,
v
erte
xQ)
;
w
h
i
l
e(
!
v
erte
xQ
.IsE
m
p
t
y
()
)
{v
erte
xQ
.De
q
u
e
u
e
(
i
te
m
)
;
i
f
(
!
gra
p
h
.
I
s
M
a
r
k
e
d
(
i
t
e
m
)
)
s
ta
c
k
.
P
u
s
h(i
t
e
m
)
;
}
}
}
w
h
i
l
e(
!
s
t
a
c
k
.IsE
m
p
t
y
(
)
&
&
!
f
o
u
n
d
)
;
i
f
(
!
f
o
u
n
d
)
c
o
u
t
<
<
"P
ath
n
o
t
f
o
u
n
d
"
<
<
e
n
d
l
;
}
(
c
o
n
t
inue
s
)
222
te
m
p
l
at
e<
c
l
a
s
s
V
erte
x
T
y
pe>
v
o
i
d
G
r
a
p
h
T
y
p
e
<
V
erte
x
T
y
p
e
>
::
G
et
T
o
V
ert
i
c
e
s
(
V
erte
x
T
y
p
e
Q
u
e
T
y
e
<
V
erte
x
T
y
p
e
>
&
a
d
j
v
erte
x
Q
)
{i
nt
f
r
o
m
In
d
e
x
;
i
nt
to
I
n
d
e
x
;
v
erte
x
,
f
r
o
m
I
n
d
e
x
=
I
n
d
e
x
I
s
(
v
ert
i
c
es,
v
erte
x)
;
f
or
(
to
I
n
d
ex
=
0;
to
I
n
d
ex
<
n
u
m
V
ert
i
c
e
s
;
to
I
n
d
e
x
++)
i
f
(
e
d
g
e
s
[
f
r
o
m
I
n
d
e
x
][t
o
I
n
d
e
x
]
!
=
NUL
L
_
E
D
G
E
)
a
d
j
v
erte
xQ
.
E
n
q
u
e
u
e
(
v
ert
i
c
e
s[
to
I
n
d
e
x
]
)
;
}
223
B
r
eadt
h
-Fi
r
s
t-Sea
r
c
h
ing
(B
F
S)
Wh
a
t
is
t
he
i
d
ea
beh
i
nd
B
F
S?
•
–
Lo
o
k
a
t
all
p
o
s
sible
p
a
t
h
s
a
t
t
h
e
s
a
m
e
d
e
p
th
b
e
f
o
r
e
y
ou
g
o
a
t
a
d
e
ep
er
l
e
v
el
–
B
a
c
k
u
p
as
f
ar
as
pos
s
ible
when
y
ou
r
ea
c
h
a
"
d
e
a
d
e
n
d
"
(
i
.
e.,
n
e
xt
v
er
t
e
x
h
as
b
e
e
n
"
m
ar
k
e
d
"
or
t
h
e
r
e
i
s
n
o
n
e
xt
v
er
t
e
x)
224
B
r
e
a
dt
h
-Fi
r
s
t
-Se
a
r
c
hing
(B
F
S)
(
c
o
n
t.)
•
B
F
S
c
an
b
e
im
p
le
m
e
n
t
ed
S
et
f
o
u
nd
to
f
a
l
s
e
q
u
e
u
e
.E
n
q
u
e
u
e
(s
t
a
r
t
V
erte
x
)
DO
q
u
e
u
e.D
e
q
u
e
u
e
(v
erte
x
)
IF
v
ertex
=
=
e
n
d
V
ertex
S
et
f
o
u
nd
to
true
E
L
S
E
e
f
f
i
c
ie
n
tly
u
sing
a
q
u
eue
E
n
q
u
e
ue
a
l
l
a
d
j
a
c
e
n
t
v
ert
i
c
es
o
n
to
q
u
e
u
e
W
HILE
!
q
u
e
u
e.
I
s
E
m
pt
y
(
)
A
ND
!
f
o
u
nd
•
Shou
l
d
w
e
m
ark
a
v
er
t
e
x
when
when
it
is
d
e
q
u
e
u
ed
?
it
is
e
n
qu
e
u
ed
or
225
(
i
n
i
t
i
al
i
z
a
t
i
o
n
)
226
n
e
x
t
:
227
228
t
e
m
p
l
a
t
e
<
c
l
ass
V
erte
x
T
y
p
e
>
v
o
i
d
B
r
e
a
dt
h
F
i
r
t
s
S
e
a
r
c
h
(
G
r
a
p
h
T
y
p
e
<
V
erte
x
T
y
p
e>
graph,
V
erte
x
T
y
pe
s
tart
V
erte
x
,
V
erte
x
T
y
pe
e
n
d
V
erte
x
)
;
{Q
u
e
T
y
p
e
<
V
erte
x
T
y
p
e
>
Q
u
e
T
y
p
e
<
V
erte
x
T
y
p
e
>
q
u
e
u
e;
v
erte
xQ
;//
b
o
ol
f
o
u
nd
=
f
a
l
s
e;
V
erte
x
T
y
pe
v
erte
x
;
V
erte
x
T
y
pe
i
te
m
;
gra
p
h
.
C
l
e
a
r
M
a
r
k
s
()
;
q
u
e
u
e.
E
n
q
u
e
u
e
(
s
tar
t
V
erte
x
)
;
do
{q
u
e
u
e.D
e
q
u
e
u
e(
v
erte
x
)
;
i
f
(
v
ertex
=
=
e
n
d
V
erte
x
)
f
o
u
nd
=
tru
e
;
(
c
o
n
t
inue
s
)
229
e
l
s
e
{i
f
(
!
gra
p
h
.
I
s
M
a
r
k
e
d
(
v
erte
x)
)
{graph
.
M
a
r
k
V
erte
x
(
v
erte
x
)
;
gra
p
h
.
G
e
t
T
o
V
ert
i
c
es
(
v
erte
x
,
v
erte
xQ)
;
w
h
i
l
e(
!
v
ert
x
Q
.I
s
E
m
pt
y
()
)
{v
erte
xQ
.De
q
u
e
u
e
(
i
te
m
)
;
i
f
(
!
graph
.
I
s
M
a
r
k
e
d
(
i
te
m
)
)
q
u
e
u
e
.E
n
q
u
e
u
e(
i
t
e
m
)
;
}
}
}
}
w
h
i
l
e
(
!
q
u
e
u
e
.
I
s
E
m
p
t
y
(
)
&
&
!
f
o
u
n
d
)
;
i
f
(
!
f
o
u
n
d
)
c
o
u
t
<
<
"P
ath
n
o
t
f
o
u
n
d
"
<
<
}
e
n
d
l
;
230
Single
-
sou
r
ce
shor
t
e
s
t
-
p
a
th
p
r
oblem
•
The
r
e
a
r
e
mul
t
i
p
le
p
a
t
hs
f
r
om
a
sou
r
ce
v
e
rt
e
x
t
o
a
de
s
t
i
n
a
t
ion
v
e
rt
e
x
S
h
or
t
e
s
t
p
at
h
:
t
he
p
a
t
h
whose
t
o
t
al
w
e
i
g
h
t
•
(i
.
e.,
sum
of
ed
g
e
w
e
i
g
h
t
s)
i
s
min
i
mum
E
x
amp
l
es:
•
–
Au
s
ti
n
-
>Hou
s
t
o
n
-
>
A
tla
n
t
a
-
>
W
ashi
n
g
t
on:
m
iles
1
5
60
–
Au
s
ti
n
-
>D
a
lla
s
-
>D
e
n
v
er
-
>
A
tla
n
t
a-
>
W
a
shi
n
g
t
on:
2
9
80
m
iles
231
Single-sou
r
c
e
s
h
o
r
t
e
s
t
-p
a
th
p
r
oblem
(
c
o
n
t.)
Com
m
on
a
l
g
o
r
i
t
hms:
D
i
j
k
s
t
ra's
a
l
g
o
r
i
t
hm,
Be
l
l
m
a
n
-
F
ord
a
l
g
o
r
i
t
hm
B
F
S
c
an
b
e
used
t
o
s
o
l
v
e
t
he
sho
r
t
e
s
t
g
r
aph
•
•
p
r
oblem
when
t
he
g
r
aph
is
w
e
ig
h
t
less
t
he
w
e
i
g
h
t
s
a
r
e
t
he
same
(
mark
v
er
t
i
c
es
b
e
f
o
r
e
E
n
qu
e
u
e
)
or
a
l
l
232
A tree in data structures is a finite set of nodes with a designated root and subtrees, including internal nodes and leaf nodes. Terminology like root, parent nodes, leaves, and levels are explained, along with concepts of height and degree of a tree. Additionally, binary trees are introduced as a specific type of tree with distinct left and right subtrees. The transformation of any tree into a binary tree using left child-right sibling representation is discussed.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
UNIT-III Definition of Tree A tree is a finite set of one or more nodes such that: There is a specially designatednode called the root. The remaining nodes are partitioned into n>=0 disjoint sets T1, ..., Tn, where each of these sets is a tree. We call T1, ..., Tn the subtrees of the root. 139
Representation of Tree Level 1 T0 T1 2 T2 T3 T4 T T 3 5 6 Fig.Tree 1 140
Terminology A D B C E F G H Fig.Tree 2 141
ROOT: This is the unique node in the tree to which further subtrees are attached.in the above fig node A is a root node. Degree of the node: The total number of sub-trees attached to the node is called the degree of Node A E 0 Leaves: These are terminal nodesof the tree.The nodes with degree 0 are always the leaf nodes.In above given tree E,F,G,C and H are the leaf nodes. Internal nodes: The nodes other than the root node and the leaves are called the internal nodes.Here B and D are internal nodes. the node. degree 3 142
Parent nodes: The node which is having further sub-trees(branches)is called the parent node of those sub-trees. In the given example node B is parent node of E,F and G nodes. Predecessor: While displaying the tree ,if some particular node occurs previous to some other node then that node is called the predecessor of the other node.In above figure E is a predecessor of the node B. successor: The node which occurs next to some other node is a successor above figure B is successor of F and G. Level of the tree: The root node is always considered at level 0,then its adjacent children are supposed to be at level 1 and so on.In above figure the node A is at level 0,the nodes B,C,D are at level 1,the nodes E,F,G,H are at level 2. node.In 143
Height of the tree: The maximum level is the height of the tree.Here height of the tree is 3.The height of the tree is also called depth of the tree. Degree of tree: The maximum degree of the node is called the degree of the tree. The degree of a node is the number of subtrees of The degree of A is 3; the degree of C is 1. The node with degree 0 is a leaf or terminal node. A node that has subtreesis the parent of the roots of the subtrees. The roots of these subtrees are the children of the node. Children of the same parent are siblings. The ancestors of a node are all the nodes alongthe path from the root to the node. the node 144
Binary Trees A binary tree is a finite set of nodes that is either empty or consists of a root and two disjoint binary trees called the left subtree and the right subtree. Any tree can be transformedinto binary tree. by left child-right sibling representation The left subtree and the right subtree are distinguished. 145
Types Of Binary Trees There are three types of binary trees Left skewed binary tree Right skewed binary tree Complete binary tree 146
Left skewed binary tree If the right subtree is missing in every node of a tree we cal it as left skewed tree. A B C 147
Right skewed binary tree If the left subtree is missing in every node of a tree we call it as right subtree. A B C 148
Completebinary tree The tree in which degree of each node is at the most two is called a complete binary tree.In a complete binary tree there is exactly one node at level 0,twonodes at level 1 and four nodes at level 2 and so on.so we can say that a complete binary tree of depth d will contains exactly level l,where l is from 0 to d. nodes at each 2l A C B D E F G 149
Abstract Data Type Binary_Tree structure Binary_Tree(abbreviatedBinTree)is objects: a finite set of nodes either empty or consisting of a root node, left Binary_Tree, and right Binary_Tree. functions: for all bt, bt1, bt2 BinTree,item Bintree Create()::= createsan empty binary tree BooleanIsEmpty(bt)::= if (bt==empty binary tree) return TRUE else return FALSE element 150
BinTree MakeBT(bt1, item, bt2)::= return a binary tree whose left subtree is bt1, whose right subtree bt2, and whose root Bintree Lchild(bt)::= else element Data(bt)::= else of bt Bintree Rchild(bt)::= if (IsEmpty(bt)) return error else return the right subtree of bt is node contains the data item if (IsEmpty(bt)) return error return the left subtree of bt if (IsEmpty(bt)) return error return the data in the root node 151
Maximum Number of Nodes in BT The maximum number of binary tree is The maximum nubmer of of depth k is 2k-1, k>=1. nodes on level i of a 2i-1, i>=1. nodes in a binary tree Prove by induction. k2i 1 i 1 1 2k 152
Binary Tree Representation Sequential(Arrays) representation Linked representation 153
Array Representation of Binary Tree This representation uses only a single linear array tree as follows: i)The root of the tree is stored in tree[0]. ii)if a node occupies tree[i],then its left child is stored in tree[2*i+1],its right tree[2*i+2],and the parent is 1)/2]. child is stored in stored in tree[(i- 154
Sequential Representation A [1] [2] [3] [4] [5] [6] [7] [8] [9] A B C D E F G H I . . . . B C E G D F . . . . H I 155
Sequential Representation [0] [1] [2] [3] [4] [5] [6] [7] [8] 55 44 66 33 50 55 44 66 50 33 22 22 156
Advantages of sequential representation The only advantage with this type of representation is that the direct access to any node can be possible and findingthe parent or left right children of any particular node is fast because of the random access. 157
Disadvantages of sequential representation The major disadvantage with this type of representation is wastage of memory. The maximumdepth of the tree has to be fixed. The insertions and deletion of any node in tree will be adjusted at meaning of binary tree can be preserved. the costlier as other nodes has to be appropraite positions so that the 158
Linked Representation struct node { int data; struct }; node * left_child, *right_child; data right_child left_child data right_child left_child 159
Linked Representation root 55 44 66 X X 50 X X 33 X 55,44,66,33,50,22 X 22 X 160
Advantages of Linked representation This representation is superior to our representation as there is no wastage of memory. Insertions and deletions which are the most common operations other nodes. can be done without moving the 161
Disadvantages of linked representation This representation does not provide direct access to a node and special algorithms are required. This representationneeds additional space in each node trees. for storing the left and right sub- 162
Full BT VS Complete BT A binary tree with n nodes and depth k is completeiff its nodes correspondto the nodes numberedfrom 1 to n in the full binary tree of depth k. A full binary tree of depth k is a binary tree of depth k having A k 2 -1 nodes, k>=0. A B C B C G D F E F G E D H I N O M L J I K H 163 Complete binary tree Full binary tree of depth 4
Binary Tree Traversals The process of going through a tree in such a way that each node is visted once is tree traversal.several method are used for tree traversal.the traversal in a binary activities such as: Visiting the root Traverse left subtree Traverse right subtree tree involves three kinds of basic 164
We will use some notations to traverse a given binary tree as follows: L means move to the Left child. R means move to the Right child. D means the root/parentnode. The only difference among the methods is the order in which these three operations are performed. There are three standard ways empty binary tree namely : Preorder Inorder Postorder of traversing a non 165
Preorder(also known as depth-first order) 1.Visit the 2.Traverse 3.Traverse root(D) the the left subtree in preorder(L) right subtree in preorder(R) Print 1st A Print 2nd B Print 4th D Print 3rd E C Print at the last A-B-C-D-E is the preorder traversal of the above figure. 166
Inorder(also known as symmetric order) 1.Traverse 2.Visit the 3.Traverse the left subtree in Inorder(L) root(D) the right subtree in Inorder(R) A Print 3rd Print 2nd B Print 4th D Print 1st E C Print at the last C-B-A-D-E figure. is the Inorder traversal of the above 167
Postorder 1.Traverse 2.Traverse 3.Visit the the left subtree in postorder(L) the right root(D) subtree in postorder(R) Print at the last A Print 3rd B Print 4th D Print 1st E C Print 2nd C-D-B-E-A is the postorder traversal of the above figure. 168
Binary tree traversals A A B C B C G D F E G D F E J H I K H I J FIG(a) FIG(b) Preorder:ABDHIECFJKG Inorder:HDIBEAJFKCG Postorder:HIDEBJKFGCA preorder inorder: postorder:HIDJEBFGCA :ABDHIEJCFG HDIBJEAFCG 169
Arithmetic Expression Using BT inorder traversal A / B * C * D + E infix expression preorder traversal + * * / A B C D E prefix expression postorder traversal A B / C * D * E + postfix expression level order traversal + * E * D / C A B + * E * D C / B A 170
Inorder Traversal (recursive version) void inorder(tree_pointer ptr) /* { if (ptr) { inorder(ptr->left_child); printf( %d , ptr->data); indorder(ptr->right_child); } } inorder tree traversal */ A / B * C * D + E 171
Preorder Traversal (recursive void preorder(tree_pointerptr) version) /* preorder tree { if (ptr) { printf( %d , ptr->data); preorder(ptr->left_child); predorder(ptr->right_child); } } traversal */ + * * / A B C D E 172
Postorder Traversal (recursive version) void postorder(tree_pointerptr) /* postorder tree traversal */ { A B / C * D * E + if (ptr) { postorder(ptr->left_child); postdorder(ptr->right_child); printf( %d ,ptr->data); } 173 }
Iterative Inorder Traversal (using stack) iter_inorder(tree_pointer node) void { int top= -1; /* initialize stack */ tree_pointer stack[MAX_STACK_SIZE]; for (;;) { for (; node; node=node->left_child) add(&top, node);/* add to stack */ node= delete(&top); /* delete from stack */ if (!node) break; /* empty stack */ printf( %D , node->data); node = node->right_child; } } O(n) 174
Trace Operations of Inorder Traversal Call of inorder Value in root Action 1 2 3 4 5 6 5 7 4 8 9 8 10 3 Call of inorder Value in root Action 11 12 11 13 2 14 15 14 16 1 17 18 17 19 + * * / A NULL A NULL / B NULL B NULL * C NULL C NULL * D NULL D NULL + E NULL E NULL printf printf printf printf printf printf printf printf printf 175
Level Order Traversal (using queue) void level_order(tree_pointer ptr) /* { int front = rear = 0; tree_pointer queue[MAX_QUEUE_SIZE]; if (!ptr) return; /* empty queue */ addq(front, &rear, ptr); for (;;) { ptr = deleteq(&front, rear); level order tree traversal */ 176
if (ptr) { printf( %d , ptr->data); if (ptr->left_child) addq(front, &rear, ptr->left_child); if (ptr->right_child) addq(front, &rear, ptr->right_child); } else break; } + * E * D / C A B } 177
Copying Binary Trees tree_poointer { tree_pointer temp; if (original) { temp=(tree_pointer) malloc(sizeof(node)); if (IS_FULL(temp)) { fprintf(stderr, exit(1); } temp->left_child=copy(original->left_child); temp->right_child=copy(original->right_child temp->data=original->data; return } return } copy(tree_pointer original) the memory is full\n ); temp; postorder NULL; 178
Post-order-evalfunction void post_order_eval(tree_pointer node) { /* modified post order traversal to evaluate a propositional calculus tree */ if (node) { post_order_eval(node->left_child); post_order_eval(node->right_child); switch(node->data) { case not: node->value = !node->right_child->value; break; 179
case and: node->value = node->right_child->value && node->left_child->value; break; case or: node->value = node->right_child->value | | node->left_child->value; break; case true: break; case false: } node->value = TRUE; node->value = FALSE; } } 180
Threaded Binary Trees Two many null pointers in current of binary trees n: number of nodes number of non-null links: n-1 total links: 2n null links: 2n-(n-1)=n+1 representatio Replace these threads . null pointers with some useful 181
Threaded Binary Trees (Continued) If ptr->left_child is replace it with a pointer visited before ptr in an null, to the node that would inorder traversal be If ptr->right_childis null, replace it with a pointer to the node that visited after ptr in an inorder traversal would be 182
A Threaded Binary Tree root A dangling C B dangling G F E D inorder traversal: H, D, I, B, E, A, F, C, G I H 183
Data Structures for Threaded BT left_thread left_child data right_child right_thread TRUE FALSE FALSE: child TRUE: thread typedef struct threaded_tree *threaded_pointer; typedef struct threaded_tree { short int left_thread; threaded_pointer left_child; char data; threaded_pointer right_child; short int right_thread; }; 184
Memory Representation of A Threaded BT root -- f f A f f C B f f f f G F E D t t t t f t f I H t t t t 185
Next Node in Threaded BT threaded_pointer tree) { threaded_pointer temp; temp = tree->right_child; if (!tree->right_thread) while (!temp->left_thread) temp = temp->left_child; return temp; } insucc(threaded_pointer 186
Inorder Traversal of Threaded BT void { /* traverse the threaded binary tree inorder */ threaded_pointer temp = tree; for (;;) temp = insucc(temp); if (temp==tree) break; printf( %3c , temp->data); } O(n)(timecomplexity) } tinorder(threaded_pointer tree) { 187
Inserting Nodes into Threaded BTs Insert child as the right child of node parent set child->left_threadand child->right_thread to TRUE change parent->right_childto point to child change parent->right_thread to FALSE child->left_childto point to parent set set child->right_childto parent->right_child 188
