6 ms·
> There are ways to do a DFS of a tree without any sort of stack, though What do you mean by this? You need a way to say that the unexplored nodes we've most r
by hyt7u 12y ago
> There are ways to do a DFS of a tree without any sort of stack, though
What do you mean by this? You need a way to say that the unexplored nodes we've most recently found are the ones we explore first. How do you do that (with constant time operations) without what's effectively a stack?
- taeric 12y agoThreaded trees was what I had in mind.[1] I believe the example there still talks of checking a visited list, though. Either a misunderstanding on my part, or on that page. I'll have to check on my books. Later, sadly. :) [1] http://en.wikipedia.org/wiki/Threaded_binary_tree http://en.wikipedia.org/wiki/Threaded_binary_tree Edit: Apologies for a quick edit. I remembered I had a short implementation on my computer. Basically, when you follow a link, you know if it was a regular link or a thread. If it was a regular link, you could still go left from the new node. Otherwise, you visit and go right. Again, keep note of whether it was a thread or not. Repeat until done. (Make sense?)
- hyt7u 12y agoAh, great, thanks. I wasn't thinking about modifications to the tree.
- taeric 12y agoYeah, apologies if it looks like I was intentionally misleading. Was not my intent.
- al2o3cr 12y ago"Again, keep note of whether it was a thread or not." This sounds like the visited list again...
- taeric 12y agoYou only have to remember the link you just followed. Basically, make a boolean "followedThread" and initialize to false. Then, go to the root and follow this algorithm if (!followedThread && left != null) set followedThread <- curNode.left.isThread set curNode <- curNode.left.node else set followedThread <- curNode.right.isThread set curNode <- curNode.right.node Only node you really have to special case is the root node, and you can do that by making its right.node == null. Then you just do this while curNode != null. That make sense? (Also... very possible that I made a mistake here...)