I took my second exam in Data Structures. There was a question that I could not understand. I recall it was worth 2 points so it should have been straightforward.
It say something similar like: If a binary tree was implemented using an array implementation. In Java A[0] retrieves the first element in the array. How do I retrieve the left and right child?
I did not want to leave the question blank so I wrote A[0.leftchild] and A[0.rightchild].
The question is about how you would implement a binary tree, using a regular 1D array as the storage area for the nodes.
For example, given an array of 7 nodes, you could define the left/right child relationships between the nodes like in this image:
e.g. the root node is at 0, it's left child is at 1 and right child at 4. The node at 1 has it's left child at 2 and right child at 3. The node at 4 has it's left child at 5 and right child at 6. The nodes at 2/3/5/6 are leaf nodes.
The examiner wanted you to write out a formula that would take a node index as input (and probably also the tree depth/array size as an input too), and produce the left/right node indices as output.
The question is about how you would implement a binary tree, using a regular 1D array as the storage area for the nodes.
For example, given an array of 7 nodes, you could define the left/right child relationships between the nodes like in this image:
e.g. the root node is at 0, it's left child is at 1 and right child at 4. The node at 1 has it's left child at 2 and right child at 3. The node at 4 has it's left child at 5 and right child at 6. The nodes at 2/3/5/6 are leaf nodes.
The examiner wanted you to write out a formula that would take a node index as input (and probably also the tree depth/array size as an input too), and produce the left/right node indices as output.
Why is the left child is at 1 and the right child is at 4 given a root node at 0? Why not make the left child at 1 and right child at 4? Would there be an issue? The left and right child are far apart in the array given a node at 0. But at node 1 and node 4 the children are close together in the array.
Alvaro has the right answer. I assume it is supposed to be a heap structure, since that is expandable (to as many nodes deep as you wish) in a straightforward manner.
Hodgman's method requires moving nodes if an extra level in the tree hierarchy is added.
In a binary tree, the left and right child of an index are 2n+1 and 2n+2.
The picture was just an example of mapping the nodes of the tree to different array indices. I deliberately didn't post a real formula so you could still learn it by yourselfWhy is the left child is at 1 and the right child is at 4 given a root node at 0? Why not make the left child at 1 and right child at 4? Would there be an issue? The left and right child are far apart in the array given a node at 0. But at node 1 and node 4 the children are close together in the array.
Álvaro's post contains the links that you should read.
The picture was just an example of mapping the nodes of the tree to different array indices. I deliberately didn't post a real formula so you could still learn it by yourselfWhy is the left child is at 1 and the right child is at 4 given a root node at 0? Why not make the left child at 1 and right child at 4? Would there be an issue? The left and right child are far apart in the array given a node at 0. But at node 1 and node 4 the children are close together in the array.
Álvaro's post contains the links that you should read.
Ah I see so there is multiple solutions to this then. Thanks for not posting a real formula!
This topic has been locked by a moderator. New replies are not allowed.
With your permission, GameDev.net uses analytics cookies to understand how people use the platform. You can accept analytics or continue with necessary cookies only. Learn more
