Drawing a Symmetric Binary B-Tree

I have a little "project" which involves drawing Symmetric Binary B-Trees, like this one: adad

But I cant figure out a way to correctly calculate the position (x,y) of each node. The way Im doing it right now, as the tree's height grows some nodes tend to get overlapped by others.

Can anyone give me some light as to how can I calculate the position of a node?

Im using C# and this is the class I have right now that represents a node:

class SBBTreeNode<T> where T : IComparable {

        public SBBTreeNode(T item) {
            Data = item;
            Left = null;
            Right = null;
        }

        public T Data { get; private set; }
        public SBBTreeNode<T> Left;
        public SBBTreeNode<T> Right;
        public bool IsHorizontal { get; set; } //Is this node horizontal?

        public bool IsLeaf() {
            return Left == null && Right == null;
        }
    }

Solution

Here is a drawing routine:

void drawTree(Graphics G)
{
    if (flatTree.Count <= 0) return;
    if (maxItemsPerRow <= 0) return;
    if (maxLevels <= 0) return;
    int width = (int)G.VisibleClipBounds.Width / (maxItemsPerRow + 2);
    int height = (int)G.VisibleClipBounds.Height / (maxLevels + 2);
    int side = width / 4;
    int textOffsetX = 3;
    int textOffsetY = 5;
    int graphOffsetY = 50;
    Size squaresize = new Size(side * 2, side * 2);

    foreach (SBBTreeNode<string> node in flatTree)
    {
        Point P0 = new Point(node.Col * width, node.Row * height + graphOffsetY);
        Point textPt = new Point(node.Col * width  + textOffsetX, 
                                    node.Row * height + textOffsetY + graphOffsetY);
        Point midPt = new Point(node.Col * width + side, 
                                node.Row * height + side + graphOffsetY);

        if (node.Left != null)
            G.DrawLine(Pens.Black, midPt, 
                new Point(node.Left.Col * width + side, 
                          node.Left.Row * height + side + graphOffsetY));
        if (node.Right != null)
            G.DrawLine(Pens.Black, midPt, 
                new Point(node.Right.Col * width + side, 
                          node.Right.Row * height + side + graphOffsetY));

        G.FillEllipse(Brushes.Beige, new Rectangle(P0, squaresize));
        G.DrawString(node.Data, Font, Brushes.Black, textPt);
        G.DrawEllipse(Pens.Black, new Rectangle(P0, squaresize));
    }
}

and its result:

b-tree

Usage:

flatTree  = FlatTree();
setRows();
setCols();
panel_tree.Invalidate();

Now for the various pieces that lead up to this:

The drawTree routine is obviously triggered from a Panel's Paint event.

I uses a few class level variables:

This is the Tree I build in my tests; please note that to make things a little simpler I have dumped your generic type T for string:

Dictionary<string, SBBTreeNode<string> > tree
        = new Dictionary<string, SBBTreeNode<string>>();

This is a flat traversal copy of the tree, that is, its elements are ordered by level and from left to right:

List<SBBTreeNode<string>> flatTree = new List<SBBTreeNode<string>>() ;

Here are the dimesions of the tree:

int maxItemsPerRow = 0;
int maxLevels = 0;

This is how the flat tree is created, using a Queue:

List<SBBTreeNode<string>> FlatTree()
{
    List<SBBTreeNode<string>> flatTree = new List<SBBTreeNode<string>>();
    Queue<SBBTreeNode<string>> queue = new Queue<SBBTreeNode<string>>();

    queue.Enqueue((SBBTreeNode<string>)(tree[tree.Keys.First()]));
    flatNode(queue, flatTree);
    return flatTree;
}

This is the recursive call to get the nodes in order:

void flatNode(Queue<SBBTreeNode<string>> queue, List<SBBTreeNode<string>>flatTree)
{
    if (queue.Count == 0) return;

    SBBTreeNode<string> node = queue.Dequeue();
    if (!node.IsHorizontal) flatTree.Add(node);
    if (node.Left != null) { queue.Enqueue(node.Left); }
    if (node.Left != null && node.Left.Right != null && node.Left.Right.IsHorizontal) 
        queue.Enqueue(node.Left.Right);
    if (node.Right != null) 
    { 
        if (node.Right.IsHorizontal) flatTree.Add(node.Right);   
        else queue.Enqueue(node.Right); 
    }
    flatNode(queue, flatTree);
}

Finally we can set the (virtual) coordinates of each node:

void setCols()
{
    List<SBBTreeNode<string>> FT = flatTree;
    int levelMax   = FT.Last().Row;
    int LMaxCount = FT.Count(n => n.Row == levelMax);
    int LMaxCount1 = FT.Count(n => n.Row == levelMax-1);
    if (LMaxCount1 > LMaxCount)
      { LMaxCount = LMaxCount1; levelMax = levelMax - 1; }

    int c = 1;
    foreach (SBBTreeNode<string> node in FT) if (node.Row == levelMax)
        {
            node.Col = ++c;
            if (node.Left != null) node.Left.Col = c - 1;
            if (node.Right != null) node.Right.Col = c + 1;
        }

    List<SBBTreeNode<string>> Exceptions = new List<SBBTreeNode<string>>();

    for (int n = FT.Count- 1; n >= 0; n--)
    {
       SBBTreeNode<string> node = FT[n];
       if (node.Row < levelMax)
       {
          if (node.IsHorizontal) node.Col = node.Left.Col + 1;
          else if ((node.Left == null) | (node.Right == null)) {Exceptions.Add(node);}
          else node.Col = (node.Left.Col + node.Right.Col) / 2;
       }
    }
    // partially filled nodes will need extra attention
    foreach (SBBTreeNode<string> node in Exceptions) 
                                 textBox1.Text += "\r\n >>>" + node.Data;
    maxLevels = levelMax;
    maxItemsPerRow =  LMaxCount;
}

Note that I have not coded the special case of partially filled nodes but only add them to a list of exceptions; you have to decide what to do with those, ie if they can happen and where they ought to be painted.

OK, this is almost it. We have to do two more things:

I have taken the liberty to add two coordinate fields to your node class:

public int Row { get; set; }
public int Col { get; set; }

And I have writen my AddNode routine in such a way that the level of each node is set right there.

You will certainly want/need to do it differently. A simple SetRows routine is a snap, especially when you use the flatTree for transversal:

void setRows()
{
    foreach (SBBTreeNode<string> node in flatTree)
    {
        if (node.Left != null)  node.Left.Row = node.Row + 1;
        if (node.Right != null) node.Right.Row = 
                                node.Row + 1 - (node.Right.IsHorizontal ? 1:0);
    }
}

Explanation:

Besides the flatTree, I use for drawing, the core of the solution is the SetCols routine.

In a balanced B-Tree the maximum width is reached either at the last or the second-to-last row.

Here I count the number of nodes in that row. This gives me the width of the whole tree, maxItemsPerRow. The routine also sets the height as maxLevels

Now I first set the Col values in that widest row, from left to right (and if present to dangling children in the last row.)

Then I move up level by level and calculate each Col value as the middle between the Left and Right Child, always watching out for horizontal nodes.

Note that I assume that all horizontal nodes are right children! If that is not true you will have to make various adaptions in both the FlatTree and the setCol routines..