Creazione di un diagramma del nodo dell'albero

Question

Sto cercando di creare un diagramma ad albero come il nodo, come lo example image here. Ho il seguente codice:

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

Il mio codice è quasi funzionante. Il problema che sto avendo è che alcuni nodi si sovrappongono. Nell'immagine sopra, i nodi 25 e 66 si sovrappongono. Il motivo, ne sono sicuro, è perché il suo posizionamento matematico dei nodi di sinistra e dei nodi di destra equivale allo spazio, quindi il nodo destro del genitore si sovrappone al nodo sinistro del genitore adiacente. Come posso risolvere questo problema?

UPDATE:

Questo è l'aggiornamento del codice che ho fatto dopo il suggerimento del 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); 
      } 

Ecco uno screenshot da questo codice:

Answer 1

Assegnare una larghezza di ciascuna node:

• la la larghezza di una foglia è la larghezza dell'immagine, w.
• la larghezza di un nodo è la larghezza del suo nodo figlio sinistro + una costante d + la larghezza del nodo figlio destro.

       

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

partire dal nodo radice e x = 0, disegnare l'immagine a dimezzare della larghezza, compensato da x.
quindi calcolare la posizione x per ogni nodo bambino e 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

Hai ragione che stanno andando da sovrapporre. È perché stai aggiungendo/sottrai un valore fisso a xOffset mentre attraversi l'albero. Nell'immagine di esempio, in realtà non è un offset fisso: piuttosto, è logaritmico esponenziale rispetto alla sua posizione verticale. Più in basso vai, minore deve essere l'offset.

Sostituire gli anni 30 con A * Math.Log(yOffset), dove A è un valore di ridimensionamento che dovrete modificare fino a quando non sembra corretto.

EDIT: o è esponenziale? Non riesco a visualizzare troppo bene questa roba. Potresti finire col volere A * Math.Exp(-B * yOffset) invece. (Il negativo è significativo: questo significa che otterrà più piccolo con i più grandi YOffset, che è ciò che si desidera.)

A sarà come il tuo padrone, fattore di scala lineare, mentre B controllerà quanto velocemente l'offset ottiene più piccola.

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

Aggiornamento:

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

Chiamato con:

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

Il - 10 nel Exp è significativo: è la prima YOffset della testa. Produce il seguente:

Se si desidera un preciso controllo del margine/padding poi con tutti i mezzi andare con il metodo del DTB, ma credo che 3 linee in più con una sola formula è elegante una soluzione matematica, come si' sto per ottenere.

Aggiornamento 2:

Un'altra cosa che ho dimenticato: sto usando di base e = 2.7183, ma che ci si vuole qualcosa di più vicino a 2. Logicamente si userebbe esattamente 2, ma perché i nodi hanno non- zero larghe si potrebbe desiderare qualcosa di un po 'più grande, come 2.1.È possibile modificare la base moltiplicando B per Math.Log(new_base):

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

Vorrei anche spiegare come ho ottenuto il valore di 0.05f. Fondamentalmente, stai aumentando di yOffset di 20 per ogni livello dell'albero. Se sottrai l'iniziale yOffset della testata (che è 10 nel mio caso), i miei primi numeri yOffset sono 0, 20, 40, 60, ecc. Voglio che l'offset x sia tagliato a metà per ogni riga; ovvero,

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

Ovviamente, B deve essere 1/20 o 0,05. Ottengo il valore Math.Log(2.1) dalla relazione:

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

Così, con base 2.1, sembra che questo: