Hey all...you've all been so helpful on my last question, so thank
you...so i have another question...
what is a good way to represent a tree in lisp? i understand lists
are good ways, but i want something that is easily searchable, like
for a depth-first or breadth-first search. Something that can retain
a value at each node of the tree...or if anyone has a better data
structure to do these searches with, i'm all ears... Any suggestions
please? Any help would be appreciated...
Thank you.
-Pete.
In article <················@news.columbia.edu>,
Peat <·····@columbia.edu> wrote:
>Hey all...you've all been so helpful on my last question, so thank
>you...so i have another question...
>what is a good way to represent a tree in lisp? i understand lists
>are good ways, but i want something that is easily searchable, like
>for a depth-first or breadth-first search. Something that can retain
>a value at each node of the tree...or if anyone has a better data
>structure to do these searches with, i'm all ears... Any suggestions
>please? Any help would be appreciated...
Use defstruct:
(defstruct tree-node
data
(subtree nil :type list))
The subtree would be a list of tree-node objects. Here's how you might use
it:
(defun depth-first-map (function tree-node)
(funcall function (tree-node-data tree-node))
(mapc #'depth-first-map (tree-node-subtree tree-node)))
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
Pete asks:
what is a good way to represent a tree in lisp? i understand lists are
good ways, but i want something that is easily searchable, like for a
depth-first or breadth-first search.
Well, list-style tree representations *are* easily searchable. However, in
general, it's better to explicitly define structures, e.g.
(defstruct node children value)
;; The root node of a tree is given value 'root.
(defun make-tree ()
(make-node :value 'root))
;; To add a child, make a node with the given value to the end of the list
;; children
(defun add-child (node value)
(setf (node-children node)
(append (node-children node) (list (make-node :value value)))))
;; Returns the value of the first node to pass the test, seached depth
;; first, or NIL if none is found.
(defun dfs (tree test)
(if (funcall test tree)
(node-value tree)
(some (lambda (child) (dfs child test)) (node-children tree))))
;; Of course, this is very simple, and you probably want to define
;; print-object methods, nicer interfaces to the particular nodes,
;; entries for a node's parents, etc.
;; testing
USER(21): (setq tree (make-tree))
#S(NODE :CHILDREN NIL :VALUE ROOT)
USER(22): (add-child tree 'first)
(#S(NODE :CHILDREN NIL :VALUE FIRST))
USER(23): (add-child (first (node-children tree)) 'second)
(#S(NODE :CHILDREN NIL :VALUE SECOND))
USER(24): (add-child tree 'third)
(#S(NODE :CHILDREN (#S(NODE # #)) :VALUE FIRST)
#S(NODE :CHILDREN NIL :VALUE THIRD))
USER(25): (pprint tree)
#S(NODE :CHILDREN
(#S(NODE :CHILDREN (#S(NODE :CHILDREN NIL :VALUE SECOND))
:VALUE FIRST)
#S(NODE :CHILDREN NIL :VALUE THIRD))
:VALUE ROOT)
USER(26): (dfs tree (lambda (node)
(format t "~%Testing node ~a" (node-value node))
(eq 'third (node-value node))))
Testing node ROOT
Testing node FIRST
Testing node SECOND
Testing node THIRD
THIRD
USER(27):
--
Lawrence Hunter, PhD.
National Library of Medicine phone: +1 (301) 496-9303
Bldg. 38A, 9th fl, MS-54 fax: +1 (301) 496-0673
Bethesda. MD 20894 USA email: ······@nlm.nih.gov
Hi, thanks for all your help...your advice is really helping me...i
was wondering if you have any suggestions on how i would put different
combinations of letters into a search space (tree)...say i had O for a
starting letter...this would be at the root...and i had a group of
letters, like FQG which can be added on as letters to form words like
OGF or OFG... for each level there would be another letter...ie. root
has O, next level has (OF OQ OG), the next level under OF would have
(OFG OFQ) etc...
i'm writing a game and this game requires that i try and find words
that fit...so in the instance above, i have O has some letter and i'm
trying to build words from a group of given letters onto that O. I
figured i would put the search space in the tree and search it,
finding the first word that fits...
Any other suggestions would be really welcome...
Thanks again...
-Pete.
In article <·················@news.columbia.edu>,
Peat <·····@columbia.edu> wrote:
>Hi, thanks for all your help...your advice is really helping me...i
>was wondering if you have any suggestions on how i would put different
>combinations of letters into a search space (tree)...say i had O for a
>starting letter...this would be at the root...and i had a group of
>letters, like FQG which can be added on as letters to form words like
>OGF or OFG... for each level there would be another letter...ie. root
>has O, next level has (OF OQ OG), the next level under OF would have
>(OFG OFQ) etc...
>i'm writing a game and this game requires that i try and find words
>that fit...so in the instance above, i have O has some letter and i'm
>trying to build words from a group of given letters onto that O. I
>figured i would put the search space in the tree and search it,
>finding the first word that fits...
This sounds like a B*-tree. I suggest you review the literature on
algorithms and data structures to see how to organize these. The
Lisp-specific details are secondary to understanding the data structure in
general.
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.