7.4.3 List-structure Representation

Another way to represent a binary tree is indicated in Figure 7.11. Each node's record is made complex. A complex record's sublist points to the representation of the node's left subtree. The result is that btree is implemented as the list structure lstree. Abstractly, binary trees are a special case of list-structures, but there are list-structures that do not correspond to binary trees. However, in computer science the term tree usually implies zero or restricted sharing of storage, whereas the term list-structure or list implies the possibility of more general sharing of storage.