java图形二叉搜索树节点间距

1 月，2 周 Questions & Answers 2619

我很难为我的作业计算二叉搜索树中节点之间的间距。我已经实现了GUI，在那里我可以手动创建树，或者通过导入文本文件以及其他功能创建树

在二进制搜索树节点类中，我应该使用X和Y坐标的getter和setter方法。现在，我已经让它工作起来了，但这是我在互联网上找到的一堆代码。例如，见this link

问题是，我不想使用这段代码，因为

不是我的，而且

它不使用提供的getter和setter方法

我被告知，为了获得正确的间距：

X坐标与顺序遍历过程中处理节点的顺序数成正比

Y坐标与节点的深度有关

我有一个getHeight()方法，它可以工作，我假设它与获取深度相同

我希望有人能帮助我或给我指出正确的方向

更新

对于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); } }

# 2 楼答案

对于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始终是二进制且平衡的，则每个级别有2到n个节点的幂。如果没有，则必须首先检查每个级别有多少个节点。完成后，只需将屏幕宽度除以节点数，并将它们按顺序放置，同时添加到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（）方法中还没有需要绘制的节点，则可以修改此方法以将其返回给您

Python中文网

有 Java 编程相关的问题?

java图形二叉搜索树节点间距

共 (2) 个答案

# 1 楼答案

# 2 楼答案