如何在我的 prettyPrint() BST 方法中根据任务的需要有效地打印白色 space

Question

对于我的 BST class 的漂亮打印方法，我们的讲师告诉我们树：

    bst.put(7, 7);   //        _7_
    bst.put(8, 8);   //      /     \
    bst.put(3, 3);   //    _3_      8
    bst.put(1, 1);   //  /     \
    bst.put(2, 2);   // 1       6
    bst.put(6, 6);   //  \     /
    bst.put(4, 4);   //   2   4
    bst.put(5, 5);   //        \
                     //         5

代码必须这样打印树：

                    "-7\n" +
                    " |-3\n" + 
                    " | |-1\n" +
                    " | | |-null\n" + 
                    " | |  -2\n" +
                    " | |   |-null\n" +
                    " | |    -null\n" +
                    " |  -6\n" +
                    " |   |-4\n" +
                    " |   | |-null\n" +
                    " |   |  -5\n" +
                    " |   |   |-null\n" +
                    " |   |    -null\n" +
                    " |    -null\n" +
                    "  -8\n" +
                    "   |-null\n" +
                    "    -null\n";

我已经得到了我的代码，可以使用递归打印出与讲师指定的树几乎完美的树，尽管我找不到一种方法来打印他指定的白色 spaces。我知道只在任何右子树上打印字符是一个问题，但我不确定正确打印 spaces 的方法。

我的代码是这样打印的：

-7
 |-3
 | |-1
 | | |-null
 | |-2
 | | |-null
 | |-null
 |-6 
 | |-4
 | | |-null
 | |-5
 | | |-null
 | |-null
 |-null
-8
 |-null
-null

如您所见，右子树节点没有前缀间距，任何为右子树节点添加 space 前缀的尝试只会改变树的格式。

这是我的代码，如有帮助将不胜感激

public String prettyPrintKeys() {
    String output = "";
    int indent = 0;
    output = prettyPrint(root, indent);
    System.out.print(output);
    return output;
}
private String prettyPrint(Node x, int indent){
    String output = "";
    for(int i=0; i<indent; i++){
        output = output + " |";
    }
    if(x == null){
        return output = output + "-null\n";
    }
    indent++;
    output = output + "-" + x.key + "\n" + prettyPrint(x.left, indent);
    indent--;
    output = output + prettyPrint(x.right, indent);
    return output;
}

Answer 1

我通常不做作业，但这有点棘手，而你已经完成了 90% 的作业。

您遇到了概念性错误。主要是我认为你可以 "return" 这个值以某种方式。我认为那行不通。您必须传入您的 return 值，以便可以添加它，就像您必须传入 indent 变量一样。

另一个问题是您没有仔细查看所需的输出。有两种缩进样式。一个用于打印右节点，其中“|”被打印，一个用于左节点，其中打印“”。您必须单独跟踪它们。

这是我的尝试，希望我做对了。 ;-)

package quicktest;

/**
 *
 * @author Brenden Towey
 */
public class TreePrint
{

   public static void main( String[] args )
   {
      Node root = new Node();
      fill( root );
      prettyPrintKeys( root );
   }

   public static String prettyPrintKeys( Node root )
   {
//      String output = "";
//      int indent = 0;
      StringBuilder indent = new StringBuilder();
      StringBuilder output = new StringBuilder();

      prettyPrint( root, indent, output );
      System.out.print( output );
      return output.toString();
   }

   private static void prettyPrint( quicktest.TreePrint.Node x,
           StringBuilder indent, StringBuilder output )
   {
//      for( int i = 0; i < indent; i++ )
//         output = output + " |";
      output.append( indent );
//      if( x == null )
//         return output = output + "-null\n";
      output.append( "-" );
      output.append( x );
      output.append( "\n" );
      if( x == null ) return;
//      indent++;
//      output = output + "-" + x.key + "\n" + prettyPrint( x.left, indent );
      indent.append( " |" );
      prettyPrint( x.left, indent, output );
//      indent--;
//      output = output + prettyPrint( x.right, indent );
      indent.delete( indent.length()-2, indent.length() );
      indent.append( "  " );  // <<-- second indent style
      prettyPrint( x.right, indent, output );

      // needed a second indent-- here
      indent.delete( indent.length()-2, indent.length() );
   }

   private static class Node
   {

      Comparable key;
      Node left;
      Node right;

      @Override
      public String toString()
      {
         return "Node{" + "key=" + key + '}';
      }


   }

   private static void fill( Node root )
   {
      insert( root, 7 );
      insert( root, 8 );
      insert( root, 3 );
      insert( root, 1 );
      insert( root, 2 );
      insert( root, 6 );
      insert( root, 4 );
      insert( root, 5 );
   }

   private static void insert( quicktest.TreePrint.Node node, Comparable newKey )
   {
      if( node.key == null ) {
         node.key = newKey;
         return;
      }
      if( node.key.compareTo( newKey ) > 0 ) {
         if( node.left == null ) node.left = new Node();
         insert( node.left, newKey );
         return;
      }
      if( node.right == null ) node.right = new Node();
      insert( node.right, newKey );
   }
}

这个程序的输出：

run:
-Node{key=7}
 |-Node{key=3}
 | |-Node{key=1}
 | | |-null
 | |  -Node{key=2}
 | |   |-null
 | |    -null
 |  -Node{key=6}
 |   |-Node{key=4}
 |   | |-null
 |   |  -Node{key=5}
 |   |   |-null
 |   |    -null
 |    -null
  -Node{key=8}
   |-null
    -null
BUILD SUCCESSFUL (total time: 0 seconds)

如何在我的 prettyPrint() BST 方法中根据任务的需要有效地打印白色 space

How to effectively print white space as necessary to the task in my prettyPrint() BST method

java

tree

pretty-print

binary-search-tree

如何在我的 prettyPrint() BST 方法中根据任务​​的需要有效地打印白色 space

How to effectively print white space as necessary to the task in my prettyPrint() BST method

java

tree

pretty-print

binary-search-tree

如何在我的 prettyPrint() BST 方法中根据任务的需要有效地打印白色 space