Chapter 7 Recursive Data Types176
Problem 7.5.
Definition.The recursive data type, binary-2PTG, ofbinary treeswith leaf labels,
L, is defined recursively as follows:
Base case:hleaf;li 2 binary-2PTG, for all labelsl 2 L. Constructor case:IfG 1 ;G 22 binary-2PTG, thenhbintree;G 1 ;G 2 i 2 binary-2PTG:Thesize,jGj, ofG 2 binary-2PTG is defined recursively on this definition by: Base case:
jhleaf;lijWWD1; for alll 2 L: Constructor case:jhbintree;G 1 ;G 2 ijWWDjG 1 jCjG 2 jC1:For example, for the size of the binary-2PTG,G, pictured in Figure 7.1, is 7.G
G 11
winG1,2
winlose winFigure 7.1 A picture of a binary treew.