Representing tree as a list

Question

I should write a function which calculates amount of leaves in the given tree. Before writing algorithm, I want to be sure about my representation.

For this tree, my representation is:

(define liste 
    (list '5 (list '1 (list '8) (list '2 (list '1) (list '9))) (list '10) 
    (list '4 (list '9))))

Is that correct?

My other question is that do I need any parameter except list for this function?

Btw, I know that I don't need to write list every time but this looks more clear for me.

Edit:

(define (howmany L)
    (if (empty? L) 
        0
        (if (= (length L) 1)
            (+ 1 (howmany (cdr L)))
            (if (= (length (car (cdr L))) 1)
                (+ 1 (howmany (cdr L)))
                (howmany (cdr L))))))

When I call (howmany (list-ref liste 1)), it returns 2. However, it should return 3. (8, 1, 9)

When I call (howmany (list-ref liste 2)), it retursn 1. Fine.

When I call (howmany (list-ref liste 3)), it returns 2. It should return 1. (Only 9)

What's my mistake?

Answer 1

Indenting the expression to mimick the graphical representation of the tree reveals that your expression is correct:

(define liste 
  (list 5 
        (list 1 
              (list 8) 
              (list 2 
                    (list 1) 
                    (list 9)))
        (list 10) 
        (list 4 
              (list 9))))

A shorter way to a structural equivalent value is:

      '(5
        (1
         (8)
         (2
          (1)
          (9)))
        (10)
        (4
         (9)))

Your sum-of-leaves function does not need more parameters, but if you want to use an accumulator, you can write:

(define (sum tree)
  (sum-it tree 0))

(define (sum-it tree sum-so-far)
   ...)

Answer 2

To count up your leaves.

(define (node-count-of-leaves node)
  (let ((count 0))
    (node-walk (lambda (node)
                 (when (node-is-leaf? node)
                   (set! count (+ 1 count)))
               node)
    count))

As regards your how many function, you are not recursing down the tree correctly and perhaps adding 1 on non-leaves.

For the above code, abstraction is your friend:

(define (make-node value . children)
  `(,value ,@children))

(define node-value car)
(define node-children cdr)

(define (make-leaf-node value)
   (make-node value))
(define (node-is-leaf? node)
  (null? (node-children node)))

(define (node-degree node)
  (length (node-children node)))

Now you get to use descriptively-named functions, like node-children, rather then, in your representation, combinations of car, cdr, cadr, etc.

With the above, go ahead and build a tree.

(define my-tree
  (make-node 5
    (make-node 1 ...)
    (make-leaf-node 10)
    (make-node 4 ...)))

and then you can walk the tree:

(define (node-walk func node)
  (func node)
  (for-each (lambda (node) (node-walk func node))
            (node-children node))))

Answer 3

Here's my implementation of the count-leaves function:

(define (count-leaves tree)
  (if (null? (cdr tree))
      1
      (let loop ((count 0)
                 (children (cdr tree)))
        (if (null? children)
            count
            (loop (+ count (count-leaves (car children)))
                  (cdr children))))))

Or, if you're allowed to use map in your assignment, it can be much shorter:

(define (count-leaves tree)
  (if (null? (cdr tree))
      1
      (apply + (map count-leaves (cdr tree)))))

Tests (tested under Racket):

> (count-leaves tree)
5
> (count-leaves (second tree))
3
> (count-leaves (third tree))
1
> (count-leaves (fourth tree))
1