8 Trees

Tree structures enable efficient access and efficient update to large collections of data. Binary trees in particular are widely used and relatively easy to implement. But binary trees are useful for many things besides searching. Just a few examples of applications that trees can speed up include describing mathematical expressions and the syntactic elements of computer programs (using expression trees, see Section 8.3.1), prioritising jobs (using binary heaps, see Section 9.2), or organising the information needed to drive data compression algorithms (using Huffman coding, see Section 9.4).

This chapter covers terminology used for discussing binary trees (Section 8.1), tree traversals (Section 8.4), approaches to implementing tree nodes (Section 8.3), and various examples of binary trees. The chapter concludes by discussing non-binary trees, i.e., trees with more (or less) than two children (Section 8.6).