Page 223 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes 7. Write a method and the corresponding recursive function to traverse a binary tree (in
whatever order you find convenient) and dispose of all its nodes. Use this method to

implement a Binary_tree destructor.
8. Consider a heap of n keys, with xk being the key in position k (in the contiguous
representation) for 0 ≤ k < n. Prove that the height of the subtree rooted at xk is the greatest
integer not exceeding lg(n/(k+ 1)), for all k satisfying 0 ≤ k < n.
9. “A heap can be used as a priority queue: the highest priority item is at the root and is
trivially extracted.” Discuss.
10. “The enqueue method of the BinaryHeap class takes as its argument the item to be inserted
in the heap.” Explain.

Answers: Self Assessment

1. binary tree 2. closely related 3. smallest key
4. dequeueMin 5. simulation 6. position 0
7. priority queue 8. Array subscript

10.9 Further Readings

Books Brian W. Kernighan and Dennis M. Ritchie, The C Programming Language, Prentice
Hall, 1988.
Burkhard Monien, Data Structures and Effi cient Algorithms, Thomas Ottmann,
Springer.
Kruse, Data Structure & Program Design, Prentice Hall of India, New Delhi.
Mark Allen Weles, Data Structure & Algorithm Analysis in C, Second Ed., Addison-
Wesley Publishing.
RG Dromey, How to Solve it by Computer, Cambridge University Press.
Shi-Kuo Chang, Data Structures and Algorithms, World Scientifi c.
Shi-kuo Chang, Data Structures and Algorithms, World Scientifi c.

Sorenson and Tremblay, An Introduction to Data Structure with Algorithms.
Thomas H. Cormen, Charles E, Leiserson & Ronald L., Rivest: Introduction to
Algorithms. Prentice-Hall of India Pvt. Limited, New Delhi.

Timothy A. Budd, Classic Data Structures in C++, Addison Wesley.

Online links www.en.wikipedia.org
www.web-source.net
www.webopedia.com

218 LOVELY PROFESSIONAL UNIVERSITY