Let's discuss some general properties of little-t trees.
We've seen that structures like
(cons (list 1 2) (list 3 4))
can be represented in a tree-like structure:
Little-t trees are composed of branches and leaves.
The tree above has five
branches; they correspond to the lines on the diagram above. Notice that a
branch can lead to a subtree—a tree that is contained within a larger tree.
In this case, the branch
((1 2) 3 4) contains the subtree
A leaf has no branches connecting from it. The tree above has 4 leaves:
Leaves are found at the "bottom" of the tree, also called the fringe.
Compared to trees in the real world, trees in computer science tend to be upside-down!
When working with trees, it is usually helpful to think recursively.
As an example, let's write a function
count-leaves that counts the number of leaves in a tree.
We'll start by informally outlining what our function will do in plain English.
This is called writing pseudocode. After we understand how our
should behave, we'll write the actual Racket code for it. This is good general technique for
Recall how we defined
length, which finds the number of elements in a list:
lengthof an empty list is 0.
lengthof a non-empty list
xis 1 plus the
The base case is the same for
count-leavesof an empty list is 0.
Our recusive case is slightly different though.
length, we are guaranteed that the
car of the list is a single element, so we count its length as 1.
car may contain one or more trees, and so its length will not always be 1.
Therefore, we need to recursively find the
count-leaves of the
car of the tree as well! Our recursive call is therefore:
count-leavesof a tree is the
carof the tree plus
cdrof the tree.
Eventually we will
car ourselves to the leaf of the tree, and so our second base case will be:
count-leavesof a leaf is
When we call
car on a tree, we have to determine if it returns another tree (a pair), or a leaf (a single element, technically known as an atom).
How do we check for it? Racket has a built-in predicate
pair? that tests if its argument is the result of a
cons. For example:
(pair? (cons 1 2))returns
(pair? (cons 1 (cons 2 3)))returns
pair? and the pseudocode above,
we can write the complete code for
(define (count-leaves x) (cond ((null? x) 0) ;; is the tree is empty? ((not (pair? x)) 1) ;;is the tree a single element? (else (+ (count-leaves (car x)) ;; else, call count-leaves on the car (count-leaves (cdr x))))) ;; and cdr of x and add them up.
In Lesson 4, we saw the function
scale-list, which multiplies each
item in a list by a given numeric factor. We are going to write an analogous
scale-tree, which accepts a deep list and a numeric factor and multiplies all elements in the deep list by that factor.
Here is an example call:
> (scale-tree (list 1 (list 2 (list 3 4) 5) (list 6 7)) 10) (10 (20 (30 40) 50) (60 70))
Test Your Understanding
Below is an unfinished definition of scale-tree. Which base case(s) do we need to correctly define
(define (scale-tree tree factor) (cond ;;Your answer here. (else (cons (scale-tree (car tree) factor) (scale-tree (cdr tree) factor)))))
scale-tree out in your interpreter with some examples of your own!
Let's work on a problem with a similar structure.
This time, we want to write a function called
deep-reverse that reverses the order of all elements in a deep list.
> (define x (list (list 1 2) (list 3 4))) ((1 2) (3 4)) > (deep-reverse x) ((4 3) (2 1))
Notice that not only do
(1 2) and
(3 4) switch places, but their elements do as well.
deep-reverse should also work for lists that do not contain other lists inside of it.
deep-reverse. Which recursive call(s) do we need in order to correctly define
(define (deep-reverse d-l) (cond ((null? d-l) null) ;;Your answer here. ))
Try this out in your Racket interpreter!
Trees can contain subtrees, so recursion can be very helpful when solving problems involving trees.