Установить позицию для рисования бинарного дерева

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)

Answer 2

Улучшить решение Павла Зайченкова,

Пусть корень index быть 1, а для другого узла:

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

И Y будет (рассмотреть глубину, начиная с 1):

Y = nodeIndex / (2 ^ depth)

Этот алгоритм делает так, что если у узла есть два потомка, то расстояние между узлом и левым потомком и расстояние между узлом и правым потомком будут равны:

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

Я искал способ рисовать двоичные деревья в Qt, и я не смог найти пример, поэтому я сделал библиотеку для рисования двоичных деревьев, здесь это https://github.com/rom1504/GenericBinaryTree

Сначала ваш метод кажется правильным (это то, что я сделал первым), но если последний слой не заполнен, ширина отображаемого дерева будет слишком большой.

Answer 5

Я пишу это на 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);

 }