Computer Science & Perl Programming

Chapter 22. Trees and Game Trees

Sean M. Burke

Perl’s facility with references, combined with its automatic management of memory allocation, makes it straightforward to write programs that store data in structures of arbitrary form and complexity.

But I’ve noticed that many programmers, especially those who started out with more restrictive languages, seem at home with complex but uniform data structures—multidimensional arrays, or more struct-like things like hashes-of-arrays (-of-hashes[-of-hashes]), and so on—but they’re often uneasy buliding more freeform, less tabular structures, like trees.

Trees are easy to build and manage in Perl, as I’ll demonstrate by showing how the HTML::Element class manages elements in an HTML document tree, and by walking you through a from-scratch implementation of game trees. First, I need to nail down what I mean by a “tree.”

What Is a Tree?

My first brush with tree-shaped structures was in linguistics classes, where tree diagrams were used to describe the syntax underlying natural language sentences. After learning my way around those trees, I started to wonder—are what I’m used to calling “trees” the same as what programmers call “trees?” I asked lots of helpful and patient programmers how they would define a tree. Many replied with a answer in jargon that they could not really explain (understandable, since explaining things, especially defining things, is harder than people think):

Q: So what is a “tree?” A tree-shaped data structure?

A: A tree is ...