#:g1: ArcでL-99 (P59 左右で高さのバランスのとれた二分木)

Posted 2008-05-17 20:09:00 GMT

-(http://www.ic.unicamp.br/~meidanis/courses/mc336/2006s2/funcional/L-99_Ninety-Nine_Lisp_Problems.html)
ここでいう左右で高さのバランスのとれた二分木とは、左右の木た高さの差が±1までの二分木とのこと。
本来バックトラックで解くところですが、全通り生成しております。
そして、hbal-treeで条件を満した木を選り分けているのですが、最初から条件を満した木を生成してしまっているため、意味のないことになっております…。

;(each x (firstn 5 (hbal-tree 3)) (prn x))
;>>>
;(x (x (x nil nil) (x nil nil)) (x (x nil nil) (x nil nil)))
;(x (x (x nil nil) nil) (x (x nil nil) (x nil nil)))
;(x (x nil (x nil nil)) (x (x nil nil) (x nil nil)))
;(x (x (x nil nil) (x nil nil)) (x (x nil nil) nil))
;(x (x (x nil nil) nil) (x (x nil nil) nil))

(def hbal-tree (h) (keep hbal-tree-p gen-tree-h.h))

(def gen-tree-h (h) (case h 0 '(()) 1 '((x () ())) (with (h-1 (gen-tree-h (- h 1)) h-2 (gen-tree-h (- h 2))) (map (fn (tree) `(x ,@tree)) `(,@(comb2 h-1 h-1) ,@(comb2 h-1 h-2) ,@(comb2 h-2 h-1))))))

(def hbal-tree-p (tree) (let (_ left right) tree (>= 1 (abs (- tree-height.left tree-height.right))))

(def tree-height (tree) (let (_ left right) tree (if tree (+ 1 (max tree-height.left tree-height.right)) 0)))


comments powered by Disqus