Creating a node tree diagram

Question

I am trying to create a tree similar to a node diagram, for example, an 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 am facing is that some of the nodes overlap. In the image above, nodes 25 and 66 overlap. The reason, I'm sure, is that it mathematically stacks the left nodes and the right nodes in equal space, so the parent right node is superimposed on the neighboring parent left node. How can I fix this problem?

UPDATE:

This is the code update I made after the dtb 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 for each node :

• sheet width is the image width, w .
• the width of a node is the width of its left child element node + constant d + the width of its right child element 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 at the root of the node and x = 0 , draw an image with half the width shifted by x .
Then calculate the x position for each child node and write:

 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); } } 

Using:

 CalculateWidth(root); DrawNode(g, root, 0, 0); 

Answer 2

You are right that you are going to intersect. This is because you add / subtract a fixed value in xOffset when you cross the tree. In the example image, this is not actually a fixed offset: rather, it is logarithmic exponentially with respect to its vertical position. The farther you go, the smaller the offset should be.

Replace 30s with A * Math.Log(yOffset) , where A is some scaling value that you will need to adjust until it looks right.

EDIT : or is it exponential? I can not imagine this stuff too well. Instead, you might want A * Math.Exp(-B * yOffset) . (Negative is significant: this means that it will decrease as yOffset increases, which is what you want.)

A will look like your master, a linear scale factor, and B will control how quickly the bias decreases.

 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); 

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

If you need precise control of margin / indentation, then be sure to use the dtb method, but I think that 3 extra lines with one formula are as elegant mathematical solutions that you are going to get.

Update 2:

One more thing that I forgot: I use base e = 2.7183 , but you need something closer to 2. Logically you would use exactly 2, but since the nodes have a nonzero width, you might need something a little more 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 0.05f. Basically, you increase yOffset by 20 for each level of the tree. If I subtract the initial yOffset head (which in my case is 10), then my first few yOffset are 0, 20, 40, 60, etc. I want the offset x to be cut in half for each row; i.e

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

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

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

So, with base 2.1, it looks like this: