0
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Is this for your Huffman compressor? You could just ask about that you know. It might result in more useful answers. For example, if you're worried about representing the Huffman tree, what if I told you there are several ways to get the codes without building any tree? $\endgroup$ – harold Feb 12 '19 at 12:12
  • $\begingroup$ No this isn't for a Huffman compressor. Though that would be interesting. I have a long way to go before understanding how that works. I simply have been wanting to know how to encode trees in a relative way, i.e. math.stackexchange.com/questions/3103614/… $\endgroup$ – Lance Pollard Feb 12 '19 at 12:19
  • $\begingroup$ Please explain how to get codes without building a tree, I would love to know :) $\endgroup$ – Lance Pollard Feb 12 '19 at 12:23
  • 1
    $\begingroup$ There are various ways to get a valid set of code lengths (such as package merge and Engel coding, these also deal with a length limit which you often have) then you can generate canonical Huffman codes for that set of lengths $\endgroup$ – harold Feb 12 '19 at 12:38
  • 3
    $\begingroup$ Pointers are just integers. Array indices are just integers. So the array index of an array entry is a relative pointer (relative to the beginning of the array). Just store the difference of array indices. $\endgroup$ – Wandering Logic Feb 12 '19 at 17:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.