设置绘制二叉树的位置 [英] set position for drawing binary tree

问题描述

我想用这样的图形框架（Qt）绘制二叉树：

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

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

但是我在为每个节点设置X和Y时遇到问题，您对设置和固定位置有任何想法吗？ （我只有每个节点的高度以及左子节点和右子节点的高度）

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)

推荐答案

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

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

首先，让我们为每个节点分配两个数字：节点的 depth 和完全填充的行中节点的串行 index 。在您的示例中，我们为每个节点分配（深度，索引）为

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)

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

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

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

然后给出 canvasWidth ， canvasHeight 和 treeDepth 作为全局常量，每个节点的位置可以这样找到：

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

将为（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）

这篇关于设置绘制二叉树的位置的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！