A
binary tree is an
ordered tree data structure in which each node has at most two
children. Typically the child nodes are called
left and
right. One use of binary trees is as
binary search trees.
There is a one-to-one mapping between general ordered trees and binary trees which Lisp uses to represent general ordered trees as binary trees. Each node N in the ordered tree corresponds to a node N' in the binary tree; the left child of N' is the node corresponding to the first child of N, and the right child of N' is the node corresponding to the N's next sibling --- that is, the next node among N's parent's children.
One way of thinking about this is that each node's children are in a linked list, chained together with their right fields, and the node only has a pointer to the beginning of this list.