## Tree structure

Q&A's, tips, howto's
cameyo
Posts: 101
Joined: Sun Mar 27, 2011 3:07 pm

### Tree structure

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

cameyo
Posts: 101
Joined: Sun Mar 27, 2011 3:07 pm

### Re: Tree structure

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: 101
Joined: Sun Mar 27, 2011 3:07 pm

### Re: Tree structure

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

``````