2

次のようなグラフィカルフレームワーク(Qt)でバイナリツリーを描画したい:

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

しかし、すべてのノードにXとYを設定するのに問題があります.設定と固定位置について何か考えはありますか? （私はすべてのノードと左子と右子の高さだけを持っています）

4

5 に答える 5

7

キャンバスの幅canvasWidthと高さを指定するとcanvasHeight、各ノードの位置を計算できます。

まず、各ノードに 2 つの数値を割り当てましょう。ノードの深さと、完全に入力された行のノードのシリアルインデックスです。あなたの例では、各ノードに次のように割り当て(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)

于 2013-01-06T23:32:14.410 に答える
2

Pavel Zaichenkovのソリューションを改善し、

ルートindexを 1 とし、他のノードの場合:

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

Y は次のようになります (深さが 1 から始まると考えてください)。

Y = nodeIndex / (2 ^ depth)

このアルゴリズムは、ノードに 2 つの子がある場合、ノードと左の子の間の距離と、ノードと右の子の間の距離が等しくなるようにします。

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)
于 2013-01-06T17:43:27.783 に答える
0

Qt で二分木を描画する方法を探していたのですが、例が見つからなかったので、二分木を描画するための lib を作成しました。こちらはhttps://github.com/rom1504/GenericBinaryTree

あなたの方法は最初は正しいようです（それが私が最初にしたことです）が、最後のレイヤーがいっぱいでない場合、表示されるツリーの幅が大きすぎます。

于 2013-06-27T01:45:48.560 に答える
0

グラフィカル インターフェイスとしてopenframework ( http://www.openframeworks.cc/ ) を使用して c++ で記述します。

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

 }
于 2013-05-01T11:17:38.223 に答える