EPTI have a NLR traversal here that I made: http://pastebin.com/m5c01b50
I need a RNL traversal next and I just can't figure it out. Once again, it has to be iterative, no recursion allowed. Please help.
[!] Help with binary search trees.
| Blogs > Sinensis |
|
Sinensis
United States2513 Posts
I have a NLR traversal here that I made: http://pastebin.com/m5c01b50 I need a RNL traversal next and I just can't figure it out. Once again, it has to be iterative, no recursion allowed. Please help. | ||
|
onmach
United States1241 Posts
1. If there is a node to the right, push current node onto stack, follow right node (by setting it to currentNode). 2. If there is no right node, print current node. 3. If there is a left node push it onto stack. follow left node. 4. If there is no left node pop your current node from the stack. If you can't pop anything because your stack is empty, you are done. That _should_ do it. | ||
|
DeathByMonkeys
United States742 Posts
| ||
|
Sinensis
United States2513 Posts
The code I'm trying to implement this with is giving me nonsense output (only displays 3 nodes out of many). I've got the pseudocode and loop to accomplish it here: http://pastebin.com/m23f256a Any other suggestions? | ||
|
evanthebouncy!
United States12806 Posts
So normally if you want to write iter, or at least this is what I do, is I write a recursive one first, then try to convert it into an iterative one. For trees, the idea of a "fringe" is crusial, make sure you understand what it is and how to use it. Here's an overview: A fringe is where you put your unexpanded nodes on. For instance, if you want to do a Dpth first search on a tree and print everything, you can do: 1) recursively: define printTree(node): ......if leaf?(node) .........print node.content ......else: ..........printTree(node.left) ..........print node.content ..........printTree(node.right) 2) iteratively: define printTree(node): ......fringe = new Stack() ......visited = new Set() ......fringe.push(node) ......while(fringe.notEmpty()) ............current = fringe.pop ............if current in visited: ..................print current.content ............else: ..................visited.add(current) ..................fringe.push(current.left) ..................fringe.push(current) ..................fringe.push(current.right) remark: there's bit bug here where what if a node doesn't have children but whatever, the general idea is same. So then, breadth first search is EXACTLY THE SAME except you use a Que for your fringe, and a whole sort of tree search is done with different fringe implementation, and how to use it. In short, all tree search is done by maintaining a fringe, and deciding what/when to put in it, and how/when to take it out | ||
|
onmach
United States1241 Posts
Since you made a good faith attempt, here is my attempt at solving this. I have no compiled this, there may still be errors, but you can see that this is pretty close. http://pastebin.com/d3e9d837a The idea here is you have to go right as far as you can saving each node along the way into your stack, print the node, then go left once, right as far as you can again, print node, etc. When you can no longer go right or left, you go back up (that is where the pop comes in). I'm not a java programmer and I don't have an environment for it at work, so you'll undoubtedly have to tweak that a bit. I may have the termination condition slightly wrong, but otherwise I think that is pretty close. Edit: Actually this will have an infinite loop. You'll have to do what the guy above me said, you will have to keep a list of nodes you have visited so that you don't revisit them. At each step of the way, if the node you want to go to is in your list of visited nodes, you pretend it is null. Another way is to save the last node you worked on and compare that to the nodes of your current node and if it is on the right, only then do you go left and if it is on the left, you go up. That is way more efficient, but more difficult. | ||
| ||
