Chapter 11: Trees

Huffman coding to encode these symbols with given frequencies: \({\bf{A}}:{\rm{ }}{\bf{0}}.{\bf{10}},{\rm{ }}{\bf{B}}:{\rm{ }}{\bf{0}}.{\bf{25}},{\rm{ }}{\bf{C}}:{\rm{ }}{\bf{0}}.{\bf{05}},{\rm{ }}{\bf{D}}:{\rm{ }}{\bf{0}}.{\bf{15}},{\rm{ }}{\bf{E}}:{\rm{ }}{\bf{0}}.{\bf{30}},{\rm{ }}{\bf{F}}:{\rm{ }}{\bf{0}}.{\bf{07}},{\rm{ }}{\bf{G}}:{\rm{ }}{\bf{0}}.{\bf{08}}\). What is the average number of bits required to encode a symbol?

Explain how breadth-first search or depth-first search canbe used to order the vertices of a connected graph.

Either draw a full \({\bf{m - }}\)ary tree with \(76\) leaves and height \(3\), where \({\bf{m}}\) is a positive integer, or show that no such tree exists.

What is the value of each of these postfix expressions?

1. \({\bf{521 - - 314 + + }} * \)
2. \({\bf{93/5 + 72 - }} * \)
3. \(3{\bf{2}} * 2 \uparrow 53{\bf{ - }}84{\bf{/}} * {\bf{ - }}\)

Devise an algorithm for determining if a set of universal addresses can be the addresses of the leaves of a rooted tree.

Show that the length of the shortest path between vertices v and u in a connected simple graph equals the level number of u in the breadth-first spanning tree of G with root v.

Construct two different Huffman codes for these symbols and frequencies: \({\bf{t: 0}}{\bf{.2, u: 0}}{\bf{.3, v: 0}}{\bf{.2, w: 0}}{\bf{.3}}\).

Either draw a full \({\bf{m - }}\)ary tree with \(84\) leaves and height \(3\), where \({\bf{m}}\) is a positive integer, or show that no such tree exists.

Construct the ordered rooted tree whose preorder traversal is a, b, f, c, g, h, i, d, e, j, k, l, where a has four children, c has three children, j has two children, b and e have one child each, and all other vertices are leaves.

Use Sollin's algorithm to produce a minimum spanning tree for the weighted graph shown in

\({\bf{a}})\)Figure \(1\).

\(b)\)Figure \(3\).