二叉树中的节点交叉

Question

我正在编写代码来构建二叉树并将其显示以用于家庭作业。（所以，自然地，我必须从头开始构建树。）代码功能，但我似乎无法理解想出一种方法来防止节点越过树下大约 4 层。我希望有人可以帮助启动我的大脑......但是有没有办法检查树下降了多少级别并调整上面级别的节点之间的水平距离？在我的研究中，我看到了一些不同的做法，但我的必须根据分配参数递归地使用 displayTree() 方法。任何帮助表示赞赏。

P.S。当前的 horizontalGap 变量是我一直在修改的，所以如果它弄乱了代码，我深表歉意。这是 displayTree() 方法。

//displayTree() with crossing issue
//**************************************************************************
public void displayTree(Graphics g, Node localTree, int x, int y, int level)

{
      // Display the root
      int verticalGap = 50;
      int horizontalGap = 250 / level;

      g.drawOval(x, y, radius, radius);
      g.drawString(localTree.getKey() + "", x + (radius / 4) , y + 20);

      if (localTree.getLeft() != null) {
         // Draw a line to the left node
         lineToLeftChild(g, x - horizontalGap, y + verticalGap, x, y);
        // Draw the left subtree recursively
         displayTree(g, localTree.leftChild, x - horizontalGap, y + verticalGap, level + 1);
      }

     if (localTree.rightChild != null) {
         // Draw a line to the right node
        lineToRightChild(g, x + horizontalGap, y + verticalGap, x, y);
        // Draw the right subtree recursively
        displayTree(g, localTree.rightChild, x + horizontalGap, y + verticalGap, level + 1);  
      }
    }//end displayTree()
    //**************************************************************************

    //Line to child
    //**************************************************************************
    private void lineToLeftChild(Graphics g,  int x1, int y1, int x2, int y2) { 
        g.drawLine(x1 + (radius/2), y1, x2, y2 + (radius/2));  
    }//end LinetoLeft
    //**************************************************************************

    //Line to child
    //**************************************************************************
    private void lineToRightChild(Graphics g, int x1, int y1, int x2, int y2) {
        g.drawLine(x1 + (radius /2), y1, (x2 + radius) , y2 + (radius/2));
    }//end line to Right()
    //**************************************************************************
}

Answer 1

这是您遇到的跨节点问题示例？

我认为您的节点在某种程度上开始交叉这一事实是您如何显示树的结果。较低级别的节点数可能比较高级别的节点数多得多，因此 space 的最小数量需要在节点数最多的级别确定。这会导致在更高级别出现大量白色 space。

您想支持多少个级别？您可以计算某个级别的最大节点数量的最小值 space（例如 2^6 的 10 个像素 = 根节点下 6 个级别的 64 个节点），并且每个更高级别的 space 加倍等级.

您还可以使用不同的方式来显示您的树，例如 "file manager" 类似于 The Java Tutorials - How to Use Trees 的方法，子节点根据需要占用 space :

编辑：代码示例

如果您想从 Stack Overflow 获得好的快速答案，最好在您的问题中添加一个简短的、可运行的问题示例（所谓的最小、完整和可验证的示例：请参阅 https://whosebug.com/help/mcve 获取更多信息）。这样你帮助别人帮助你。

这是我添加到您的代码中的一些代码，用于创建具有可能解决方案的示例：

// Main class TreeFromScratch:

import java.awt.BorderLayout;
import javax.swing.*;

public class TreeFromScratch {
    public static void main(final String[] arguments) {
        SwingUtilities.invokeLater(() -> new TreeFromScratch().createAndShowGui());
    }

    private void createAndShowGui() {
        final JFrame frame = new JFrame("Stack Overflow");
        frame.setBounds(100, 100, 1200, 600);
        frame.setDefaultCloseOperation(WindowConstants.EXIT_ON_CLOSE);

        final JPanel panel = new JPanel(new BorderLayout());
        final Node tree = createTree();
        panel.add(new CustomTree(tree), BorderLayout.CENTER);
        frame.getContentPane().add(panel);

        frame.setVisible(true);
    }

    private Node createTree() {
        final Node tree = new Node('a');
        tree.leftChild = new Node('b');

        tree.leftChild.leftChild = new Node('c');
        tree.leftChild.leftChild.leftChild = new Node('d');
        tree.leftChild.leftChild.leftChild.leftChild = new Node('e');
        tree.leftChild.leftChild.leftChild.leftChild.leftChild = new Node('f');

        tree.leftChild.rightChild = new Node('g');
        tree.leftChild.rightChild.rightChild = new Node('h');
        tree.leftChild.rightChild.rightChild.rightChild = new Node('i');
        tree.leftChild.rightChild.rightChild.rightChild.rightChild = new Node('j');

        tree.rightChild = new Node('k');
        tree.rightChild.leftChild = new Node('l');
        tree.rightChild.leftChild.leftChild = new Node('m');
        tree.rightChild.leftChild.leftChild.leftChild = new Node('n');
        tree.rightChild.leftChild.leftChild.leftChild.leftChild = new Node('o');

        return tree;
    }
}


// Class CustomTree:

import java.awt.Graphics;
import javax.swing.JPanel;

public class CustomTree extends JPanel {
    private Node tree;
    private int radius = 40;

    public CustomTree(Node tree) {
        this.tree = tree;
    }

    @Override
    protected void paintComponent(Graphics g) {
        displayTree(g, tree, 660, 100, 1);
    }

    //displayTree() with crossing issue
    //**************************************************************************
    public void displayTree(Graphics g, Node localTree, int x, int y, int level) {
        // Display the root
        int verticalGap = 50;
        //int horizontalGap = 250 / level;
        int horizontalGap = (int) (660 / Math.pow(2, level));

        g.drawOval(x, y, radius, radius);
        g.drawString(localTree.getKey() + "", x + (radius / 4), y + 20);

        if (localTree.getLeft() != null) {
            // Draw a line to the left node
            lineToLeftChild(g, x - horizontalGap, y + verticalGap, x, y);
            // Draw the left subtree recursively
            displayTree(g, localTree.leftChild, x - horizontalGap, y + verticalGap,
                        level + 1);
        }

        if (localTree.rightChild != null) {
            // Draw a line to the right node
            lineToRightChild(g, x + horizontalGap, y + verticalGap, x, y);
            // Draw the right subtree recursively
            displayTree(g, localTree.rightChild, x + horizontalGap, y + verticalGap,
                        level + 1);
        }
    }//end displayTree()
    //**************************************************************************

    //Line to child
    //**************************************************************************
    private void lineToLeftChild(Graphics g, int x1, int y1, int x2, int y2) {
        g.drawLine(x1 + (radius / 2), y1, x2, y2 + (radius / 2));
    }//end LinetoLeft
    //**************************************************************************

    //Line to child
    //**************************************************************************
    private void lineToRightChild(Graphics g, int x1, int y1, int x2, int y2) {
        g.drawLine(x1 + (radius / 2), y1, (x2 + radius), y2 + (radius / 2));
    }//end line to Right()
    //**************************************************************************
}


// Class Node:

public class Node {
    private char key;
    protected Node leftChild;
    protected Node rightChild;

    public Node(char key) {
        this.key = key;
    }

    public char getKey() {
        return key;
    }

    public Node getLeft() {
        return leftChild;
    }
}

通过不同的计算方式 horizontalGap，树现在看起来像这样：

二叉树中的节点交叉

Nodes crossing in Binary Tree

java

tree

swing

binary-tree