Binary tree

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.

Graph theorists use the following definition. A binary tree is a connected acyclic graph such that the degree of each vertex is no more than 3. A rooted binary tree is such a graph that has one of its vertices of degree no more than 2 singled out as the root. With the root thus chosen, each vertex will have a uniquely defined parent, and up to two children; however, so far there is insufficient information to distinguish a left or right child. If we drop the connectedness requirement, and there are multiple connected component in the graph, we call such a structure a forest.

The obvious way of implementing binary trees in programming languages typically gives a rooted binary tree where the children of each node are ordered.

Encoding n-ary trees as binary trees in Lisp

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.

For example, in the tree on the left, A has the 6 children {B,C,D,E,F,G}. It can be converted into the binary tree on the right.

          __ A ______               A
         /  /|\   \  \             /
        /  / | \   \  \           B
       B  C  D  E   F  G         / \
      /|\      / \     |        G   C
     / | \    /   \    |       / \   \
    G  H  I  J     K   L      M   H   D
   / \       |     |           \   \   \
  M   N      O     P            N   I   E
                                       / \
                                      J   F
                                     / \   \
                                    O   K   G
                                       /   /
                                      P   L

The binary tree is just the general tree tilted sideways, with the arcs representing first child and next sibling. The leaves of the tree on the left would be written in Lisp as:

(((M N) H I) C D ((O) (P)) F (L))

which would be implemented in memory as the binary tree on the right, without any letters on those nodes that have a left child.

See also: AVL tree, B-tree, binary space partition, Red-Black tree