Chapter 8
Trees
Contents
8.1.1 Tree Definitions and Properties
8.1.2 The Tree Abstract Data Type
8.1.3 Computing Depth and Height
8.2.1 The Binary Tree Abstract Data Type
8.2.2 Properties of Binary Trees
8.3.1 Linked Structure for Binary Trees
8.3.2 Array-Based Representation of a Binary Tree
8.3.3 Linked Structure for General Trees
8.4.1 Preorder and Postorder Traversals of General Trees
8.4.2 Breadth-First Tree Traversal
8.4.3 Inorder Traversal of a Binary Tree
8.4.4 Implementing Tree Traversals in Python
8.4.5 Applications of Tree Traversals
8.4.6 Euler Tours and the Template Method Pattern 
8.1 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 array-based lists or linked lists. Trees also provide a natural organization for data, and consequently have become ubiquitous structures in file systems, graphical user interfaces, databases, ...
Get Data Structures and Algorithms in Python now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
