So you can store a binary tree without pointers using a 1-D array:
Binary Trees can be represented using 1-D array in memory(Fig 1).The rule to store binary tree in array are :
The values of binary tree is stored in an array called as tree. The root of the tree is stored at first location i.e. at tree[0](0 index). The left child of tree is stored at 2i +1 and right child is stored at 2i+2 location. The maximum size of the array tree is given as 2d+1-1, where d is the depth of the tree. An empty tree or sub-tree is specified using NULL. If tree[0] = NULL, then it means that tree is empty.
But this assumes the items are all the same size. In my case I'm wondering how to store them when the nodes contain arbitrarily sized data. You can do this by storing them using linked lists, but the problem with linked lists is they require pointers, and pointers are usually 32-bits which means they're large enough to point to anywhere in the typically available memory on most standard computers.
This is kind of a hack. You're basically doing absolute addressing for the nodes, where each pointer is an absolute address to the node. I'm instead wondering if there is any way to use relative addressing. That is, you say where the linked node is relative to the current node. This would allow for a linked-list like situation -- so it solves the dynamically sized records problem -- but without absolute addresses. I am having difficulty though, without having the advantage of absolute pointers, of how relative pointers might work with a tree.
