Family Tree display

Question

I am creating a family tree program. My question is how do i position the nodes? Originally i positioned the root at the center of my screen and it works fine if it is a perfect binary tree and the levels are very less. However it is not most often the case. This is a sample tree :-

            A
        B       C
    D   E   F   I   J
K   L               N   O

As you can see, the main problem is regarding the position of the nodes. If a node has many childs and it's adjacent node also has many children, they tend to overlap.(MAIN PROBLEM) I am using absolute positioning of the node using Canvas in Silverlight. You may not bother with the Silverlight and Canvas part if you are not a Silverlight developer. I just need the logic of how to position the nodes.

The height of the tree can be computed fairly easily by knowing the total number of levels of tree but the width of the tree is what is troubling me. How can i calculate the width of the tree (total width of the canvas)

Can somebody give me some general guidelines regarding how to set the width of the canvas and what logic will work perfect for the positioning of the nodes.

NOTE :- I am not asking for the whole algorithm and it is not my homework. I already have the algorithm and database. I just need guideline for the positioning part of the node.

Thanks in advance :)

Answer 1

I would suggest to give zoom in and zoom out functionality to unclutter the GUI Real Estate.

A Node with many children can be grouped and a special icon to denote it can be zoomed in to next level would be good i feel, as the family grows, as user can get big picture at first and as then can zoom into any branch he wishes too.

Take cues from google map's UI, might help.

Answer 2

If you implement a function: width(node) for arbitrary node of this tree, it is easy to positioning each node

This function may be defined recursively:
- for a tree of height 1 it tree this is exactly length of this node
- for a tree of height bigger than 1 this is a sum of lengths of all direct children of this node (plus some spaces between those)

Answer 3

I would recommend starting with the widest level of the tree if you want to guess the width of the canvas. You can calculate by traversing the tree breadth-first. Multiply the number of nodes at that level by the amount of lateral space each node needs and you have the width of canvas you require.

However, that's no guarantee that adjacent nodes on the widest level won't each have many children. So, to perform spacing with no overlap, start by positioning the leaves of the tree at the deepest level and traverse the tree backwards, adding parents above and putting leaves into the gaps and at the sides.