How to represent binary tree?

Question

The representation of sequences in terms of lists generalizes naturally to represent sequences whose elements may themselves be sequences. For example, we can regard the object ((1 2) 3 4) constructed by (cons (list 1 2) (list 3 4)). The elements of the sequence are the branches of the tree, and elements that are themselves sequences are subtrees.

I don't understand that. I suppose to see ((1 2) (3 4)) and binary tree, but this is ternary tree (not a binary).

The list structure viewed as a tree.

 /\\
/\ 3 4 
1 2

Why it's not the following?

  / \
 /\ /\
1 2 3 4

Answer 1

In languages derived from original Lisp like Scheme you don't have lists or trees as primitive data structures, but only cons cells, that can be used in different ways to represent more complex data structures.

For instance nothing prevents you to represent a sequence of numbers as an improper list, i.e. to rapresent the sequence 1 2 3 4 as:

(cons 1 (cons 2 (cons 3 4)))  ;  => '(1 2 3 . 4)

[*|*]--->[*|*]--->[*|*]--->4
 |        |        |
 v        v        v
 1        2        3

which is more efficient then the usual proper list representation:

(cons 1 (cons 2 (cons 3 (cons 4 '())))) = (list 1 2 3 4)  ;  => '(1 2 3 4)

[*|*]--->[*|*]--->[*|*]--->[*|*]--->()
 |        |        |        |
 v        v        v        v
 1        2        3        4

(consider for instance an application in which you have to manage millions of small lists).

Usually proper lists are used, since the great majority of the primitive functions are defined only for them (for instance you get an error if you try to reverse '(1 2 3 . 4)), and so it is more convenient to use them.

For the trees, on the other hand, the situation is more complex, since you can have different kind of trees, for instance:

1. binary trees in which the information is present only in the leaves (as in your example),

2. binary trees in which the information is present in every node,

3. n-ary trees in which the information in present either in each node or in the leaves,

4. binary or n-ary trees in which the information is a list, or a more complex structure (for instance another tree),

etc.

It's up to you to choose the right representation for the problem at hand. For instance, in the case (2) above, which is much more common that the case (1), you could represent a tree as a list of three elements (the information, the left subtree, the right subtree) (and in this case you can opt either for a proper list or for an improper one), or maybe you could use a structure with three fields, or even an array with three elements.

Summing up, what is important is to define a tree in the way that best fit your need (maybe seeing if there are predefined functions or available libraries that already provide the operators that you need), and then define the basic operators to work on it, like in the answer of Sylwester, operators to build the tree and to use its components, and use always them to write your program. In this way you have all the usual benefits of the Abstract Data Type methodology, for instance you can change the representation of the tree withouth modifying the program.

Answer 2

For a better understanding translate the lists into dotted pairs:

(cons (list 1 2) (list 3 4)) ; ==
((1 2) 3 4) ==
((1 . (2 . '())) . (3 . (4 . '()))) ; ==

     /\
    /  \
   /\   \
  /  \  /\ 
1   /\  3/\
   2  ()4 ()

The tree you are drawing would be:

((1 . 2) . (3 . 4)) ; but the general way of displaying it would be
((1 . 2) 3 . 4)

I assume then that a pair is a node whose car is right and cdr is left side. Basically:

(define make-tree cons)
(define tree-right car)
(define tree-left cdr)
(define tree? pair?)
(define *tree-null* '())

Now you could model trees like this instead:

(define make-tree list)
(define tree-right car)
(define tree-left cadr)
(define tree? list?)
(define *tree-null* '())

Then the same tree would look like this:

((1 2) (3 4))

It really doesn't matter, but the first example is the common way since it uses less space. In any way these would work the same:

(define (accumulate-tree tree term combiner null-value)
  (let rec ((tree tree))
    (cond ((eq? *tree-null* tree) null-value)
          ((not (tree? tree)) (term tree))
          (else (combiner (rec (tree-left tree)) 
                          (rec (tree-right tree)))))))

(define (copy-tree tree)
  (accumulate-tree tree values make-tree *tree-null*))

(define (aritmetric-sum-tree tree)
  (accumulate-tree tree values + 0))

(define (reverse-tree tree)
  (accumulate-tree tree 
                   values
                   (lambda (left right) (make-tree right left))
                   *tree-null*))

EDIT

SICP only only offers a different way to look at the same structure, which is not a binary tree. There a node is a list of children and a child which is a list is a new node. It's far more important that you understand the boxes and that chained cons have an odd way of being displayed. Notice how the boxes are similar to my tree.

It's important to understand that with cons you can model any abstract data structure and when creating your own data structures you are in change of how to map the elements to cons. Thus the same list structure might represent something else depending on how you use them. E.g. If you have a LZW tree where you iterate the tree in a lookup you usually only need a parent. thus. a pair might be of parent and this nodes value.