X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=implementing_trees.mdwn;h=c428228f2bd56867ebf0d12e35fa61e652911e97;hp=31dc3fd01cadcf915d08d22352f554dbb4cf22b9;hb=67ed83b1ad44c7590cf7d7c1ec3a079bc5140a61;hpb=a4c3bd5c0bcebbd8f550ec6f6033f16f98cd2a8e diff --git a/implementing_trees.mdwn b/implementing_trees.mdwn index 31dc3fd0..c428228f 100644 --- a/implementing_trees.mdwn +++ b/implementing_trees.mdwn @@ -1,6 +1,9 @@ #Implementing trees# -In [[Assignment3]] we proposed a very ad-hoc-ish implementation of trees. +In [[Assignment3]] we proposed a very ad-hoc-ish implementation of +trees. It had the virtue of constructing trees entirely out of lists, +which meant that there was no need to define any special +tree-construction functions. Think about how you'd implement them in a more principled way. You could use any of the version 1 -- version 5 implementation of lists as a model. @@ -17,10 +20,10 @@ the tree's leaves that are labeled: / \ 1 2 -Linguists often use trees of this sort. The inner, non-leaf nodes of the -tree do have associated values. But what values they are can be determined from -the structure of the tree and the values of the node's left and right children. -So the inner node doesn't need its own independent label. +The inner, non-leaf nodes of the tree may have associated values. But if so, +what values they are will be determinable from the structure of the tree and the +values of the node's left and right children. So the inner nodes don't need +their own independent labels. In another sort of tree, the tree's inner nodes are also labeled: @@ -128,9 +131,9 @@ where the previous tree should be placed. However, when using trees as a computational tool, one usually does have latitude about how to structure a larger tree---in the same way that we had the -freedom to implement our sets with lists whose members were just appended in -the order we built the set up, or instead with lists whose members were ordered -numerically. +freedom to implement our [sets](/week4/#index9h1) with lists whose members were +just appended in the order we built the set up, or instead with lists whose +members were ordered numerically. When building a new tree, one strategy for where to put the new element and where to put the existing tree would be to always lean towards a certain side.