Swipe to navigate through the chapters of this book
This chapter introduces a kind of structure that turns up everywhere in computer science: trees. We will be learning to speak their language – how to talk about their components, varieties and uses – more than proving things about them. The flavour of the chapter is thus rather different from that of the preceding one on probability: more use of spatial intuition, rather less in the way of demonstration.
We begin by looking at trees in their most intuitive form – rooted (alias directed) trees – first of all quite naked and then clothed with labels and finally ordered. Special attention will be given to the case of binary trees and their use in search procedures. Finally, we turn to unrooted (or undirected) trees and their application to span graphs. As always, we remain in the finite case.
Please log in to get access to this content
Almost all introductory texts of discrete mathematics have a chapter on trees, usually preceded by one on the more general theory of graphs. More often than not, they treat unrooted trees before rooted ones. Of the two books below, both go into considerably more detail than we have done. The first starts from unrooted trees, while the approach of the second is closer to that of this chapter.
Johnsonbaugh R (2009) Discrete mathematics, 7th edn. Pearson, chapter 9
Kolman B et al (2006) Discrete mathematical structures, 6th edn. Pearson, chapter 7
- Squirrel Math: Trees
- Springer London
- Sequence number
- Chapter number