圖形二進制搜索樹 - 節點間距

Question

我很難計算二進制搜索樹中節點之間的間距以供我分配。我有GUI實現，我可以手動創建樹或通過導入文本文件以及其他功能創建它。

在二叉搜索樹節點類中，有X和Y座標的getter和setter方法，我應該使用。現在，我已經開始工作了，但這是我在互聯網上散播的代碼混搭。例如，見this link。

的事情是，我做的不希望使用此代碼，因爲

1. 這不是我和
2. 但這並沒有利用提供的getter和setter方法。

我已被告知，在爲了得到間距右：

X座標成比例，其中該節點是在中序遍歷的過程中處理的順序號。

Y座標與節點的深度有關。

我有一個getHeight()方法，它的工作原理和我認爲是相同的深度。

我希望有人能幫助我或指引我走向正確的方向。

UPDATE

對於Y座標？

int index = -1; 
BinaryTreeNode nodes[]; 
int[] levels; 

public void build(BinaryTreeNode node, int level) 
{ 
    if (node != null) 
    { 
     build(node.getLeftNode(), level+1); 
     index++; 
     nodes[index] = node; 
     levels[index] = level; 
     build(node.getRightNode(), level+1); 
    } 
} 

Answer 1

對於Y座標，遍歷父節點並總結每個父節點的高度。對於每個父母，也加上一些白色間隔，即

int y = 0; 
Parent parent = child.getParent(); 
while(parent != null) { 
    y += 10; // spacing 
    y += parent.getHeight(); 

    parent = parent.getParent(); // next iteration 
} 

然而，這不是一個非常實用的方法。相反，你應該重複級別 - 從頂級節點開始，然後是前兩個孩子，然後是4個孫輩，等等。例如：將頂部節點添加到列表中，遍歷列表併爲其所有子項創建一個新列表，然後將新列表設置爲舊列表，然後在while循環中繼續，直到列表爲空。

現在對於x位置來說，它更棘手，因爲一個漂亮的佈局取決於該特定級別的節點數量。如果節點3總是二進制和平衡的，則每級有n個節點的功率爲2。如果沒有，你必須首先檢查每個級別有多少個節點。完成後，只需將屏幕寬度除以節點數並按順序放置，隨時添加到x座標中。

編輯： 我更喜歡這種方法：

class BinaryTreeNode { 

    BinaryTreeNode left; 
    BinaryTreeNode right; 

    int x; 
    int y; 
} 

public void position(BinaryTreeNode root, int nodeHeight, int nodeWidth, int screenWidth, int screenHeight) { 

    List<BinaryTreeNode> nodes = new ArrayList<BinaryTreeNode>(); 

    nodes.add(root); 

    int level = 0; 
    while(!nodes.isEmpty()) { 

     // we know now the number of nodes and the level 
     int y = level * nodeHeight; 

     // the x position depends on the number of nodes: 
     int widthPerNode = screenWidth/nodes.size(); 

     int x = 0; // start at leftmost 

     // now have (fixed) y position and starting point for x (leftmost) 
     for(BinaryTreeNode node : nodes) { // for loop iterates in-order 
      node.y = y; 
      node.x = x; // TODO: center node within available space 

      x += widthPerNode; 
     } 

     // this level is complete, store all children in a list 
     List<BinaryTreeNode> childNodes = new ArrayList<BinaryTreeNode>(); 
     for(BinaryTreeNode node : nodes) { // for loop iterates in-order 
      if(node.left != null) { 
       childNodes.add(node.left); 
      } 
      if(node.right != null) { 
       childNodes.add(node.right); 
      } 
     } 

     // continue to next level using the collected children as the new parents 
     nodes = childNodes; 

     level++; 
    } 

    // TODO: insert insets between nodes 
    // TODO: insert stop criteria for y outside screen 
    // TODO: insert stop criteria for x outside screen 
    // TODO: getters and setters 

} 

此外，您還可以修改此方法以返回到您的人需要繪製的節點，如果這不是已經在你的paint（）方法中。

Answer 2

Y軸很簡單。傳播100個像素的水平，你就完成了。

X軸更棘手。

假設您有1個節點（葉節點）。它需要說40個像素（導致40個像素是圓的大小）

假設您有一個有兩個葉子的節點。總寬度= 40 * 2 +間距。 （比如說SPACING = 20）= 100.

假設您有第三層節點。每個孩子爲100個像素，因此100 * 2 + SPACING = 220。

第四級節點：220 * 2 + 20 = 460。

第n級節點：40 * 2 ^（正1）+（2 ^（n-1）-1）* 20 = SIZE * 2 ^（n-1）+ SPACING *（2 ^（n-1）-1）