set position for drawing binary tree

Question

I want to drawing a binary tree with an graphical framework(Qt) like this:

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

but I have a problem to set X and Y for every node, do you any idea to setting and fixation position ? (I have only height of every node and left-Child and right-Child)

Answer 1

I was looking for a way to draw binary trees in Qt and I couldn't find an example, so I made a lib to draw binary trees, here it is https://github.com/rom1504/GenericBinaryTree

Your method seems right at first (that's what I did first) but If the last layer isn't full the width of the displayed tree will be too large.

Answer 2

Given the width canvasWidth and the height canvasHeight of the canvas you can calculate position of each node.

First, let's assign two numbers to each node: the depth of the node and a serial index of the node in fully filled row. In your example, for each node we assign (depth, index) as

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

As @j_random_hacker pointed, we can find the index of a node recursively using this equation:

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

This can be done using BFS (cost: O(n)). During this traversal let's save also information about the depth of the whole tree treeDepth. In our case treeDepth=3

Then given canvasWidth, canvasHeight and treeDepth as global constants, each node's position can be found like this:

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

So in your case positions will be (canvasHeight/treeDepth*y, canvasWidth*x) where (y,x) for every node

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

Cost: O(n)

Answer 3

Improve the Pavel Zaichenkov's solution,

Let the root's index be 1, and for the other node:

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

And the Y would be (consider the depth start from 1):

Y = nodeIndex / (2 ^ depth)

This algorithm makes that if a node has two childs, then the distance between the node and left-child and the distance between the node and right-child woudl be equal:

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 4

I write it in c++ using openframework(http://www.openframeworks.cc/) as a graphical interface.

////////////////////////
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 5

I've written an article about this very subject. It can be found here: http://adhavoc.com/BinaryTree.html

Essentially, you need to move every child node as left as it can possibly be placed, with the caveat that the child nodes must be left and right of the parent respectively. Then move left branches as far right as possible, with the same caveat.