algorithmtreedrawingbinary-treedrawing2d

set position for drawing binary tree


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)


Solution

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