Печать двоичного дерева поиска с правильным форматированием

Question

У меня есть двоичная древовидная программа, которая сортирует меньшие/равные числа слева от родителя и большие числа справа от родителя, и я хочу распечатать ее диаграмму , но я не знаю, как распечатать его, чтобы он хорошо форматировался. Кроме того, если метод печати является частью класса TreeDriver или частью класса TreeNode для рекурсивного доступа к каждому узлу.

Вот классы:

TreeDriver:

import java.io.File; 
import java.io.FileNotFoundException; 
import java.util.Scanner; 

/** 
* This class serves as the driver for a generic TreeNode, giving it the type of Integer. 
*/ 
public class TreeDriver 
{ 
    //region Instance Variables 
    TreeNode<Integer> root; 
    //endregion 


    //region Constructors 
    public TreeDriver() throws FileNotFoundException 
    { 
     fill(); 
     System.out.println("Count: " + root.getCount()); 
    } 
    //endregion 


    //region Public Methods 
    public void fill() throws FileNotFoundException 
    { 
     Scanner reader = new Scanner(new File("TreeValueSource")); 
     String temp; 
     Integer entry; 

     makeRoot(); 

     while (reader.hasNext()) 
     { 
      temp = reader.nextLine(); 
      if (temp.contains("//")) 
      { 
       if (reader.hasNext()) 
        temp = reader.nextLine(); 
       else break; 
      } 
      else if (checkInt(temp)) 
      { 
       entry = new Integer(temp); 
       root.add(entry); 
      } 
      else System.out.println("ERROR IN FILL"); 
     } 
    } 

    private void makeRoot() 
    { 
     Scanner scan = new Scanner(System.in); 

     System.out.println("Enter a root value(default 50): "); 
     String input = scan.next(); 

     if (checkInt(input)) 
      root = new TreeNode<>(new Integer(input)); 
     else 
      root = new TreeNode<>(50); 
    } 


    public void printCount() 
    { 
     System.out.println(root.getCount()); 
    } 
    //endregion 


    //region Private Methods 
    private boolean checkInt(String candidate) 
    { 
     boolean parsable = true; 

     try 
     { 
      Integer.parseInt(candidate); 
     } catch (NumberFormatException e) 
     { 
      parsable = false; 
     } 

     return parsable; 
    } 
    //endregion 
} 

TreeNode:

public class TreeNode<T extends Comparable<T>> 
{ 
    //region Instance Variables 
    //Links 
    private TreeNode<T> leftChild; //Left Link 
    private TreeNode<T> rightChild; //Right Link 

    //Properties 
    private T data;   //Info Stored by the TreeNode 
    private int childCount; //Number of Children 
    private int depth;  //Level of the Node in the Tree 
    //endregion 


    //region Constructors 
    public TreeNode(T data, int parentDepth) 
    { 
     leftChild = null; 
     rightChild = null; 
     childCount = 0; 
     depth = parentDepth + 1; 
     this.data = data; 
    } 

    public TreeNode(T data) 
    { 
     leftChild = null; 
     rightChild = null; 
     childCount = 0; 
     depth = 0; 
     this.data = data; 
     System.out.println("A Root was Created"); 
    } 
    //endregion 


    //region Public Methods 

    /** 
    * ADD 
    * Adds a new TreeNode to the tree. Left if equal or smaller, Right if larger 
    * 
    * @param data The data held by the TreeNode 
    * @see TreeNode 
    */ 
    public void add(T data) 
    { 
     if (this.data.compareTo(data) <= 0) 
     { 
      addLeft(data); 
     } else if (this.data.compareTo(data) > 0) 
     { 
      addRight(data); 
     } else 
     { 
      System.out.println("ERROR IN TREENODE.ADD"); 
     } 
    } 


    public int getCount() 
    { 
     return count(); 
    } 


    /** 
    * IS LEAF 
    * Determines if the current node has no children 
    * 
    * @return True if no children, False otherwise 
    */ 
    public boolean isLeaf() 
    { 
     return childCount == 0; 
    } 
    //endregion 


    //region Private Methods 

    //Adds the data to the left of this.TreeNode 
    private void addLeft(T data) 
    { 
     if (null == leftChild) 
     { 
      leftChild = new TreeNode(data, depth); 
      childCount += 1; 
     } else 
      leftChild.add(data); 
    } 


