java - 使用文本打印二叉搜索树

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

有一件事是肯定的:这不是一个简单的问题。这是我的方法。

首先，让我们弄清楚递归。我想要做的是打印节点的左子树，然后打印右子树，然后以某种方式组合这两个子树以获得最终结果。为此，我需要一个用于这些中间值的数据类:

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;

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

好的，那么我们如何实现printTree呢？嗯，这很简单:我们杀死 bat 侠编写一些样板文件。

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);
}

现在，进入主要 Activity :

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());
}

希望这能解决您的问题!如果有任何方法可以解决这个问题，请随时发表评论。