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 nary trees as binary trees in Lisp
There is a onetoone 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 LThe 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:
See also: AVL tree, Btree, binary space partition, RedBlack tree
Search Encyclopedia

Featured Article
