Tree structure

Q&A's, tips, howto's
Locked
cameyo
Posts: 183
Joined: Sun Mar 27, 2011 3:07 pm
Location: Italy
Contact:

Tree structure

Post by cameyo »

Which is the best way to represent a tree with a list?
Do you know newLISP code that works with trees?
Thanks

cameyo
Posts: 183
Joined: Sun Mar 27, 2011 3:07 pm
Location: Italy
Contact:

Re: Tree structure

Post by 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
Posts: 183
Joined: Sun Mar 27, 2011 3:07 pm
Location: Italy
Contact:

Re: Tree structure

Post by cameyo »

Some basic functions on binary trees.
Maybe these can be useful to other beginners like me...

Code: Select all

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 +) ;


Locked