i have question for example i want to implement binary tree with array i want understand what will indexes for left child and rigth child ?my array is 0 based i want implement searching in tree using array can anybody help me?
+4
A:
left child = parent * 2 + 1
right child = parent * 2 + 2
I imagine this is homework so I will let you figure out the searching algorithm.
danben
2010-05-28 16:28:34
A:
I think you are looking for a heap. Or at least, you use a tree when an array structure is not enough for your needs so you can try to implement a tree inside an array but it wouldn't make much sense since every node contains references to its children without any need of indices.
But an heap is an array that can also be seen as a binary tree, look it out here. It's a tree in the sense that it organizes data as a tree but without having direct references to the children, they can be inferred from the position.
Jack
2010-05-28 16:30:19
I think you're confused. A heap is a tree where the value of each child is less than (for a max-heap) or more than (for a min-heap) the value of its parent. This has nothing to do with whether a tree is implemented using an array or linked nodes.
sepp2k
2010-05-28 17:20:21
Of course it is so. I didn't say that a heap didn't have any kind of additional constraint. The fact is that usually you don't use an array to store a binary tree unless it's a specific type of binary tree (that is why I mentioned the heap). How useful would be to use an array to store a generic binary tree? Operations would be extremely unefficient compared to an implementation that used references..
Jack
2010-05-28 17:28:28
Why would it be extremely inefficient?
danben
2010-05-29 15:52:50
Because a rearrangment in the tree (think about a rotation: http://en.wikipedia.org/wiki/Tree_rotation) will imply moving many items instead that just changing some references..
Jack
2010-05-29 16:46:18
+4
A:
To implement a binary tree as an array you put the left child for node i at 2*i+1 and the right child at 2*i+2.
So for instance, having 6 nodes here's the indices of the corresponding array
0
|
---------
| |
---1-- --2--
| | | |
3 4 5 6
nico
2010-05-28 16:32:21