Trees

Table of contents:

All of the data structures we have seen so far, such as arrays and linked lists, are linear. In a linear structure, there is a first item and a last item. Every item (except the last) has a successor and every item (except the first) has a predecessor.

This chapter introduces trees, which are more general structures for representing branching or hierarchical data. For example, biological classification diagrams, many organizational charts in businesses, and sports playoff brackets are trees. We have seen a few trees already in this book, including class inheritance diagrams like Figure 3-10 and recursion trees like Figure 9-16.

We begin with a discussion of the simplest kind of trees, binary trees. Using the game of Questions as a running example, Section 10.1 introduces tree terminology and discusses the implementation of binary trees. The issue of traversing trees is addressed in Section 10.2. More general trees are covered in Section 10.3, where we use trees to design an intelligent Tic Tac Toe player.


Binary Trees

Part I: Object-Oriented Programming

Encapsulation

Polymorphism

Inheritance

Part II: Linear Structures

Stacks and Queues

Array-Based Structures

Linked Structures

Part III: Algorithms

Analysis of Algorithms

Searching and Sorting

Recursion

Part IV: Trees and Sets

Trees

Sets

Part V: Advanced Topics

Advanced Linear Structures

Strings

Advanced Trees

Graphs

Memory Management

Out to the Disk

Part VI: Appendices

A. Review of Java

B. Unified Modeling Language

C. Summation Formulae

D. Further Reading

Index



Data Structures and Algorithms in Java
Data Structures and Algorithms in Java
ISBN: 0131469142
EAN: 2147483647
Year: 2004
Pages: 216
Authors: Peter Drake

Similar book on Amazon

Flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net