设置绘制二叉树的位置

Question

我想绘制一个带有图形框架(Qt)的二叉树,如下所示:

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

但是我为每个节点设置X和Y都有问题,你是否知道设置和固定位置？(我只有每个节点的高度和左 - 儿童和右儿童)

Answer 1

给定画布的宽度canvasWidth和高度canvasHeight,您可以计算每个节点的位置.

首先,让我们为每个节点分配两个数字:节点的深度和完全填充行中节点的串行索引.在你的榜样,对每个节点我们指定(depth, index)为

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

正如@j_random_hacker所指出的,我们可以使用以下等式递归地找到节点的索引:

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

这可以使用BFS(成本:O(n))来完成.在此遍历过程中,我们还会保存有关整棵树深度的信息treeDepth.在我们的例子中treeDepth=3

然后给出canvasWidth,canvasHeight并treeDepth作为全局常量,每个节点的地位可以这样找到:

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

所以你的情况职位将是(canvasHeight/treeDepth*y, canvasWidth*x)其中(y,x)的每个节点

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

费用:O(n)