Created
November 9, 2013 00:35
-
-
Save ranacseruet/7379890 to your computer and use it in GitHub Desktop.
Binary Tree Traversal In LISP(Preorder,Inorder & PostOrder)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
(defparameter *tree2* '(40 (30 (25 () ()) (35 () ())) (60 (50 () ()) ()))) | |
(defparameter *tree* '(3 (2 (1 () ()) ()) (5 () ()))) | |
;validate if given parameter is a binary tree or not | |
(defun is-tree(tree) | |
(cond | |
((null tree) NIL) | |
((< (list-length tree) 3) NIL) | |
(t) | |
) | |
) | |
;return left subtree of a binary tree | |
(defun left-subtree(tree) | |
(cond | |
((null tree) NIL) | |
((not (listp tree)) NIL) | |
(t (car (cdr tree))) | |
) | |
) | |
(defun right-subtree(tree) | |
(cond | |
((null tree) NIL) | |
((not (listp tree)) NIL) | |
(t (car (cdr (cdr tree)))) | |
) | |
) | |
;perform preorder traverse | |
(defun preorder(tree) | |
(if | |
(not (is-tree tree)) NIL | |
(cons (car tree) | |
(append (preorder (left-subtree tree)) | |
(preorder (right-subtree tree)) | |
) | |
) | |
) | |
) | |
;perform inorder traverse | |
(defun inorder(tree) | |
(if | |
(not (is-tree tree)) NIL | |
(append | |
(inorder (left-subtree tree)) | |
(list (car tree)) | |
(inorder (right-subtree tree)) | |
) | |
) | |
) | |
;perform postorder traverse | |
(defun postorder(tree) | |
(if | |
(not (is-tree tree)) NIL | |
(append | |
(postorder (left-subtree tree)) | |
(postorder (right-subtree tree)) | |
(list (car tree)) | |
) | |
) | |
) | |
;example execution | |
(print (postorder *tree2*)) | |
(print (preorder *tree2*)) | |
(print (inorder *tree2*)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
how do you return values from the level on the list?