Data-Structures-And-Algorithms-Alfred-V-Aho

Data Structures and Algorithms: CHAPTER 3: Trees

Implement the seven tree operations of Section 3.2 using the following tree implementations:

3.16a. parent pointers

b.lists of children

c.leftmost-child, right-sibling pointers.

The degree of a node is the number of children it has. Show that in any

3.17binary tree the number of leaves is one more than the number of nodes of degree two.

Show that the maximum number of nodes in a binary tree of height h is

3.182h+1 - 1. A binary tree of height h with the maximum number of nodes is called a full binary tree.

Suppose trees are implemented by leftmost-child, right-sibling and parent *3.19 pointers. Give nonrecursive preorder, postorder, and inorder traversal

algorithms that do not use "states" or a stack, as Fig. 3.9 does.

Suppose characters a, b, c, d, e, f have probabilities .07, .09, .12, .22, .23,

3.20.27, respectively. Find an optimal Huffman code and draw the Huffman tree. What is the average code length?

Suppose T is a Huffman tree, and that the leaf for symbol a has greater *3.21 depth than the leaf for symbol b. Prove that the probability of symbol b is

no less than that of a.

*3.22

Prove that Huffman's algorithm works, i.e., it produces an optimal code for the given probabilities. Hint: Use Exercise 3.21.

Bibliographic Notes

Berge [1958] and Harary [1969] discuss the mathematical properties of trees. Knuth [1973] and Nievergelt [1974] contain additional information on binary search trees. Many of the works on graphs and applications referenced in Chapter 6 also cover material on trees.

The algorithm given in Section 3.4 for finding a tree with a minimal weighted path length is from Huffman [1952]. Parker [1980] gives some more recent explorations into that algorithm.

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1203.htm (31 of 32) [1.7.2001 19:01:17]

Data Structures and Algorithms: CHAPTER 3: Trees

†Recall our discussion of recursion in Section 2.6 in which we illustrated how the implementation of a recursive procedure involves a stack of activation records. If we examine Fig. 3.8, we can observe that when PREORDER(n) is called, the active procedure calls, and therefore the stack of activation records, correspond to the calls of PREORDER for all the ancestors of n. Thus our nonrecursive preorder procedure, like the example in Section 2.6, models closely the way the recursive procedure is implemented.

†For the data reading phase, which we omit, we also need a cursor for the array ALPHABET as it fills with symbols and their probabilities.

Table of Contents Go to Chapter 4

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1203.htm (32 of 32) [1.7.2001 19:01:17]

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/images/fig2_2.gif

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/images/fig2_2.gif [1.7.2001 19:01:28]

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/images/fig2_4.gif

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/images/fig2_4.gif [1.7.2001 19:01:33]

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/images/fig2_7.gif

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/images/fig2_7.gif [1.7.2001 19:01:41]

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/images/fig2_8.gif

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/images/fig2_8.gif [1.7.2001 19:01:45]

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/images/fig2_9.gif

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/images/fig2_9.gif [1.7.2001 19:02:03]

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/images/fig2_10.gif

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/images/fig2_10.gif [1.7.2001 19:02:10]

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/images/fig2_13.gif

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/images/fig2_13.gif [1.7.2001 19:02:14]

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/images/fig2_15.gif

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/images/fig2_15.gif [1.7.2001 19:02:20]