Data Structures and Algorithms in C++, Second Edition

Chapter 7. Trees

Contents

7.1 General Trees	268
7.1.1 Tree Definitions and Properties	269
7.1.2 Tree Functions	272
7.1.3 A C++ Tree Interface	273
7.1.4 A Linked Structure for General Trees	274
7.2 Tree Traversal Algorithms	275
7.2.1 Depth and Height	275
7.2.2 Preorder Traversal	278
7.2.3 Postorder Traversal	281
7.3 Binary Trees	284
7.3.1 The Binary Tree ADT	285
7.3.2 A C++ Binary Tree Interface	286
7.3.3 Properties of Binary Trees	287
7.3.4 A Linked Structure for Binary Trees	289
7.3.5 A Vector-Based Structure for Binary Trees	295
7.3.6 Traversals of a Binary Tree	297
7.3.7 The Template Function Pattern	303
7.3.8 Representing General Trees with Binary Trees	309
7.4 Exercises	310

General Trees

Productivity experts say that breakthroughs come by thinking "nonlinearly." In this chapter, we discuss one of the most important nonlinear data structures in computing—trees. Tree structures are indeed a breakthrough in data organization, for they allow us to implement a host of algorithms much faster than when using linear data structures, such as lists, vectors, and sequences. Trees also provide a natural organization for data, and consequently have become ubiquitous structures in file systems, graphical user interfaces, databases, Web sites, and other computer systems.

It is not always clear what productivity experts mean by "nonlinear" thinking, but when we say that trees are "nonlinear," we are referring to an organizational relationship ...