图形二进制搜索树 - 节点间距

我很难计算二进制搜索树中节点之间的间距以供我分配。我有GUI实现，我可以手动创建树或通过导入文本文件以及其他功能创建它。图形二进制搜索树 - 节点间距

在二叉搜索树节点类中，有X和Y坐标的getter和setter方法，我应该使用。现在，我已经开始工作了，但这是我在互联网上散播的代码混搭。例如，见this link。

的事情是，我做的不希望使用此代码，因为

这不是我和
但这并没有利用提供的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); 
    } 
}

来源

2011-03-03 Daimo-S

我很乐意帮忙，什么是问题？你如何获得按顺序的遍历计数？ – biziclop 2011-03-03 23:42:19

问题是，如何在GUI中创建和显示二叉查找树时计算节点间距。我想我在我的问题中有一些漫不经心:) – 2011-03-04 00:13:35

对于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（）方法中。

来源

2011-03-03 23:55:26 ThomasRS

非常感谢托马斯的帮助。我需要让你说的东西沉浸在一点:) ..我会发布一个更新，如果/当我得到我的尤里卡时刻......谢谢 – 2011-03-04 00:17:49

如果你发现y水平第一，x将是直截了当 – ThomasRS 2011-03-04 00:35:16

感觉自由地问如果太难了，但那么代码将不会是你自己的..：P – ThomasRS 2011-03-04 18:08:11

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）

来源

2011-03-04 03:00:31 iluxa

嗨iluxa ...对于缺乏反应感到抱歉，对于间距问题，我仍然没有更多的努力。感谢您的帮助和回应，虽然:) ..虽然没有放弃 – 2011-03-07 02:50:43

图形二进制搜索树 - 节点间距

回答

相关问题