Alternate Representations for Trees

Data Structures and Algorithms with Object-Oriented Design Patterns in C++

Alternate Representations for Trees

Figure shows an alternate representation of the tree defined in Equation . In this case, the tree is represented as a set of nested regions in the plane. In fact, what we have is a Venn diagram which corresponds to the view that a tree is a set of sets.

Figure: An Alternate Graphical Representation for Trees

This hierarchical, set-within-a-set view of trees is also evoked by considering the nested structure of computer programs. E.g., consider the following fragment of C++ code:

D: {
    E: {
        F: statement();
    }
    G: {
        H: {
            I: statement();
	}
        J: {
            K: statement();
            L: statement();
	}
        M: statement();
    }
}

The nesting structure of this program and the tree given in Equation

are isomorphic .

Therefore, it is not surprising that trees have an important rôle in the analysis and translation of computer programs.