Perl Cookbook

Program: Binary Trees

Because Perl’s built-in data types are already powerful, high-level, dynamic data types in their own right, most code can use what’s already provided. If you just want quick lookups, you nearly always want to use a simple hash. As Larry has said, “The trick is to use Perl’s strengths rather than its weaknesses.”

However, hashes provide no inherent ordering. To traverse the hash in a particular order, you must first extract its keys and then sort them. If you find yourself doing so many times, performance will suffer, but probably not enough to justify the time required to craft a fancy algorithm.

A tree structure provides ordered traversals. How do you write a tree in Perl? First, you grab one of your favorite textbooks on data structures; the authors recommend Cormen et al., as mentioned in Section -1.3 in the the preface. Using an anonymous hash to represent each node in the tree, translate the algorithms in the book into Perl. This is usually much more straightforward than you would imagine.

The program code in Example 11.1 demonstrates a simple binary tree implementation using anonymous hashes. Each node has three fields: a left child, a right child, and a value. The crucial property of an ordered binary tree is that all its left children have values less than the current node’s value, and all right children have values greater than the current node’s value.

The main program does three things. First, it creates a tree with 20 random nodes. Then it shows ...