algorithm - 设置绘制二叉树的位置

Question

我想用这样的图形框架 (Qt) 绘制二叉树:

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

但是我在为每个节点设置 X 和 Y 时遇到问题，您知道设置和固定位置吗？ (我只有每个节点的高度和左 child 和右 child )

Answer 1

给定 Canvas 的宽度 canvasWidth 和高度 canvasHeight，您可以计算每个节点的位置。

首先，让我们为每个节点分配两个数字:节点的深度 和节点在完全填充的行中的序列索引。在您的示例中，对于每个节点，我们将 (depth, index) 分配为

          (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

这可以使用 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)