Example:Inductive definition of the set of trees

From CS2800 wiki
Revision as of 12:04, 20 April 2018 by {{GENDER:Mdg39|[math]'"2}} [/math]'"7
(<math>1) </math>2 | <math>3 (</math>4) | <math>5 (</math>6)

The set [math]T [/math] of binary trees with integer nodes is defined inductively by

  • Rule 1: The empty tree is in [math]T [/math]
  • Rule 2: If [math]t_1 [/math] and [math]t_2 [/math] are trees, then the tree with value [math]a [/math], left child [math]t_1 [/math] and right child [math]t_2 [/math] is in T.


We often think of trees pictorially; in this case we might give a BNF definition of [math]T [/math] as follows:

Tree-defn.svg

However, it is also useful to write trees symbolically; in this case we might define [math]T [/math] as follows:

[math]t \href{/cs2800/wiki/index.php/%E2%88%88}{∈} T \href{/cs2800/wiki/index.php/BNF}{::=} nil \href{/cs2800/wiki/index.php/%5Cmid}{\mid} tree(a,t_1,t_2) \qquad a \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%A4}{ℤ} [/math]

Using the first definition, the following is an example tree:

Tree-example.svg

Using the second definition, we would write this as [math]tree(3,tree(0,nil,nil),tree(1,tree(0,nil,nil),nil)) [/math]