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 Java
8.1 General Trees
Productivity experts say that breakthroughs come by thinking “nonlinearly.” In this chapter, we will 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 arrays or linked lists. Trees also provide a natural organization for data, and consequently have become ubiquitous structures in file systems, graphical user interfaces, databases, websites, and many 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 ...
Get Data Structures and Algorithms in Java, 6th Edition 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.
