algorithm - que - establecer posición para dibujar un árbol binario

para que sirve un arbol binario

Question

Quiero dibujar un árbol binario con un marco gráfico (Qt) como este:

        9
       /  /
      1    10
    /  /     /
   0    5     11
  /    /  /
 -1   2    6

pero tengo un problema para configurar X e Y para cada nodo, ¿tienes alguna idea de establecer y fijar la posición? (Tengo solo la altura de cada nodo e izquierda-Niño y el Niño-derecho)

Answer 1

Dado el ancho canvasWidth y el alto canvasHeight del lienzo puede calcular la posición de cada nodo.

Primero, asignemos dos números a cada nodo: la profundidad del nodo y un índice serial del nodo en la fila completa. En su ejemplo, para cada nodo que asignamos (depth, index) como

(0, 1) / / (1, 1) (1, 2) / / / (2, 1) (2, 2) (2, 4) / / / (3, 1) (3, 3) (3, 4)

Como señaló @j_random_hacker, podemos encontrar el índice de un nodo recursivamente usando esta ecuación:

leftChildIndex = parentIndex * 2 - 1
rightChildIndex = parentIndex * 2

Esto se puede hacer usando BFS (costo: O (n)). Durante este treeDepth , treeDepth también información sobre la profundidad del árbol entero Profundidad del árbol. En nuestro caso treeDepth=3

Luego, dado canvasWidth , canvasHeight y treeDepth como constantes globales, la posición de cada nodo se puede encontrar así:

def position(depth, index):
    x = index * canvasWidth / (2^depth + 1)
    y = depth * canvasHeight / treeDepth
    return y, x

Entonces, en su caso, las posiciones serán (canvasHeight/treeDepth*y, canvasWidth*x) donde (y,x) para cada nodo

(0, 1/2) / / (1, 1/3) (1, 2/3) / / / (2, 1/5) (2, 2/5) (2, 4/5) / / / (3, 1/9) (3, 3/9) (3, 4/9)

Costo: O (n)

Answer 2

Lo escribo en c ++ usando openframework ( http://www.openframeworks.cc/ ) como una interfaz gráfica.

////////////////////////
void BSTree:: paint()
{
ppx=ofGetWidth()/(2+numNode());
ppy=ofGetHeight()/(2+findHeight());
draw(root,1,1);
}
 ////////////////////////
 int BSTree:: draw(TreeNode *n,int x,int y)
 {
int xr=x;  
if(n==NULL) return xr 
int lx=draw(n->l,x,y+1); 
xr+=numNode2(n->l); 
int rx=draw(n->r,xr+1,y+1);
n->draw(xr*ppx,y*ppy);
if(n->l!=NULL) ofLine(xr*ppx,y*ppy,lx*ppx,(y+1)*ppy);
if(n->r!=NULL) ofLine(xr*ppx,y*ppy,rx*ppx,(y+1)*ppy);

return xr;

 }



 ///////////////////////
 void TreeNode::draw(int x,int y)
 {
ofSetColor(255,130,200);
float radius = 25 ;
ofFill();       // draw "filled shapes"
ofCircle(x,y,radius);

ofSetHexColor(0x000000);
char xx[100] ;
sprintf(xx,"%d",data);
ofDrawBitmapString(xx, x-5,y);

 }

Answer 3

Estaba buscando una forma de dibujar árboles binarios en Qt y no pude encontrar un ejemplo, así que hice una lib para dibujar árboles binarios, aquí está https://github.com/rom1504/GenericBinaryTree

Su método parece correcto al principio (eso es lo que hice primero) pero si la última capa no está llena, el ancho del árbol mostrado será demasiado grande.

Answer 4

Mejore la solución de Pavel Zaichenkov,

Deje que el index la raíz sea 1, y para el otro nodo:

leftNodeIndex = parentNodeIndex * 2 - 1
rightNodeIndex = parentNodeIndex * 2 + 1

Y la Y sería (considere la profundidad desde 1):

Y = nodeIndex / (2 ^ depth)

Este algoritmo establece que si un nodo tiene dos hijos, entonces la distancia entre el nodo y el hijo izquierdo y la distancia entre el nodo y el hijo derecho serán iguales:

Y - leftChlidY = rightChlidY - Y

(1, 1/2) / / (2, 1/4) (2, 3/4) / / / (3, 1/8) (3, 3/8) (3, 7/8) / / / (4, 1/16) (4, 5/16) (4, 7/16)

Answer 5

He escrito un artículo sobre este mismo tema. Se puede encontrar aquí: http://adhavoc.com/BinaryTree.html

Básicamente, debe mover cada nodo secundario tan a la izquierda como sea posible, con la advertencia de que los nodos secundarios deben estar a la derecha y a la izquierda del elemento principal, respectivamente. Luego, mueva las ramas izquierdas lo más derecha posible, con la misma advertencia.