在二叉樹中交叉的節點

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，樹現在看起來是這樣的：