Binary Trees and Structural Representations

Key Insight

A binary tree is defined as a finite set of nodes that is either empty or consists of a root and the elements of two disjoint binary trees, designated as the 'left' and 'right' subtrees. This recursive definition highlights that a binary tree is not merely a special case of a general tree but a distinct concept. Key differences include that a binary tree can be empty, whereas a general tree cannot, and the explicit distinction between left and right subtrees matters even if one is empty, leading to structures that might be identical as general trees being distinct as binary trees.

Tree structures can be graphically represented in numerous ways beyond traditional branching diagrams. These include 'nested sets,' where containment illustrates hierarchy, 'nested parentheses' akin to algebraic formulas, and 'indentation' resembling an outline or table of contents. Any hierarchical classification scheme inherently forms a tree structure. For instance, an algebraic formula like 'a − (b × ((c/d) + (e/f)))' defines an implicit tree structure where operator precedence dictates node relationships. A 'Dewey decimal notation' can uniquely number nodes in a forest or tree, with children of node α numbered 'α.1, α.2, ...', providing a natural sequential ordering useful for analysis and analogous to book section numbering.

Rectangular arrays can be viewed as a specialized tree or forest structure, though this representation explicitly reflects row relationships but not column relationships. A 'List' is a more general information structure, recursively defined as a finite sequence of zero or more 'atoms' or other 'Lists.' Unlike trees, Lists allow for overlapping sub-Lists and can even be recursive, meaning a List can contain itself, which is not possible in a standard tree definition due to the disjointness requirement for subtrees. The fundamental memory representation for binary trees often involves nodes with two link variables, 'LLINK' and 'RLINK', pointing to their respective subtrees, and a pointer 'T' to the tree's root, with 'T = Λ' signifying an empty tree. This simple representation underlies the significant role of binary trees in computer science, as general trees are frequently converted into equivalent binary tree forms for internal processing.