Tree structure

[cameyo]

Which is the best way to represent a tree with a list?

Do you know newLISP code that works with trees?

Thanks

[cameyo]

To start:

"Simply Scheme" Harvey-Wright (Chapter 18)

"SICP" Abelman-Sussman (2.2.2 Hierarchical Structures)

...

binary trees, binary search trees, AVL trees, 2-3-4 trees, red-black trees... it is a long road :-)

[cameyo]

Some basic functions on binary trees.

Maybe these can be useful to other beginners like me...

Code Select Expand

List structure of a tree --> (V L R)
where V = tree Value
      L = Left sub-tree
      R = Right sub-tree

leaf --> (V nul nul)

Example:
         A
        /
       /  
      B     C
     /     /
    /     /  
   D     E     F

(setq my-tree '(A (B (D nul nul)) (C (E nul nul) (F nul nul)))
root: A
nodes: B C
leaves: D E F

Functions:

(define (bst-create-empty) '())

(define (bst-create value left-subtree right-subtree)
  (list value left-subtree right-subtree))

(define (bst-isempty? BST) (null? BST))

(define (bst-value BST) (first BST))

(define (bst-left-subtree BST) (first (rest BST)))

(define (bst-right-subtree BST) (first (rest (rest BST))))

(define (bst-istree? LST)
  (or (null? LST)
      (and (list? LST)
           (= (length LST) 3)
           (bst-istree? (bst-left-subtree LST))
           (bst-istree? (bst-right-subtree LST)))))

(define (bst-count-nodes BST)
  (if (null? BST)
      0
      (+ 1 (bst-count-nodes (bst-left-subtree BST))
           (bst-count-nodes (bst-right-subtree BST)))))

(define (bst-count-leaves BST)
  (if (null? BST)
      0
      (if (and (null? (bst-left-subtree BST)) (null? (bst-right-subtree BST)))
          (+ 1 (bst-count-leaves (bst-left-subtree BST))
               (bst-count-leaves (bst-right-subtree BST)))
          (+   (bst-count-leaves (bst-left-subtree BST))
               (bst-count-leaves (bst-right-subtree BST))))))

(define (bst-isleaf? BST)
    (and (bst-isempty? (bst-left-subtree BST))
         (bst-isempty? (bst-right-subtree BST))))


(define (bst-traverse-inorder BST)
    (cond
      ((bst-isempty? BST) '())
      (true (append
              (bst-traverse-inorder (bst-left-subtree BST))
              (list (bst-value BST))
              (bst-traverse-inorder (bst-right-subtree BST))))))

(define (bst-traverse-preorder BST)
    (cond
      ((bst-isempty? BST) '())
      (true (append
              (list (bst-value BST))
              (bst-traverse-preorder (bst-left-subtree BST))
              (bst-traverse-preorder (bst-right-subtree BST))))))

(define (bst-traverse-postorder BST)
    (cond
      ((bst-isempty? BST) '())
      (true (append
              (bst-traverse-postorder (bst-left-subtree BST))
              (bst-traverse-postorder (bst-right-subtree BST))
              (list (bst-value BST))))))

Example:
              A
             /
            /  
           /    
          B       C
         /      /
        /      /  
       D     E ()    F
                    /
                   /  
                  G    ()

(setq tree '(A (B (D () ()) (E () ())) (C () (F (G () ()) ()))))
(bst-istree? tree)
;-> true
(bst-count-nodes tree)
;-> 7
(bst-count-leaves tree)
;-> 3
(bst-traverse-inorder tree)
;-> (D B E A C G F)
(bst-traverse-preorder tree)
;-> (A B D E C F G)
(bst-traverse-postorder tree)
;-> (D E B G F C A)

Example:
            +
           /
          *   E
         /
        *   D
       /
      ^   C
     /
    A   B

(setq arit '(+ (* (* (^ (A () ()) (B () ())) (C () ())) (D () ())) (E () ())))
(bst-istree? arit)
;-> true
(bst-count-nodes arit)
;-> 9
(bst-count-leaves arit)
;-> 5
infix
(bst-traverse-inorder arit)
;-> (A ^ B * C * D + E)
prefix
(bst-traverse-preorder arit)
;-> (+ * * ^ A B C D E) ;
postfix
(bst-traverse-postorder arit)
;-> (A B ^ C * D * E +) ;