Quote:
Originally Posted by HelloWorld  But I need to somehow change the root in a real time so that it can compare when it's getRight or getLeft though  |
I'm not sure what you meant by the root being the constructor, although I think you've just discovered why while-loops don't cut the mustard. As I hinted at before, recursion is really the only elegant way to do these kinds of operations.
the pseudocode I posted is for a Binary search tree (try it). Binary search trees are deceptively simple - based on the mathematical concept of a binary search. In fact, they're far more difficult to explain than to create.
The best analogy I can think of is looking up a word in a dictionary, by starting in the middle, and eliminating half the remaining dictionary at a time - your "root node" is always whatever portion of the dictionary remains at each dictionary-traversal.
Here's some traversal psuedocode for the binary search tree. Again, really simple, but it works a treat.
Code:
Begin Method: In_Order_Traversal( Root )
If( Root is not NULL )
In_Order_Traversal( Root.left )
Write( Root.data )
In_Order_Traversal( Root.right )
End If
End Method Recursion perhaps isn't the most naturally easy concept to visualise - For a BSTree, it involves two "jumps" at each node (and generally not one-after-the-other, unless the node is a 'leaf' - ie, left and right are NULL), so it doesn't fit any ordinary looking flowcharts. Any accurate flow chart can only end up looking like the schematic of the BSTree itself.