i just cant make this make any sense.
In order is left root right
http://en.wikipedia....aversal#Example
If left root right is followed then it SHOULD be:
ABDCEFGIH
i can see how i and h are exchanged if you simply go to the node furthest left in the graph but this is taking some imagination.
ive coded these things before using recursion and it makes sense that way, but the way they teach this is just... weird, almost chaotic
tree traversal question
Page 1 of 16 Replies  1464 Views  Last Post: 17 April 2012  08:06 PM
Replies To: tree traversal question
#2
Re: tree traversal question
Posted 17 April 2012  07:39 PM
The definition is applied recursively. So at G, the I node is treated as a subtree. So I is the root, H is the left child, and there is no right child. So H must be visited before I.
#3
Re: tree traversal question
Posted 17 April 2012  07:47 PM
macosxnerd101, on 17 April 2012  07:39 PM, said:
The definition is applied recursively. So at G, the I node is treated as a subtree. So I is the root, H is the left child, and there is no right child. So H must be visited before I.
So how do you explain C?
I find that to be much more difficult to understand
#4
Re: tree traversal question
Posted 17 April 2012  07:52 PM
Just remember this for an inorder traversal: Whenever you arrive at a node, try to go left. If you can't (NULL or 'visited' left child), then try to go the right. If you can't go right (NULL or 'visited' right child), mark the node as 'visited', print it, and go back to the parent and then mark the parent as 'visited'. The process starts all over again with the parent as the current node. Now according to this logic you have:
arrive at F, I can go left, go there arrive at B, I can go left, go there arrive at A, I can't go left (NULL) and I can't go right (NULL), mark as visited, go to parent and mark it as visited. arrive at B, I can't go left (visited), but I can go right, go there arrive at D, I can go left, go there arrive at C, I can't go left (NULL) and I can't go right (NULL), mark as visited, go to parent and mark it as visited. arrive at D ....
This post has been edited by blackcompe: 17 April 2012  07:58 PM
#5
Re: tree traversal question
Posted 17 April 2012  07:53 PM
You copied the inorder traversal wrong from Wikipedia. The actual ordering is:
Quote
Inorder traversal sequence: A, B, C, D, E, F, G, H, I (left, root, right); note how this produces a sorted sequence
#6
Re: tree traversal question
Posted 17 April 2012  07:59 PM
macosxnerd101, on 17 April 2012  07:53 PM, said:
You copied the inorder traversal wrong from Wikipedia. The actual ordering is:
Quote
Inorder traversal sequence: A, B, C, D, E, F, G, H, I (left, root, right); note how this produces a sorted sequence
I never copied it to begin with. I was following left root right and am looking for an explanation as to how to make it work.
blackcompe's idea makes sense, and produces the right answer which is helpful, but im still trying to reconcile the formal way
#7
Re: tree traversal question
Posted 17 April 2012  08:06 PM
Think about it recursively, with the following pseudocode:
Now when you invoke inorder(root) passing the F node from the Wikipedia example, it starts by going left until you hit A. Then you go back up to B, then back down to D. Rather than printing D, you print C first, then D, then back down to E. Walk through the pseudocode with the tree.
Hopefully this helps clear things up.
inorder(TreeNode root) if(root is null) return inorder(root>left) print root>element inorder(root>right)
Now when you invoke inorder(root) passing the F node from the Wikipedia example, it starts by going left until you hit A. Then you go back up to B, then back down to D. Rather than printing D, you print C first, then D, then back down to E. Walk through the pseudocode with the tree.
Hopefully this helps clear things up.
Page 1 of 1