    //Adds the data to the right of this.TreeNode 
    private void addRight(T data) 
    { 
     if (null == rightChild) 
     { 
      rightChild = new TreeNode(data, depth); 
      childCount += 1; 
     } else 
      rightChild.add(data); 
    } 


    /** 
    * COUNT 
    * Recursively counts the number of TreeNodes 
    * 
    * @return the number of TreeNodes, 0 if an error 
    */ 
    private int count() 
    { 
     if (isLeaf()) 
     { 
      return 1; 
     } else if (childCount == 2) 
     { 
      return 1 + leftChild.count() + rightChild.count(); 
     } else if (null == leftChild) 
     { 
      return 1 + rightChild.count(); 
     } else if (null == rightChild) 
     { 
      return 1 + leftChild.count(); 
     } else 
     { 
      System.out.println("ERROR IN COUNT AT DEPTH " + depth); 
      return 0; 
     } 
    } 
    //endregion 
} 

Answer 1

Вы можете использовать этот ответ в качестве модели

[How to print binary tree diagram?

Изменение класса BtreePrinter. И нет, вы не должны помещать метод печати в класс TreeDriver.

class Node<T extends Comparable<?>> { 
    Node<T> left, right; 
    T data; 

    public Node(T data) { 
     this.data = data; 
    } 
} 

class BTreePrinter { 

    public static <T extends Comparable<?>> void printNode(Node<T> root) { 
     int maxLevel = BTreePrinter.maxLevel(root); 

     printNodeInternal(Collections.singletonList(root), 1, maxLevel); 
    } 

    private static <T extends Comparable<?>> void printNodeInternal(List<Node<T>> nodes, int level, int maxLevel) { 
     if (nodes.isEmpty() || BTreePrinter.isAllElementsNull(nodes)) 
      return; 

     int floor = maxLevel - level; 
     int endgeLines = (int) Math.pow(2, (Math.max(floor - 1, 0))); 
     int firstSpaces = (int) Math.pow(2, (floor)) - 1; 
     int betweenSpaces = (int) Math.pow(2, (floor + 1)) - 1; 

     BTreePrinter.printWhitespaces(firstSpaces); 

     List<Node<T>> newNodes = new ArrayList<Node<T>>(); 
     for (Node<T> node : nodes) { 
      if (node != null) { 
       System.out.print(node.data); 
       newNodes.add(node.left); 
       newNodes.add(node.right); 
      } else { 
       newNodes.add(null); 
       newNodes.add(null); 
       System.out.print(" "); 
      } 

      BTreePrinter.printWhitespaces(betweenSpaces); 
     } 
     System.out.println(""); 

     for (int i = 1; i <= endgeLines; i++) { 
      for (int j = 0; j < nodes.size(); j++) { 
       BTreePrinter.printWhitespaces(firstSpaces - i); 
       if (nodes.get(j) == null) { 
        BTreePrinter.printWhitespaces(endgeLines + endgeLines + i + 1); 
        continue; 
       } 

       if (nodes.get(j).left != null) 
        System.out.print("/"); 
       else 
        BTreePrinter.printWhitespaces(1); 

       BTreePrinter.printWhitespaces(i + i - 1); 

       if (nodes.get(j).right != null) 
        System.out.print("\\"); 
       else 
        BTreePrinter.printWhitespaces(1); 

       BTreePrinter.printWhitespaces(endgeLines + endgeLines - i); 
      } 

      System.out.println(""); 
     } 

     printNodeInternal(newNodes, level + 1, maxLevel); 
    } 

    private static void printWhitespaces(int count) { 
     for (int i = 0; i < count; i++) 
      System.out.print(" "); 
    } 

    private static <T extends Comparable<?>> int maxLevel(Node<T> node) { 
     if (node == null) 
      return 0; 

     return Math.max(BTreePrinter.maxLevel(node.left), BTreePrinter.maxLevel(node.right)) + 1; 
    } 

    private static <T> boolean isAllElementsNull(List<T> list) { 
     for (Object object : list) { 
      if (object != null) 
       return false; 
     } 

     return true; 
    } 

}