使用文本打印二叉搜索树

Question

我想以这种格式打印二叉查找树:

     4 
    / \
   /   \
  2     5 
 / \   / \
1   3 4   6

我想我必须获得树的深度，然后，对于每个级别，在每个元素前后打印一些空格。

public void printTree(BSTNode T, int depth) {
    for (int i = 1; i <= depth; i++){
        //then what?
    }

我不知道如何继续。

节点类：

public class BSTNode {
    private int value;
    private BSTNode left;
    private BSTNode right;

    public BSTNode(){
        value = 0;
        left = null;
        right = null;
    }

    public BSTNode(int x){
        value = x;
        left = null;
        right = null;
    }

    void setValue(int x){
        value = x;
    }

    int getValue(){
        return value;
    }

    void setLeft(BSTNode l){
        left = l;
    }

    BSTNode getLeft(){
        return left;
    }

    void setRight(BSTNode r){
        right = r;
    }

    BSTNode getRight(){
        return right;
    }
}

Answer 1

我已经找到了一个没有斜线的解决方案。先遍历树的宽度；在ArrayList中存储一个级别上找到的所有值；根据级别，在带有缩进和间距的一行上打印值；转到下一个级别并存储该级别的所有值，依此类推。

注释块用于斜线。

给定输入10,5,15,1,7,20,12,6,2,8到二叉查找树，没有斜杠的输出是

       10               
   5       15       
 1   7   12   20   
  2 6 8         

斜杠是

       10               
       / \       
      /   \      
     /     \     
    /       \    
   5       15       
   / \      / \   
  /   \    /   \  
 1   7   12   20   
 / \  / \  / \  / \ 
  2 6 8         

带有斜杠的解决方案的输出并不完美，需要改进。节点之间的间距存在一些问题。

public void printTree(BSTNode T, int depth) {
    int indent, spacing, numberOfSlashes;
    ArrayList value = new ArrayList();
    for (int d = 1; d <= depth; d++){
        value.clear();
        getLevel(value, T, d);
        indent = (int) (Math.pow(2, (depth-d)) - 1);
        spacing = (int) (Math.pow(2, (depth-d+1)) - 1);
        for (int i = 0; i < indent; i++){
            System.out.print(" ");
        }
        for (Object x: value){
            System.out.print(x);
            for (int i = 0; i < spacing; i++){
                System.out.print(" ");
            }
        }
        System.out.println();
        /*if (depth != d){
            numberOfSlashes = (int) Math.pow(2, (depth-d-1));
            printSlash(value, numberOfSlashes, indent, 1);
        }*/
    }
}

private void printSlash(ArrayList v, int slashes, int indent, int s) {
    for (int z = 0; z < slashes; z++){
        for (int index = 0; index < v.size(); index++){
            for (int i = 0; i < indent; i++){
                System.out.print(" ");
            }
            System.out.print("/");
            for (int space = 0; space < s; space++){
                System.out.print(" ");
            }
            System.out.print("\\");
            for (int nextSpace = 0; nextSpace < indent; nextSpace++){
                System.out.print(" ");
            }
        }
        System.out.println();
        indent = indent - 1;
        s = s + 2;
    }
}

private void getLevel(ArrayList v, BSTNode T, int l) {
    if (T == null)
        v.add(" ");
    else if (l == 1)
        v.add(T.getValue());
    else if (l > 1){
        getLevel(v, T.getLeft(), l-1);
        getLevel(v, T.getRight(), l-1);
    }
}   

Answer 2

您可以做的是获取一个队列，并在每个级别遍历时使用每个级别的节点对其进行初始化。之后弹出每个元素，打印它并推送以排队其左右节点。像这样继续遍历直到整个深度，您将能够以所需的格式打印树。

Answer 3

有一件事是肯定的：这不是一个容易的问题。这是我的方法。

首先，让我们直接递归。我希望能够做的是打印节点的左侧子树，然后打印右侧子树，然后以某种方式将这两者结合起来以获得我的最终结果。为此，我需要为这些中间值提供一个数据类：

public class TreeString {
    private List<String> lines;
    private int columnCount;
    private int rootColumn;

    public TreeString(List<String> lines, int columnCount, int rootColumn) {
        this.lines = new ArrayList<>(lines);
        this.columnCount = columnCount;
        this.rootColumn = rootColumn;
    }

    /** @return the number of lines */
    public int getLineCount() {
        return lines.size();
    }

    /** @return the number of columns */
    public int getColumnCount() {
        return columnCount;
    }

    /** @return the index of the column containing the center of the root */
    public int getRootColumn() {
        return rootColumn;
    }

    /** @return the number of columns to the right of the column containing the center of the root */
    public int getRootColumnFromRight() {
        return getColumnCount() - (getRootColumn() + 1);
    }

    /** @return the line at {@code index} */
    public String getLine(int index) {
        return lines.get(index);
    }
}

例如，这棵树

    4
   / \
  2   5
 / \
1   3

将由这个TreeString表示：

lines = new ArrayList<>(Arrays.asList("    4  ", "   / \\ ", "  2   5", " / \\   ", "1   3  "));
columnCount = 7;
rootColumn = 4;

请注意，所有行的长度相同。这在以后会很重要。

好，那么我们如何实现< code>printTree？嗯，很简单:我们< s >杀死蝙蝠侠写一些样板文件。

public void printTree(BSTNode node, int depth) {
    if (depth > 0) {
        TreeString treeString = treeStringFromBSTNode(node, depth);
        for (int i = 0; i < treeString.getLineCount(); ++i) {
            System.out.println(treeString.getLine(i));
        }
    }
}

public TreeString treeStringFromString(String string) {
    return new TreeString(Collections.singletonList(string), string.length(), string.length() / 2);
}

public TreeString treeStringFromBSTNode(BSTNode node, int depth) {
    TreeString value = treeStringFromString(String.valueOf(node.getValue()));
    TreeString left = depth <= 1 || node.getLeft() == null ? null : treeStringFromBSTNode(node.getLeft(), depth - 1);
    TreeString right = depth <= 1 || node.getRight() == null ? null : treeStringFromBSTNode(node.getRight(), depth - 1);
    return combineTreeStrings(value, left, right);
}

现在，我们来看主要事件:

public String spaces(int numSpaces) {
    String string = "";
    for (int i = 0; i < numSpaces; ++i) {
        string += " ";
    }
    return string;
}

public TreeString combineTreeStrings(TreeString parent, TreeString left, TreeString right) {
    if (left == null && right == null) {
        return parent;
    }

    // the number of lines between the bottom of parent and the tops of left and right
    // also the number of columns between parent's root column and the root columns of left or right
    int verticalGap = 1;
    // the number of columns between the left end of right and the right end of left
    int middleGap =  0;
    if (left != null && right != null) {
        verticalGap = Math.max(verticalGap, (left.getRootColumnFromRight() + 1 + right.getRootColumn()) / 2);
        middleGap = (verticalGap - left.getRootColumnFromRight()) + 1 + (verticalGap - right.getRootColumn());
    }

    // the number of columns between the left end of left (or right, if left is null) and the left end of the result
    int lowerLeftGap;
    // the number of columns between the left end of parent and the left end of the result
    int upperLeftGap;
    if (left != null) {
        lowerLeftGap = Math.max(0, parent.getRootColumn() - verticalGap - 1 - left.getRootColumn());
        upperLeftGap = Math.max(0, left.getRootColumn() + 1 + verticalGap - parent.getRootColumn());
    } else {
        lowerLeftGap = Math.max(0, parent.getRootColumn() + 1 + verticalGap - right.getRootColumn());
        upperLeftGap = Math.max(0, right.getRootColumn() - verticalGap - 1 - parent.getRootColumn());
    }

    // the number of columns between the right end of the result and the right end of right (or left, if right is null)
    int lowerRightGap;
    // the number of columns between the right end of the result and the right end of parent
    int upperRightGap;
    if (right != null) {
        lowerRightGap = Math.max(0, -right.getRootColumnFromRight() - 1 - verticalGap + parent.getRootColumnFromRight());
        upperRightGap = Math.max(0, -parent.getRootColumnFromRight() + verticalGap + 1 + right.getRootColumnFromRight());
    } else {
        lowerRightGap = Math.max(0, -left.getRootColumnFromRight() + verticalGap + 1 + parent.getRootColumnFromRight());
        upperRightGap = Math.max(0, -parent.getRootColumnFromRight() - 1 - verticalGap + left.getRootColumnFromRight());
    }

    List<String> lines = new ArrayList<>();
    // parent lines
    for (int i = 0; i < parent.getLineCount(); ++i) {
        lines.add(spaces(upperLeftGap) + parent.getLine(i) + spaces(upperRightGap));
    }
    // slash and backslash lines
    for (int i = 0; i < verticalGap; ++i) {
        String leftLeg;
        if (left != null) {
            leftLeg = "/";
        } else if (upperLeftGap > 0) {
            leftLeg = " ";
        } else {
            leftLeg = "";
        }

        String rightLeg;
        if (right != null) {
            rightLeg = "\\";
        } else if (upperRightGap > 0) {
            rightLeg = " ";
        } else {
            rightLeg = "";
        }

        int numLeftSpaces = upperLeftGap + parent.getRootColumn() - leftLeg.length() - i;
        int numRightSpaces = upperRightGap + parent.getRootColumnFromRight() - rightLeg.length() - i;
        lines.add(spaces(numLeftSpaces) + leftLeg + spaces(i + 1 + i) + rightLeg + spaces(numRightSpaces));
    }
    // left and right lines
    for (int i = 0; i < Math.max(left == null ? 0 : left.getLineCount(), right == null ? 0 : right.getLineCount()); ++i) {
        String leftLine;
        if (left == null) {
            leftLine = "";
        } else if (i >= left.getLineCount()) {
            leftLine = spaces(left.getColumnCount());
        } else {
            leftLine = left.getLine(i);
        }

        String rightLine;
        if (right == null) {
            rightLine = "";
        } else if (i >= right.getLineCount()) {
            rightLine = spaces(right.getColumnCount());
        } else {
            rightLine = right.getLine(i);
        }

        lines.add(spaces(lowerLeftGap) + leftLine + spaces(middleGap) + rightLine + spaces(lowerRightGap));
    }
    return new TreeString(lines, upperLeftGap + parent.getColumnCount() + upperRightGap, upperLeftGap + parent.getRootColumn());
}

希望这能解决你的问题！如果有什么方法可以清理，不要犹豫发表评论。