在二叉树中交叉的节点

Question

我正在研究构建二叉树并将其显示为作业分配的代码（因此，我必须从头开始构建树）。但是，我不能似乎找出了一种方法来防止节点从树上穿过4级。我希望有人能够帮助开始我的大脑......但是有没有办法检查树下面有多少层，并调整上面各层节点之间的水平距离？在我的研究中，我看到一些做法不同，但我必须通过displayTree（）方法递归地按照赋值参数进行递归。任何帮助表示赞赏。

P.S.当前的horizo​​ntalGap变量是我一直在修补的东西，所以如果它与代码混淆，我很抱歉。这里是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

这是跨节点问题的一个例子吗？

我认为，你的节点开始穿越在一定程度上其实是你如何展示你的树的结果。较低级别的节点数量可能会高得多，因此需要在节点数量最多的级别上确定最小空间量。这可能会导致更高层次上的大量空白。

你想支持多少个关卡？您可以计算某个级别上最大节点数量的最小空间（例如，根节点下面的6个级别为2^6 = 10个像素= 64个节点），每个更高级别为空间的两倍。

您也可以使用不同的方式来显示你的树，像这样的“文件管理器”就像从The Java Tutorials - How to Use Trees，那里的孩子节点占用同样大的空间的做法，因为他们需要：

编辑：代码示例

如果你想从堆栈溢出又好又快的答案，这是一个伟大的想法，你的问题很短，可运行例如添加到您的问题（所谓的最小，完整，可验证例如：见https://stackoverflow.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，树现在看起来是这样的：