Creando un diagrama de nodo de árbol

Question

Estoy tratando de crear un diagrama de nodo tipo árbol, como el example image here. Tengo el siguiente código:

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

Mi código casi funciona. El problema que estoy teniendo es que algunos de los nodos se superponen. En la imagen de arriba, los nodos 25 y 66 se superponen. La razón, estoy seguro, se debe a que matemáticamente los nodos derechos y los nodos derechos tienen el mismo espacio, por lo que el nodo derecho del padre se superpone con el nodo izquierdo del padre adyacente. ¿Como puedo solucionar este problema?

ACTUALIZACIÓN:

Ésta es la actualización de código que hice después de la sugerencia de DTB:

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

Aquí está una captura de pantalla de este código:

Answer 1

Asignar un ancho a cada node:

• la el ancho de una hoja es el ancho de la imagen, w.
• el ancho de un nodo es el ancho de su nodo secundario izquierdo + una constante d + el ancho del nodo secundario derecho.

       

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

Comenzando con el nodo raíz y x = 0, dibujar la imagen en el reducir a la mitad de la anchura, compensado por x.
luego calcular la posición x para cada nodo hijo y 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); 
    } 
} 

Uso:

CalculateWidth(root); 

DrawNode(g, root, 0, 0); 

Answer 2

Tienes razón de que van traslapar. Es porque está agregando/restando un valor fijo a xOffset mientras recorre el árbol. En la imagen de ejemplo, en realidad no es un desplazamiento fijo: más bien, es logarítmico exponencial con respecto a su posición vertical. Cuanto más baje, menor será el desplazamiento.

Reemplace los 30 con A * Math.Log(yOffset), donde A es un valor de escala que tendrá que ajustar hasta que se vea bien.

EDIT: ¿o es exponencial? No puedo visualizar esto demasiado bien. En su lugar, puede terminar queriendo A * Math.Exp(-B * yOffset). (Lo negativo es significativo: esto significa que va a llegar más pequeña con mayor yOffset, que es lo que desea.)

A será como su maestro, el factor de escala lineal, mientras que B controlarán la rapidez con que el desplazamiento se menor.

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

Actualización:

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

Llamado con:

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

El - 10 en el Exp es significativo: es el yOffset inicial de la cabeza. Se produce lo siguiente:

Si desea un control margen/acolchado precisa a continuación, por todos los medios seguir con el método de DTB, pero creo que 3 líneas adicionales con una única fórmula es tan elegante una solución matemática como usted' va a llegar

Actualización 2:

Una cosa más me olvidaba: Estoy usando la base e = 2.7183, pero te gustaría algo más cercano a 2. Lógicamente se podría usar exactamente 2, pero debido a que los nodos tienen no Cero anchos, es posible que desee algo un poco más grande, como 2.1.Puede cambiar la base de multiplicar por BMath.Log(new_base):

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

También debería explicar cómo llegué el valor de 0.05f. Básicamente, está aumentando yOffset en 20 para cada nivel del árbol. Si restamos el yOffset inicial del encabezado (que es 10 en mi caso), mis primeros yOffset s son 0, 20, 40, 60, etc. Quiero que el desplazamiento x se reduzca a la mitad para cada fila; es decir,

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

Obviamente, B necesita ser 1/20, o 0.05. Consigo el valor Math.Log(2.1) partir de la relación:

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

Así, con la base 2.1, se ve así: