fig ternary tree extended with special nodes of particular importance are the ordered trees of degree they are called binary trees we define an ordered binary tree as finite set of elements (nodeswhich either is empty or consists of root (nodewith two disjoint binary trees called the left and the right subtree of the root in the following sections we shall exclusively deal with binary treesand we therefore shall use the word tree to mean ordered binary tree trees with degree greater than are called multiway trees and are discussed in sect familiar examples of binary trees are the family tree (pedigreewith person' father and mother as descendants (!)the history of tennis tournament with each game being node denoted by its winner and the two previous games of the combatants as its descendantsor an arithmetic expression with dyadic operatorswith each operator denoting branch node with its operands as subtrees (see fig fig tree representation of expression ( / ( *fwe now turn to the problem of representation of trees it is plain that the illustration of such recursive structures in terms of branching structures immediately suggests the use of our pointer facility there is evidently no use in declaring variables with fixed tree structureinsteadwe define the nodes as variables with fixed structurei of fixed typein which the degree of the tree determines the number of pointer components referring to the node' subtrees evidentlythe reference to the empty tree is denoted by nil hencethe tree of fig consists of components of type defined as follows and may then be constructed as shown in fig type node pointer to nodedesctype nodedesc record opcharleftrightnode end