Creating a tree node diagram

Question

I am trying to create a tree like node diagram, like the example image here. I have the following code:

    private void DrawNode(Graphics g, Node<T> node, float xOffset, float yOffset)
    {
        if (node == null)
        {
            return;
        }

        Bitmap bmp = (from b in _nodeBitmaps where b.Node.Value.Equals(node.Value) select b.Bitmap).FirstOrDefault();

        if (bmp != null)
        {
            g.DrawImage(bmp, xOffset, yOffset);

            DrawNode(g, node.LeftNode, xOffset - 30 , yOffset + 20);
            DrawNode(g, node.RightNode, xOffset + 30, yOffset + 20);
        }
    }

My code is almost working. The problem I'm having is that some of the nodes are overlapping. In the picture above, nodes 25 and 66 are overlapping. The reason, I'm sure, is because its mathematically laying the left nodes and right nodes equal space, so the parent's right node overlaps with the adjacent parent's left node. How can I fix this problem?

UPDATE:

This is the code update I made after dtb's suggestion:

            int nodeWidth = 0;
            int rightChildWidth = 0;

            if (node.IsLeafNode)
            {
                nodeWidth = bmp.Width + 50;
            }
            else
            {
                int leftChildWidth = 0;

                Bitmap bmpLeft = null;
                Bitmap bmpRight = null;

                if (node.LeftNode != null)
                {
                    bmpLeft =
                        (from b in _nodeBitmaps where b.Node.Value.Equals(node.LeftNode.Value) select b.Bitmap).
                            FirstOrDefault();
                    if (bmpLeft != null)
                        leftChildWidth = bmpLeft.Width;
                }
                if (node.RightNode != null)
                {
                    bmpRight =
                        (from b in _nodeBitmaps where b.Node.Value.Equals(node.RightNode.Value) select b.Bitmap).
                            FirstOrDefault();
                    if (bmpRight != null)
                        rightChildWidth = bmpRight.Width;
                }

                nodeWidth = leftChildWidth + 50 + rightChildWidth;
            }


            g.DrawImage(bmp, xOffset + (nodeWidth - bmp.Width) / 2, yOffset);

            if (node.LeftNode != null)
            {
                DrawNode(g, node.LeftNode, xOffset, yOffset + 20);
            }
            if (node.RightNode != null)
            {
                DrawNode(g, node.RightNode, xOffset + nodeWidth - rightChildWidth, yOffset + 20);
            }

Here is a screenshot from this code:

Answer 1

Assign a width to each node:

• the width of a leaf is the width of the image, w.
• the width of a node is the width of its left child node + a constant d + the width of the right child node.

      

void CalculateWidth(Node<T> node)
{
    node.Width = 20;
    if (node.Left != null)
    {
        CalculateWidth(node.Left);
        node.Width += node.Left.Width;
    }
    if (node.Right != null)
    {
        CalculateWidth(node.Right);
        node.Width += node.Right.Width;
    }
    if (node.Width < bmp.Width)
    {
        node.Width = bmp.Width;
    }
}

Starting with the root node and x = 0, draw the image at the halve of the width, offset by x.
Then calculate the x position for each child node and recurse:

void DrawNode(Graphics g, Node<T> node, double x, double y)
{
    g.DrawImage(x + (node.Width - bmp.Width) / 2, y, bmp);

    if (node.Left != null)
    {
        DrawNode(g, node.Left, x, y + 20);
    }
    if (node.Right != null)
    {
        DrawNode(g, node.Right, x + node.Width - node.Right.Width, y + 20);
    }
}

Usage:

CalculateWidth(root);

DrawNode(g, root, 0, 0);

Answer 2

You're right that they're going to overlap. It's because you're adding/subtracting a fixed value to xOffset as you traverse down the tree. In the example picture, it's not actually a fixed offset: rather, it's logarithmic exponential with respect to its vertical position. The further down you go, the smaller the offset should be.

Replace the 30s with A * Math.Log(yOffset), where A is some scaling value that you'll have to tweak until it looks right.

EDIT: or is it exponential? I can't visualize this stuff too well. You might end up wanting A * Math.Exp(-B * yOffset) instead. (The negative is significant: this means it'll get smaller with larger yOffset, which is what you want.)

A will be like your master, linear scaling factor, while B will control how quickly the offset gets smaller.

double A = some_number;
double B = some_other_number;
int offset = (int)(A * Math.Exp(-B * yOffset));
DrawNode(g, node.LeftNode, xOffset - offset , yOffset + 20);
DrawNode(g, node.RightNode, xOffset + offset, yOffset + 20);

Update:

double A = 75f;
double B = 0.05f;
int offset = (int)(A * Math.Exp(-B * (yOffset - 10)));
DrawNode(g, node.LeftNode, xOffset - offset, yOffset + 20);
DrawNode(g, node.RightNode, xOffset + offset, yOffset + 20);

Called with:

DrawNode(e.Graphics, head, this.ClientSize.Width / 2, 10f);

The - 10 in the Exp is significant: it is the initial yOffset of the head. It produces the following:

If you want precise margin/padding control then by all means go with dtb's method, but I think 3 extra lines with a single formula is as elegant a mathematical solution as you're going to get.

Update 2:

One more thing I forgot: I'm using base e = 2.7183, but you'd want something closer to 2. Logically you would use exactly 2, but because the nodes have non-zero widths you might want something a bit bigger, like 2.1. You can change the base by multiplying B by Math.Log(new_base):

double B = 0.05f * Math.Log(2.1);

I should also explain how I got the value of 0.05f. Basically, you're increasing yOffset by 20 for each level of the tree. If I subtract the initial yOffset of the head (which is 10 in my case), then my first few yOffsets are 0, 20, 40, 60, etc. I want the x offset to be cut in half for each row; that is,

2 ^ (-0B) = 1
2 ^ (-20B) = 0.5
2 ^ (-40B) = 0.25

Obviously, B needs to be 1/20, or 0.05. I get the Math.Log(2.1) value from the relation:

base ^ exponent == e ^ (ln(base) * exponent)

So, with base 2.1, it looks like this: