So far we have considered only binary trees, but trees may have nodes with more than two successors. This is the case in the tree of Figure 7.1, where the nodes have up to three successors. It would be natural to assume that binary trees are a special case of trees, but the tree literature does not treat them this way. The formal definition of a tree, as opposed to a binary tree, is as follows: A tree is a root node with subtrees t1, t2, . . . , tn that are themselves trees and have no nodes in common.
Formally there are no null trees (although there are null binary trees), so each tree has at least one node, its root. It is convenient nonetheless to refer to null trees, so the terminology applied to binary trees also applies to trees. The important distinction is that no order is imposed on the subtrees of a tree, whereas for binary trees there is a distinct left and right subtree. Consequently, when trees are depicted, it makes no difference in what order subtrees are drawn; any order represents the same tree. When order among the subtrees is to be imposed, they are called ordered trees. For example the structures in Figure 7.12, when viewed as binary trees, represent two distinct binary trees, since their left and right subtrees differ, but they represent the same tree when viewed as trees.
7.5.1 Implementing Trees as Binary Trees