Path: csiph.com!x330-a1.tempe.blueboxinc.net!feeder1.hal-mli.net!weretis.net!feeder1.news.weretis.net!feeder.erje.net!newsfeed.kamp.net!newsfeed.kamp.net!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail From: "Pascal J. Bourguignon" Newsgroups: comp.lang.python,comp.lang.lisp Subject: Re: English Idiom in Unix: Directory Recursively Date: Wed, 18 May 2011 20:57:25 +0200 Organization: Informatimago Lines: 51 Message-ID: <8762p7omzu.fsf@kuiper.lan.informatimago.com> References: <87aaekoab7.fsf@kuiper.lan.informatimago.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: individual.net KG/LDwE9E7Jg7qGSz8MG5gGohMkAmI6NiRvxrnWKIUakLPjbrc Cancel-Lock: sha1:NDM5NDcxMDBlN2NiYmRjZTI0ZjhlOTJmNDExOWZlMmU5NWViNmUyYg== sha1:u3hk4yIJodltmHh3+aoSwvJh8eY= Face: iVBORw0KGgoAAAANSUhEUgAAADAAAAAwAQMAAABtzGvEAAAABlBMVEUAAAD///+l2Z/dAAAA oElEQVR4nK3OsRHCMAwF0O8YQufUNIQRGIAja9CxSA55AxZgFO4coMgYrEDDQZWPIlNAjwq9 033pbOBPtbXuB6PKNBn5gZkhGa86Z4x2wE67O+06WxGD/HCOGR0deY3f9Ijwwt7rNGNf6Oac l/GuZTF1wFGKiYYHKSFAkjIo1b6sCYS1sVmFhhhahKQssRjRT90ITWUk6vvK3RsPGs+M1RuR mV+hO/VvFAAAAABJRU5ErkJggg== X-Accept-Language: fr, es, en User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.2 (gnu/linux) Xref: x330-a1.tempe.blueboxinc.net comp.lang.python:5727 comp.lang.lisp:3522 tar@sevak.isi.edu (Thomas A. Russ) writes: > Well, unless you have a tree with backpointers, you have to keep the > entire parent chain of nodes visited. Otherwise, you won't be able to > find the parent node when you need to backtrack. A standard tree > representation has only directional links. > > Consider: > > A--+---B----+---D > | | > | +---E > | | > | +---F > | > +---C > > If all you keep is the current and previous node, then the only thing > you have reference do when doing the depth-first traverse is: > 1. Current = A, Previous = null > 2. Current = B. Previous = A > 3. Current = D Previous = B > 4. Current = E Previous = D > 5. now what? You can't get from E or D back to B. > >> By comparing the previous node (pointer or ID) to the >> current node's parent and children one will know wherefrom the >> current node was entered, and can choose the next child in the >> list as the next node, or the parent if all children have been >> visited. A visit action may be added in any or all times the >> node is visited. >> >> This node requires no stack. The only state space is constant, >> regardless of the size of the tree, requiring just the two pointers >> to previous and current. > > This will only work if there is a backpointer to the parent. No, you don't need backpointers; some cases have been mentionned in the other answer, but in general: (defun parent (tree node) (if (member node (children tree)) tree (some (lambda (child) (parent child node)) (children tree)))) Yes, the question wasn't about time complexity. -- __Pascal Bourguignon__ http://www.informatimago.com/ A bad day in () is better than a good day in {}.