设置位置绘制二叉树(set position for drawing binary tree)

我想画一个二叉树像这样的图形框架（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）的

Answer 2:

提高帕维尔Zaichenkov的解决方案，

让根的index是1，而对于其他节点：

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

和Y是（考虑从深度1开始）：

Y = nodeIndex / (2 ^ depth)

这种算法，如果一个节点有两个孩子的，则节点和左子和节点，右键孩子woudl等于之间的距离之间的距离：

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 3:

我已经写了关于这个主题的文章。它可以在这里找到： http://adhavoc.com/BinaryTree.html

从本质上讲，你需要为左分别移动每个子节点，因为它可能被放置，需要提醒的是子节点必须左右父。然后向左移动分公司作为最右端，用同样的警告。

Answer 4:

我把它写在C ++中使用openframework（ http://www.openframeworks.cc/ ），为图形界面。

////////////////////////
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);

 }