O'Reilly logo

Data Structures and Algorithms in C++, Second Edition by David M. Mount, Roberto Tamassia, Michael T. Goodrich

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Chapter 7. Trees

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required