Which is the best way to represent a tree with a list?
Do you know newLISP code that works with trees?
Thanks
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 :-)
Some basic functions on binary trees.
Maybe these can be useful to other beginners like me...
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 +) ;