Core Web Programming, Second Edition

8.11. Example: A Simple Binary Tree

This section shows how references and the Vector class can be used to create a binary tree class. This data structure includes a depthFirstSearch method, which traverses the tree in depth-first order (staying to the left and going as deep as possible until having to backtrack). Notice that this method is recursive; recursion is natural for depth-first search. The depthFirstSearch method also uses the NodeOperator interface (see Listing 8.21) to generalize the operation that will be performed on each node. This interface lets you change what to do with a tree without modifying the Node class, which is shown in Listing 8.20. Leaf nodes are implemented as a subclass of Node, see Listing 8.22. The data structure ...