Summary

In this chapter, we have looked at tree structures and some example uses of them. We studied binary trees in particular, which is a subtype of trees where each node has at most two children.

We looked at how a binary tree can be used as a searchable data structure with a BST. We saw that, in most cases, finding data in a BST is faster than in a linked list, although this is not the case if the data is inserted sequentially, unless of course the tree is balanced.

The breadth- and depth-first search traversal modes were also implemented using queue recursion.

We also looked at how a binary tree can be used to represent an arithmetic or a Boolean expression. We built up an expression tree to represent an arithmetic expression. We showed how to use a stack to parse an expression written in RPN, build up the expression tree, and finally traverse it to get the result of the arithmetic expression.

Finally, we mentioned heaps, a specialization of a tree structure. We have tried to at least lay...