Second level
Third level
Fourth level
Fifth level
‹date/time›
‹footer›
‹#›
------=_NextPart_01C57BFE.43772AC0
Content-Location: file:///C:/0C98E5E2/ch08-B_files/master04.xml
Content-Transfer-Encoding: quoted-printable
Content-Type: text/xml; charset="utf-8"
Trees
Chapter 8
Chapter 8: Trees
2
Heaps and Priority Queues
&#=
8226;In
a heap, the value in a node is less than all values in its two subtrees=
3;
&#=
8226;A
heap is a complete binary tree with the following properties
&#=
8226;The
value in the root is the smallest item in the tree
&=
#8226;Every
subtree is a heap
![](3D"slide0028_image002.jpg")
Chapter 8: Trees
3
Inserting an Item into a Heap
![](3D"slide0044_image004.jpg")
![](3D"slide0044_image006.jpg")
Chapter 8: Trees
4
Removing an Item from a Heap
![](3D"slide0029_image008.jpg")
![](3D"slide0029_image010.jpg")
Chapter 8: Trees
5
Implementing a Heap
<=
span
class=3DBB style=3D'position:absolute;left:-4.43%'>•Because a=
heap is
a complete binary tree, it can be implemented efficiently using an array
instead of a linked data structure
<=
nobr>•First elem=
ent for
storing a reference to the root data
<=
span
class=3DBB style=3D'position:absolute;left:-4.43%'>•Use next =
two
elements for storing the two children of the root
<=
span
class=3DBB style=3D'position:absolute;left:-4.43%'>•Use eleme=
nts with
subscripts 3, 4, 5, and 6 for storing the four children of these two nodes=
and
so on
![](3D"slide0030_image012.jpg")
Chapter 8: Trees
6
Inserting into a Heap
Implemented as an ArrayList
![](3D"slide0031_image014.jpg")
![](3D"slide0031_image016.jpg")
Chapter 8: Trees
7
Inserting into a Heap
Implemented as an ArrayList (continued)
![](3D"slide0032_image018.gif")
Chapter 8: Trees
8
Priority Queues
&#=
8226;The
heap is used to implement a special kind of queue called a priority queue&=
#13;
&#=
8226;Will
not create a Heap interface or code a class that implements
it
&#=
8226;Will
incorporate its algorithms when we implement a priority queue c=
lass
and Heapsort
&#=
8226;Sometimes
a FIFO queue may not be the best way to implement a waiting line
&#=
8226;A
priority queue is a data structure in which only the highest-priority item=
is
accessible
Chapter 8: Trees
9
Huffman Trees
&#=
8226;A
Huffman tree can be implemented using a binary tree and a PriorityQueue=
3;
&#=
8226;A
straight binary encoding of an alphabet assigns a unique binary number to =
each
symbol in the alphabet
&=
#8226;Unicode
for example
&#=
8226;The
message “go eagles” requires 144 bits in Unicode but only 38 u=
sing
Huffman coding
Chapter 8: Trees
10
Huffman Trees (continued)
![](3D"slide0047_image020.jpg")
Chapter 8: Trees
11
Huffman Trees (continued)
![](3D"slide0039_image022.jpg")
Chapter 8: Trees
12
Chapter Review
<=
span
class=3DBB style=3D'position:absolute;left:-4.43%'>•A tree is=
a
recursive, nonlinear data structure that is used to represent data that is
organized as a hierarchy
<=
span
class=3DBB style=3D'position:absolute;left:-4.43%'>•A binary =
tree is
a collection of nodes with three components: a reference to a data object,=
a
reference to a left subtree, and a reference to a right subtree
<=
span
class=3DBB style=3D'position:absolute;left:-4.43%'>•In a bina=
ry tree
used for arithmetic expressions, the root node should store the operator t=
hat
is evaluated last
<=
span
class=3DBB style=3D'position:absolute;left:-4.43%'>•A binary =
search
tree is a tree in which the data stored in the left subtree of every node =
is
less than the data stored in the root node, and the data stored in the rig=
ht
subtree is greater than the data stored in the root node
Chapter 8: Trees
13
Chapter Review (continued)
<=
span
class=3DBB style=3D'position:absolute;left:-4.43%'>•A heap is=
a
complete binary tree in which the data in each node is less than the data =
in
both its subtrees
<=
nobr>•Insertion=
and
removal in a heap are both O(log n)
<=
span
class=3DBB style=3D'position:absolute;left:-4.43%'>•A Huffman=
tree is
a binary tree used to store a code that facilitates file compression
<=
/span>
<=
nobr>
‹header›
‹date/time›=
Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level
‹footer›
‹#›
------=_NextPart_01C57BFE.43772AC0
Content-Location: file:///C:/0C98E5E2/ch08-B_files/master04_stylesheet.css
Content-Transfer-Encoding: base64
Content-Type: text/css
Ym9keQ0KCXt3aWR0aDo1MzRweDsNCgloZWlnaHQ6NDAwcHg7fQ0KLlRCDQoJe21zby1zcGVjaWFs
LWZvcm1hdDpub2J1bGxldFwyMDIyO30NCi5UDQoJe3RleHQtYWxpZ246Y2VudGVyOw0KCWZvbnQt
ZmFtaWx5OkFyaWFsOw0KCW1zby1iaWRpLWZvbnQtZmFtaWx5OkFyaWFsOw0KCWNvbG9yOmJsYWNr
Ow0KCW1zby1jb2xvci1pbmRleDozOw0KCWZvbnQtc2l6ZToxNTIlOw0KCW1zby1jaGFyLXdyYXA6
MTsNCgltc28ta2luc29rdS1vdmVyZmxvdzoxO30NCi5CQg0KCXttc28tc3BlY2lhbC1mb3JtYXQ6
YnVsbGV0XDIwMjI7fQ0KLkINCgl7dGV4dC1hbGlnbjpqdXN0aWZ5Ow0KCWZvbnQtZmFtaWx5OkFy
aWFsOw0KCW1zby1iaWRpLWZvbnQtZmFtaWx5OkFyaWFsOw0KCWNvbG9yOmJsYWNrOw0KCW1zby1j
b2xvci1pbmRleDoxOw0KCWZvbnQtc2l6ZToxMTQlOw0KCW1zby1jaGFyLXdyYXA6MTsNCgltc28t
a2luc29rdS1vdmVyZmxvdzoxO30NCi5CMUINCgl7bXNvLXNwZWNpYWwtZm9ybWF0OmJ1bGxldFwy
MDIyO30NCi5CMQ0KCXt0ZXh0LWFsaWduOmxlZnQ7DQoJZm9udC1mYW1pbHk6QXJpYWw7DQoJbXNv
LWJpZGktZm9udC1mYW1pbHk6QXJpYWw7DQoJY29sb3I6YmxhY2s7DQoJbXNvLWNvbG9yLWluZGV4
OjE7DQoJZm9udC1zaXplOjExNCU7DQoJbXNvLWNoYXItd3JhcDoxOw0KCW1zby1raW5zb2t1LW92
ZXJmbG93OjE7fQ0KLkIyQg0KCXttc28tc3BlY2lhbC1mb3JtYXQ6YnVsbGV0XDIwMjI7fQ0KLkIy
DQoJe3RleHQtYWxpZ246bGVmdDsNCglmb250LWZhbWlseTpBcmlhbDsNCgltc28tYmlkaS1mb250
LWZhbWlseTpBcmlhbDsNCgljb2xvcjpibGFjazsNCgltc28tY29sb3ItaW5kZXg6MTsNCglmb250
LXNpemU6OTUlOw0KCW1zby1jaGFyLXdyYXA6MTsNCgltc28ta2luc29rdS1vdmVyZmxvdzoxO30N
Ci5CM0INCgl7bXNvLXNwZWNpYWwtZm9ybWF0OmJ1bGxldFwyMDEzO30NCi5CMw0KCXt0ZXh0LWFs
aWduOmxlZnQ7DQoJZm9udC1mYW1pbHk6QXJpYWw7DQoJbXNvLWJpZGktZm9udC1mYW1pbHk6QXJp
YWw7DQoJY29sb3I6YmxhY2s7DQoJbXNvLWNvbG9yLWluZGV4OjE7DQoJZm9udC1zaXplOjg1JTsN
Cgltc28tY2hhci13cmFwOjE7DQoJbXNvLWtpbnNva3Utb3ZlcmZsb3c6MTt9DQouQjRCDQoJe21z
by1zcGVjaWFsLWZvcm1hdDpidWxsZXRcMDBCQjt9DQouQjQNCgl7dGV4dC1hbGlnbjpsZWZ0Ow0K
CWZvbnQtZmFtaWx5OkFyaWFsOw0KCW1zby1iaWRpLWZvbnQtZmFtaWx5OkFyaWFsOw0KCWNvbG9y
OmJsYWNrOw0KCW1zby1jb2xvci1pbmRleDoxOw0KCWZvbnQtc2l6ZTo3NiU7DQoJbXNvLWNoYXIt
d3JhcDoxOw0KCW1zby1raW5zb2t1LW92ZXJmbG93OjE7fQ0KLk5CDQoJe21zby1zcGVjaWFsLWZv
cm1hdDpub2J1bGxldFwyMDIyO30NCi5ODQoJe3RleHQtYWxpZ246bGVmdDsNCglmb250LWZhbWls
eTpBcmlhbDsNCgltc28tYmlkaS1mb250LWZhbWlseTpBcmlhbDsNCgljb2xvcjpibGFjazsNCglt
c28tY29sb3ItaW5kZXg6MTsNCglmb250LXNpemU6NTclOw0KCW1zby1jaGFyLXdyYXA6MTsNCglt
c28ta2luc29rdS1vdmVyZmxvdzoxO30NCi5OMUINCgl7bXNvLXNwZWNpYWwtZm9ybWF0Om5vYnVs
bGV0XDIwMjI7fQ0KLk4xDQoJe3RleHQtYWxpZ246bGVmdDsNCglmb250LWZhbWlseTpBcmlhbDsN
Cgltc28tYmlkaS1mb250LWZhbWlseTpBcmlhbDsNCgljb2xvcjpibGFjazsNCgltc28tY29sb3It
aW5kZXg6MTsNCglmb250LXNpemU6NTclOw0KCW1zby1jaGFyLXdyYXA6MTsNCgltc28ta2luc29r
dS1vdmVyZmxvdzoxO30NCi5OMkINCgl7bXNvLXNwZWNpYWwtZm9ybWF0Om5vYnVsbGV0XDIwMjI7
fQ0KLk4yDQoJe3RleHQtYWxpZ246bGVmdDsNCglmb250LWZhbWlseTpBcmlhbDsNCgltc28tYmlk
aS1mb250LWZhbWlseTpBcmlhbDsNCgljb2xvcjpibGFjazsNCgltc28tY29sb3ItaW5kZXg6MTsN
Cglmb250LXNpemU6NTclOw0KCW1zby1jaGFyLXdyYXA6MTsNCgltc28ta2luc29rdS1vdmVyZmxv
dzoxO30NCi5OM0INCgl7bXNvLXNwZWNpYWwtZm9ybWF0Om5vYnVsbGV0XDIwMjI7fQ0KLk4zDQoJ
e3RleHQtYWxpZ246bGVmdDsNCglmb250LWZhbWlseTpBcmlhbDsNCgltc28tYmlkaS1mb250LWZh
bWlseTpBcmlhbDsNCgljb2xvcjpibGFjazsNCgltc28tY29sb3ItaW5kZXg6MTsNCglmb250LXNp
emU6NTclOw0KCW1zby1jaGFyLXdyYXA6MTsNCgltc28ta2luc29rdS1vdmVyZmxvdzoxO30NCi5O
NE4NCgl7bXNvLXNwZWNpYWwtZm9ybWF0Om5vYnVsbGV0XDIwMjI7fQ0KLk40DQoJe3RleHQtYWxp
Z246bGVmdDsNCglmb250LWZhbWlseTpBcmlhbDsNCgltc28tYmlkaS1mb250LWZhbWlseTpBcmlh
bDsNCgljb2xvcjpibGFjazsNCgltc28tY29sb3ItaW5kZXg6MTsNCglmb250LXNpemU6NTclOw0K
CW1zby1jaGFyLXdyYXA6MTsNCgltc28ta2luc29rdS1vdmVyZmxvdzoxO30NCi5PQg0KCXttc28t
c3BlY2lhbC1mb3JtYXQ6bm9idWxsZXRcMjAyMjt9DQouTw0KCXt0ZXh0LWFsaWduOmxlZnQ7DQoJ
Zm9udC1mYW1pbHk6QXJpYWw7DQoJbXNvLWJpZGktZm9udC1mYW1pbHk6QXJpYWw7DQoJY29sb3I6
YmxhY2s7DQoJbXNvLWNvbG9yLWluZGV4OjE7DQoJZm9udC1zaXplOjg1JTsNCgltc28tY2hhci13
cmFwOjE7DQoJbXNvLWtpbnNva3Utb3ZlcmZsb3c6MTt9DQouTzENCgl7Zm9udC1mYW1pbHk6QXJp
YWw7DQoJbXNvLWJpZGktZm9udC1mYW1pbHk6QXJpYWw7DQoJbXNvLWNoYXItd3JhcDoxOw0KCW1z
by1raW5zb2t1LW92ZXJmbG93OjE7fQ0KLk8yDQoJe2ZvbnQtZmFtaWx5OkFyaWFsOw0KCW1zby1i
aWRpLWZvbnQtZmFtaWx5OkFyaWFsOw0KCW1zby1jaGFyLXdyYXA6MTsNCgltc28ta2luc29rdS1v
dmVyZmxvdzoxO30NCi5PMw0KCXtmb250LWZhbWlseTpBcmlhbDsNCgltc28tYmlkaS1mb250LWZh
bWlseTpBcmlhbDsNCgltc28tY2hhci13cmFwOjE7DQoJbXNvLWtpbnNva3Utb3ZlcmZsb3c6MTt9
DQouTzQNCgl7Zm9udC1mYW1pbHk6QXJpYWw7DQoJbXNvLWJpZGktZm9udC1mYW1pbHk6QXJpYWw7
DQoJbXNvLWNoYXItd3JhcDoxOw0KCW1zby1raW5zb2t1LW92ZXJmbG93OjE7fQ0KLkNCQg0KCXtt
c28tc3BlY2lhbC1mb3JtYXQ6bm9idWxsZXRcMjAyMjt9DQouQ0INCgl7dGV4dC1hbGlnbjpjZW50
ZXI7DQoJZm9udC1mYW1pbHk6QXJpYWw7DQoJbXNvLWJpZGktZm9udC1mYW1pbHk6QXJpYWw7DQoJ
Y29sb3I6YmxhY2s7DQoJbXNvLWNvbG9yLWluZGV4OjE7DQoJZm9udC1zaXplOjExNCU7DQoJbXNv
LWNoYXItd3JhcDoxOw0KCW1zby1raW5zb2t1LW92ZXJmbG93OjE7fQ0KLkNCMUINCgl7bXNvLXNw
ZWNpYWwtZm9ybWF0Om5vYnVsbGV0XDIwMjI7fQ0KLkNCMQ0KCXtmb250LWZhbWlseTpBcmlhbDsN
Cgltc28tYmlkaS1mb250LWZhbWlseTpBcmlhbDsNCglmb250LXNpemU6MTE0JTsNCgltc28tY2hh
ci13cmFwOjE7DQoJbXNvLWtpbnNva3Utb3ZlcmZsb3c6MTt9DQouQ0IyDQoJe2ZvbnQtZmFtaWx5
OkFyaWFsOw0KCW1zby1iaWRpLWZvbnQtZmFtaWx5OkFyaWFsOw0KCWZvbnQtc2l6ZTo5NSU7DQoJ
bXNvLWNoYXItd3JhcDoxOw0KCW1zby1raW5zb2t1LW92ZXJmbG93OjE7fQ0KLkNCMw0KCXtmb250
LWZhbWlseTpBcmlhbDsNCgltc28tYmlkaS1mb250LWZhbWlseTpBcmlhbDsNCglmb250LXNpemU6
ODUlOw0KCW1zby1jaGFyLXdyYXA6MTsNCgltc28ta2luc29rdS1vdmVyZmxvdzoxO30NCi5DQjQN
Cgl7Zm9udC1mYW1pbHk6QXJpYWw7DQoJbXNvLWJpZGktZm9udC1mYW1pbHk6QXJpYWw7DQoJZm9u
dC1zaXplOjc2JTsNCgltc28tY2hhci13cmFwOjE7DQoJbXNvLWtpbnNva3Utb3ZlcmZsb3c6MTt9
DQouQ1RCDQoJe21zby1zcGVjaWFsLWZvcm1hdDpub2J1bGxldFwyMDIyO30NCi5DVA0KCXt0ZXh0
LWFsaWduOmNlbnRlcjsNCglmb250LWZhbWlseTpBcmlhbDsNCgltc28tYmlkaS1mb250LWZhbWls
eTpBcmlhbDsNCgljb2xvcjpibGFjazsNCgltc28tY29sb3ItaW5kZXg6MzsNCglmb250LXNpemU6
MTUyJTsNCgltc28tY2hhci13cmFwOjE7DQoJbXNvLWtpbnNva3Utb3ZlcmZsb3c6MTt9DQouSEIN
Cgl7dGV4dC1hbGlnbjpqdXN0aWZ5Ow0KCWZvbnQtZmFtaWx5OkFyaWFsOw0KCW1zby1iaWRpLWZv
bnQtZmFtaWx5OkFyaWFsOw0KCWZvbnQtc2l6ZTo5NSU7DQoJbXNvLWNoYXItd3JhcDoxOw0KCW1z
by1raW5zb2t1LW92ZXJmbG93OjE7fQ0KLkhCMUINCgl7bXNvLXNwZWNpYWwtZm9ybWF0OmJ1bGxl
dFwyMDIyO30NCi5IQjENCgl7Zm9udC1mYW1pbHk6QXJpYWw7DQoJbXNvLWJpZGktZm9udC1mYW1p
bHk6QXJpYWw7DQoJZm9udC1zaXplOjk1JTsNCgltc28tY2hhci13cmFwOjE7DQoJbXNvLWtpbnNv
a3Utb3ZlcmZsb3c6MTt9DQouSEIyDQoJe2ZvbnQtZmFtaWx5OkFyaWFsOw0KCW1zby1iaWRpLWZv
bnQtZmFtaWx5OkFyaWFsOw0KCWZvbnQtc2l6ZTo4NSU7DQoJbXNvLWNoYXItd3JhcDoxOw0KCW1z
by1raW5zb2t1LW92ZXJmbG93OjE7fQ0KLkhCMw0KCXtmb250LWZhbWlseTpBcmlhbDsNCgltc28t
YmlkaS1mb250LWZhbWlseTpBcmlhbDsNCglmb250LXNpemU6NzYlOw0KCW1zby1jaGFyLXdyYXA6
MTsNCgltc28ta2luc29rdS1vdmVyZmxvdzoxO30NCi5IQjQNCgl7Zm9udC1mYW1pbHk6QXJpYWw7
DQoJbXNvLWJpZGktZm9udC1mYW1pbHk6QXJpYWw7DQoJZm9udC1zaXplOjY2JTsNCgltc28tY2hh
ci13cmFwOjE7DQoJbXNvLWtpbnNva3Utb3ZlcmZsb3c6MTt9DQouUUINCgl7dGV4dC1hbGlnbjpq
dXN0aWZ5Ow0KCWZvbnQtZmFtaWx5OkFyaWFsOw0KCW1zby1iaWRpLWZvbnQtZmFtaWx5OkFyaWFs
Ow0KCWZvbnQtc2l6ZTo4NSU7DQoJbXNvLWNoYXItd3JhcDoxOw0KCW1zby1raW5zb2t1LW92ZXJm
bG93OjE7fQ0KLlFCMUINCgl7bXNvLXNwZWNpYWwtZm9ybWF0OmJ1bGxldFwyMDIyO30NCi5RQjEN
Cgl7Zm9udC1mYW1pbHk6QXJpYWw7DQoJbXNvLWJpZGktZm9udC1mYW1pbHk6QXJpYWw7DQoJZm9u
dC1zaXplOjg1JTsNCgltc28tY2hhci13cmFwOjE7DQoJbXNvLWtpbnNva3Utb3ZlcmZsb3c6MTt9
DQouUUIyDQoJe2ZvbnQtZmFtaWx5OkFyaWFsOw0KCW1zby1iaWRpLWZvbnQtZmFtaWx5OkFyaWFs
Ow0KCWZvbnQtc2l6ZTo3NiU7DQoJbXNvLWNoYXItd3JhcDoxOw0KCW1zby1raW5zb2t1LW92ZXJm
bG93OjE7fQ0KLlFCMw0KCXtmb250LWZhbWlseTpBcmlhbDsNCgltc28tYmlkaS1mb250LWZhbWls
eTpBcmlhbDsNCglmb250LXNpemU6NjYlOw0KCW1zby1jaGFyLXdyYXA6MTsNCgltc28ta2luc29r
dS1vdmVyZmxvdzoxO30NCi5RQjQNCgl7Zm9udC1mYW1pbHk6QXJpYWw7DQoJbXNvLWJpZGktZm9u
dC1mYW1pbHk6QXJpYWw7DQoJZm9udC1zaXplOjU3JTsNCgltc28tY2hhci13cmFwOjE7DQoJbXNv
LWtpbnNva3Utb3ZlcmZsb3c6MTt9DQouVGJsDQoJe3RleHQtYWxpZ246anVzdGlmeTsNCglmb250
LWZhbWlseTpBcmlhbDsNCgltc28tYmlkaS1mb250LWZhbWlseTpBcmlhbDsNCglmb250LXNpemU6
OTUlOw0KCW1zby1jaGFyLXdyYXA6MTsNCgltc28ta2luc29rdS1vdmVyZmxvdzoxO30NCi5UYmwx
Qg0KCXttc28tc3BlY2lhbC1mb3JtYXQ6bm9idWxsZXRcMjAyMjt9DQouVGJsMQ0KCXtmb250LWZh
bWlseTpBcmlhbDsNCgltc28tYmlkaS1mb250LWZhbWlseTpBcmlhbDsNCglmb250LXNpemU6OTUl
Ow0KCW1zby1jaGFyLXdyYXA6MTsNCgltc28ta2luc29rdS1vdmVyZmxvdzoxO30NCi5UYmwyDQoJ
e2ZvbnQtZmFtaWx5OkFyaWFsOw0KCW1zby1iaWRpLWZvbnQtZmFtaWx5OkFyaWFsOw0KCWZvbnQt
c2l6ZTo4NSU7DQoJbXNvLWNoYXItd3JhcDoxOw0KCW1zby1raW5zb2t1LW92ZXJmbG93OjE7fQ0K
LlRibDMNCgl7Zm9udC1mYW1pbHk6QXJpYWw7DQoJbXNvLWJpZGktZm9udC1mYW1pbHk6QXJpYWw7
DQoJZm9udC1zaXplOjc2JTsNCgltc28tY2hhci13cmFwOjE7DQoJbXNvLWtpbnNva3Utb3ZlcmZs
b3c6MTt9DQouVGJsNA0KCXtmb250LWZhbWlseTpBcmlhbDsNCgltc28tYmlkaS1mb250LWZhbWls
eTpBcmlhbDsNCglmb250LXNpemU6NjYlOw0KCW1zby1jaGFyLXdyYXA6MTsNCgltc28ta2luc29r
dS1vdmVyZmxvdzoxO30NCi5kZWZhdWx0Qg0KCXttc28tc3BlY2lhbC1mb3JtYXQ6bm9idWxsZXRc
MjAyMjt9DQouZGVmYXVsdA0KCXt0ZXh0LWFsaWduOmxlZnQ7DQoJZm9udC1mYW1pbHk6QXJpYWw7
DQoJbXNvLWFzY2lpLWZvbnQtZmFtaWx5OkFyaWFsOw0KCW1zby1iaWRpLWZvbnQtZmFtaWx5OkFy
aWFsOw0KCWZvbnQtd2VpZ2h0Om5vcm1hbDsNCglmb250LXN0eWxlOm5vcm1hbDsNCgl0ZXh0LWRl
Y29yYXRpb246bm9uZTsNCgl0ZXh0LXNoYWRvdzpub25lOw0KCXRleHQtZWZmZWN0Om5vbmU7DQoJ
bXNvLWZhcmVhc3QtaGludDpubzsNCglsYXlvdXQtZmxvdzpob3Jpem9udGFsOw0KCWNvbG9yOmJs
YWNrOw0KCW1zby1jb2xvci1pbmRleDoxOw0KCWZvbnQtc2l6ZTo4NSU7DQoJbXNvLXRleHQtcmFp
c2U6MCU7DQoJbXNvLWxpbmUtc3BhY2luZzoiMTAwIDAgMCI7DQoJbXNvLW1hcmdpbi1sZWZ0LWFs
dDowOw0KCW1zby10ZXh0LWluZGVudC1hbHQ6MDsNCgltc28tY2hhci13cmFwOjE7DQoJbXNvLWtp
bnNva3Utb3ZlcmZsb3c6MTsNCglkaXJlY3Rpb246bHRyOw0KCW1zby13b3JkLXdyYXA6MTsNCglt
c28tdmVydGljYWwtYWxpZ24tc3BlY2lhbDpiYXNlbGluZTsNCgltc28tYW5zaS1sYW5ndWFnZTpF
Ti1VUzt9DQphOmxpbmsNCgl7Y29sb3I6IzAwOTk5OSAhaW1wb3J0YW50O30NCmE6YWN0aXZlDQoJ
e2NvbG9yOiMzMzMzOTkgIWltcG9ydGFudDt9DQphOnZpc2l0ZWQNCgl7Y29sb3I6Izk5Q0MwMCAh
aW1wb3J0YW50O30NCn==
------=_NextPart_01C57BFE.43772AC0
Content-Location: file:///C:/0C98E5E2/ch08-B_files/script.js
Content-Transfer-Encoding: quoted-printable
Content-Type: application/javascript; charset="us-ascii"
function LoadSld()
{
var sld=3DGetObj("SlideObj")
if( !g_supportsPPTHTML ) { =09
sld.style.visibility=3D"visible"
return
}
if( MakeNotesVis() ) return
runAnimations =3D _InitAnimations();
=09
if( IsWin("PPTSld") )
parent.SldUpdated(GetSldId())
g_origSz=3DparseInt(SlideObj.style.fontSize)
g_origH=3Dsld.style.posHeight
g_origW=3Dsld.style.posWidth
g_scaleHyperlinks=3D(document.all.tags("AREA").length>0)
if( g_scaleHyperlinks )
InitHLinkArray()
if( g_scaleInFrame||(IsWin("PPTSld") && parent.IsFullScrMode() ) )
document.body.scroll=3D"no"
_RSW()
if( IsWin("PPTSld") && parent.IsFullScrMode() )
FullScrInit();
=09
MakeSldVis();
ChkAutoAdv()
if( runAnimations )
{
if( document.all("NSPlay") )
document.all("NSPlay").autoStart =3D false;
if( sld.filters && sld.filters.revealtrans )
setTimeout( "document.body.start()", sld.filters.revealtrans.duration * =
1000 );
else
document.body.start();
}
}
function MakeSldVis()=20
{
var fTrans=3Dg_showAnimation && SldHasTrans()
if( fTrans )=09
{
if( g_bgSound ) {
idx=3Dg_bgSound.indexOf(",");
pptSound.src=3Dg_bgSound.substr( 0, idx );
pptSound.loop=3D -(parseInt(g_bgSound.substr(idx+1)));
}
SlideObj.filters.revealtrans.Apply()=09
}
SlideObj.style.visibility=3D"visible"
if( fTrans )
SlideObj.filters.revealtrans.Play()
}
function MakeNotesVis()=20
{
if( !IsNts() ) return false=20
SlideObj.style.display=3D"none"
nObj =3D document.all.item("NotesObj")
parent.SetHasNts(0)
if( nObj ) {=20
nObj.style.display=3D""
parent.SetHasNts(1)
}
return 1
}
function ChkAutoAdv()
{
if(SldHasTrans())
SlideObj.onfilterchange=3DAutoAdv
else
AutoAdv()
}
function AutoAdv()
{
if(!IsWin("PPTSld") || !gUseSldTimings )return
var sld=3DGetCurSld()
if( (sld.mAdvDelay>0) && !parent.IsFramesMode() )
setTimeout("parent.GoToNextSld()",sld.mAdvDelay)
}
function GetObj(id)
{
if(g_supportsPPTHTML) return document.all(id);
else return document.getElementById(id);
}
function SldHasTrans() { return SlideObj.style.filter !=3D ""; }
function GetSldId() { return sId=3Dlocation.href.substring(location.href.la=
stIndexOf('/')+1) }
function HideMenu() { if( frames["PPTSld"] && PPTSld.document.all.item("ctx=
tmenu") && PPTSld.ctxtmenu.style.display!=3D"none" ) { PPTSld.ctxtmenu.styl=
e.display=3D'none'; return true } return false }
function IsWin( name ) { return window.name =3D=3D name }
function IsNts() { return IsWin("PPTNts") }
function IsSldOrNts() { return( IsWin("PPTSld")||IsWin("PPTNts") ) }
function SupportsPPTAnimation() { return( navigator.platform =3D=3D "Win32"=
&& navigator.appVersion.indexOf("Windows")>0 ) }
function SupportsPPTHTML()
{
var appVer=3Dnavigator.appVersion, msie=3DappVer.indexOf("MSIE "), ver=3D0
if( msie >=3D 0 )
ver=3DparseFloat( appVer.substring( msie+5, appVer.indexOf(";",msie) ) )
else
ver=3DparseInt(appVer)
return( ver >=3D 4 && msie >=3D 0 )
}
function _RSW()
{
if( !g_supportsPPTHTML || IsNts() ||
( !g_scaleInFrame && (!IsWin("PPTSld") || !parent.IsFullScrMode()) ) )
return
var padding=3D0;
if( IsWin("PPTSld") && parent.IsFramesMode() ) padding=3D6
cltWidth=3Ddocument.body.clientWidth-padding
cltHeight=3Ddocument.body.clientHeight-padding
factor=3D(1.0*cltWidth)/g_origW
if( cltHeight < g_origH*factor )
factor=3D(1.0*cltHeight)/g_origH
newSize =3D g_origSz * factor
if( newSize < 1 ) newSize=3D1
s=3DSlideObj.style
s.fontSize=3DnewSize+"px"
s.posWidth=3Dg_origW*factor
s.posHeight=3Dg_origH*factor
s.posLeft=3D(cltWidth-s.posWidth+padding)/2
s.posTop=3D(cltHeight-s.posHeight+padding)/2
if( g_scaleHyperlinks )
ScaleHyperlinks( factor )
}
function _InitAnimations()
{
animRuntimeInstalled =3D ''+document.body.localTime !=3D 'undefined';
isFullScreen =3D (window.name =3D=3D "PPTSld") && !parent.IsFramesMode();
g_animUseRuntime =3D g_showAnimation && animRuntimeInstalled && !(isFullSc=
reen && parent.IsSldVisited());
if( g_animUseRuntime ) {
collSeq =3D document.all.tags("seq");
if( collSeq !=3D null ) {
for(ii=3D0;ii
' + ENDSHOW_MESG + '
![](3D"notes_flag.gif")
No=
tes![](3D"buttons.gif")
![](3D"slide0028_image001.png"){kind=link}
![](3D"slide0044_image003.png"){kind=link}
![](3D"slide0044_image005.png"){kind=link}
![](3D"slide0029_image007.png"){kind=link}
![](3D"slide0029_image009.png"){kind=link}
![](3D"slide0030_image011.png"){kind=link}
![](3D"slide0031_image013.png"){kind=link}
![](3D"slide0031_image015.png"){kind=link}
![](3D"slide0032_image017.png"){kind=link}
![](3D"slide0047_image019.png"){kind=link}
![](3D"slide0039_image021.png"){kind=link}