# lisp-random / miscellaneous_exercises / binary-tree-traversal.lisp

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147``` ```;;;; binary-tree-traversal.lisp ;;;; Copyright (c) 2012 Robert Smith ;;;; This file has the solution to basic computer science exercises on ;;;; tree traversal. It includes the tree representation, ;;;; construction, pre/in/post-order (depth-first) traversal, and ;;;; level-order (breadth-first) traversal. (defstruct node value left right) (defun build-tree (list) (cond ((null list) nil) ((atom list) (make-node :value list)) ((listp list) (destructuring-bind (v l r) list (make-node :value v :left (build-tree l) :right (build-tree r)))))) ;;;;;;;;;;;;;;;;;;;;;;;;;;;; Depth First ;;;;;;;;;;;;;;;;;;;;;;;;;;;;; (defun pre-order (f tree) (let ((value (node-value tree)) (left (node-left tree)) (right (node-right tree))) ;; 1. Root (funcall f value) ;; 2. Left (when left (pre-order f left)) ;; 3. Right (when right (pre-order f right))) ;; Return NIL. nil) (defun in-order (f tree) (let ((value (node-value tree)) (left (node-left tree)) (right (node-right tree))) ;; 1. Left (when left (in-order f left)) ;; 2. Root (funcall f value) ;; 3. Right (when right (in-order f right))) ;; Return NIL. nil) (defun post-order (f tree) (let ((value (node-value tree)) (left (node-left tree)) (right (node-right tree))) ;; 1. Left (when left (post-order f left)) ;; 2. Right (when right (post-order f right)) ;; 3. Root (funcall f value)) ;; Return NIL. nil) ;;;;;;;;;;;;;;;;;;;;;;;;;;; Breadth First ;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;; N.B. This is not an efficient queue implementation. DEQUEUE takes ;;; O(N) time. Implementing a heap would be a better idea. (defstruct queue elements) (defun enqueue (queue item) (setf (queue-elements queue) (push item (queue-elements queue)))) (defun dequeue (queue) (let ((elts (queue-elements queue))) (prog1 (if (null elts) nil (first (last elts))) (setf (queue-elements queue) (butlast elts))))) (defun level-order (f tree) (loop :with queue := (make-queue :elements (list tree)) :until (null (queue-elements queue)) :do (let* ((next (dequeue queue)) (left (node-left next)) (right (node-right next))) ;; Perform operation on current node. (funcall f (node-value next)) ;; Queue up new nodes at the next level. (when left (enqueue queue left)) (when right (enqueue queue right))) :finally (return nil))) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; Tests ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; (defparameter *test-tree* (build-tree `(f (b (a nil nil) (d (c nil nil) (e nil nil))) (g nil (i (h nil nil) nil))))) (defparameter *test-tree-2* (build-tree `(f (b a (d c e)) (g nil (i h nil))))) ;;; CL-USER> (pre-order #'princ *test-tree*) ;;; FBADCEGIH ;;; NIL ;;; CL-USER> (in-order #'princ *test-tree*) ;;; ABCDEFGHI ;;; NIL ;;; CL-USER> (post-order #'princ *test-tree*) ;;; ACEDBHIGF ;;; F ;;; CL-USER> (level-order #'princ *test-tree*) ;;; FBGADICEH ;;; NIL ```
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.