Chapter 11: Trees

Prove

\({\bf{a)}}\)part \(\left( {ii} \right)\) of Theorem \(4\).

\({\bf{b)}}\)part \(\left( {{\bf{iii}}} \right)\) of Theorem \(4\).

Show that if there are \(r\) trees in the forest at some intermediate step of Sollin’s algorithm, then at least \(\left\lceil {\frac{r}{2}} \right\rceil \)edges are added by the next iteration of the algorithm.

Show that postorder traversals of these two ordered rooted trees produce the same list of vertices. Note that this does not contradict the statement in Exercise 27, because the numbers of children of internal vertices in the two ordered rooted trees differ.

Well-formed formulae in prefix notation over a set of symbols and a set of binary operators are defined recursively by these rules:

1. If x is a symbol, then x is a well-formed formula in prefix notation;
2. If X and Y are well-formed formulae and * is an operator, then * XY is a well-formed formula.

Using the symbols \({\bf{0, 1, and 2}}\) use ternary \(\left( {{\bf{m = 3}}} \right)\)Huffman coding to encode these letters with the givenfrequencies: \({\bf{A:0}}{\bf{.25, E:0}}{\bf{.30, N:0}}{\bf{.10, R:0}}{\bf{.05, T:0}}{\bf{.12, Z:0}}{\bf{.18}}\).

Show that a cactus is formed if we add a circuit containing new edges beginning and ending at a vertex of a tree.

Build a binary search tree for the word’s oenology,phrenology, campanology, ornithology, ichthyology, limnology, alchemy, and astrology using alphabetical order.

In Exercises 1 – 3 construct the universal address system for the given ordered rooted tree. Then use this to order its vertices using the lexicographic order of their labels.

Which of these graphs are trees?

In Exercises 2–6 find a spanning tree for the graph shown by removing edges in simple circuits.

Use Prim's algorithm to find a minimum spanning tree for the given weighted graph.