Chapter 9. Trees
A tree is a hierarchical form of data structure. When we dealt with lists, queues, and stacks, items followed each other. But in a tree, there is a parent-child relationship between items.
To visualize what trees look like, imagine a tree growing up from the ground. Now remove that image from your mind. Trees are normally drawn downward, so you would be better off imagining the root structure of the tree growing downward.
At the top of every tree is the so-called root node. This is the ancestor of all other nodes in the tree.
Trees are used for a number of things, such as parsing expressions, and searches. Certain document types, such as XML and HTML, can also be represented in a tree form. We shall look at some of the uses of trees in this chapter.
In this chapter, we will cover the following areas:
- Terms and definitions of trees
- Binary trees and binary search trees
- Tree traversal
