java - 使用递归将二叉搜索 TreeMap 存储到数组中并打印出来

Question

我已经构建了一个二叉搜索树。我存储在树中的原始数据类型是整数。我尝试将它存储在一个二维字符数组中，然后打印出来如下图(数字代表行号和列号，我不需要打印它，请忽略“-”符号，我只使用它表示确切的位置)

-----0---1---2---3---4---5---6---7---8---9---10---11---12---13---14---15---16

0---------------------------------------12                             

1--------------------------------/-------------------\

2----------------------8--------------------------------------14

3-----------------/----------\ -----------------------------------------\

4-------------5----------------9-------------------------------------------34

5--------/-------------------------------------------------------------/-------------\

6---2---------------------------------------------------------24------------------------35

数字 12 需要存储在位置 [0][8]，第一行的中间。 数字 4 存储在 [2][4]，数字 14=[2][12]，5=[4][2]，9=[4][9] 等等。

第 1 行是第二行，“/”在位置[1][6] 和“\”在位置[1][10] 等，它们也在两个数字之间的中间

以下是我的代码

public class MainClass {
    public static void main(String[] args) {
        //level represents row number;
        // start indicates the column I am going to 
        //store number in, and end is a fixed column number
        // BinarySearchTree is a BinaryTree type instance,
        // I already story integers on it and follow with the format
        // of binary search trees, and I did tested it.
        int level=0; int start=0; int end=80;
        BinaryTree.plot(BinarySearchTree, level, start, end);
    }

private static class BinaryTree {

    private BinaryNode root;
    static char[][] offset = new char [10][20];

    public BinaryTree(){
        root = null;
    }

    public BinaryTree(Object x){
        root = new BinaryNode(x);
    }

    public boolean isEmpty(){
        return root == null;
    }  

    public Object getRootobj() throws BinaryTreeException{
        if(root == null) 
            throw new BinaryTreeException("Empty Tree");
        else
            return root.element;
    }

    public BinaryTree getLeft() throws BinaryTreeException{
        if(root == null)
            throw new BinaryTreeException("Empty Tree");
        else {
            BinaryTree t = new BinaryTree();
            t.root = root.left;
            return t;
        }
    }

    public BinaryTree getRight() throws BinaryTreeException{
        if(root == null)
            throw new BinaryTreeException("Empty Tree");
        else {
            BinaryTree t = new BinaryTree();
            t.root = root.right;
            return t;
        }
    }

    public static void plot(BinaryTree t, int level, int start, int end){
        if(!t.isEmpty()){
            plot(t.getLeft(), level+2, start/2, end/2);
            String string = Integer.toString((Integer)t.getRootobj());
            for(char c: string.toCharArray())
                offset[level][start++]=c;
            if(!(t.getLeft().isEmpty()))
                offset[++level][start/4*3] = '/';
            if(!(t.getRight().isEmpty()))
                offset[++level][((start+end)/2+start)/2] = '\\';
                plot(t.getRight(), level+2, end/2, end);
        }
        for(int i = 0; i<10; i++){
            for(int j= 0; j<20; j++)
                System.out.print(offset[i][j]);
        }
    }
}

private static class BinaryNode {

    Object element;
    BinaryNode left,right;

    BinaryNode() {
        this(0);
    }

    BinaryNode(Object e) {
        this(e, null, null);
    }

    BinaryNode(Object e, BinaryNode ln, BinaryNode m){
        element=e;
        left=ln;
        right=m;
    }
}
}

问题:我用来存储和打印出binarysearchtree的方法plot不起作用，导致java.lang.ArrayIndexOutOfBoundsException:

谁能看一下。感谢您的帮助。

Answer 1

您的固定大小的字符数组无法处理动态大小的二叉树。仅对于您给出的示例，您每行需要超过 20 个字符!这就是您的异常的来源。

但为了让您了解另一种方法 - 尽管需要一段时间，但请在您的代码中添加以下内容:

---

首先，我在 BinaryNode 类中添加了一个方法:

int getDepth() {
    int subTreeDepth;
    if (left == null && right == null) {
        subTreeDepth = 0;
    } else if (left == null) {
        subTreeDepth = right.getDepth();
    } else if (right == null) {
        subTreeDepth = left.getDepth();
    } else {
        subTreeDepth = Math.max(left.getDepth(), right.getDepth());
    }
    return 1 + subTreeDepth;
}

其次，我删除了你的固定字符数组并替换了你的 BinaryTree 中的整个绘图算法(我只是无法理解所有这些相关的数组索引操作):

public void plot() {
    if (root == null) {
        throw new BinaryTreeException("Empty Tree");
    }
    int lineCount = 2 * root.getDepth() - 1;
    StringBuilder[] lines = new StringBuilder[lineCount];
    for (int lineIndex = 0; lineIndex < lineCount; lineIndex++) {
        lines[lineIndex] = new StringBuilder();
    }
    // get the right most node (which contains the largest element value)
    BinaryNode rightMostNode = root;
    while (rightMostNode.right != null) {
        rightMostNode = rightMostNode.right;
    }
    // check how many characters we have to reserve for a single node element
    int maxElementLength = String.valueOf(rightMostNode.element).length();
    plot(root, 0, 0, maxElementLength, lines);
    for (StringBuilder singleLine : lines) {
        System.out.println(singleLine.toString());
    }
}

private void plot(BinaryNode subTreeRoot, int offset, int lineIndex, int elementLength, StringBuilder[] lines) {
    int actualOffset;
    if (subTreeRoot.left == null) {
        actualOffset = offset;
    } else {
        actualOffset = offset + (int) Math.pow(2, subTreeRoot.left.getDepth() - 1) * elementLength;
    }
    StringBuilder currentLine = lines[lineIndex];
    String elementValue = String.valueOf(subTreeRoot.element);
    for (int lineFillIndex = currentLine.length() + elementValue.length() / 2; lineFillIndex < actualOffset; lineFillIndex++) {
        currentLine.append(' ');
    }
    currentLine.append(elementValue);
    if (subTreeRoot.left != null) {
        // draw connection to left sub tree
        int connectPosition = (actualOffset - offset) * 3 / 4 + offset;
        StringBuilder connectLine = lines[lineIndex + 1];
        for (int lineFillIndex = connectLine.length(); lineFillIndex < connectPosition; lineFillIndex++) {
            connectLine.append(' ');
        }
        connectLine.append('/');
        // insert the left part of the next value line
        plot(subTreeRoot.left, offset, lineIndex + 2, elementLength, lines);
    }
    if (subTreeRoot.right != null) {
        // draw connection to right sub tree
        int connectPosition = actualOffset + elementLength - elementValue.length() / 2;
        if (subTreeRoot.right.left != null) {
            connectPosition += (int) Math.pow(2, subTreeRoot.right.left.getDepth() - 1) * elementLength / 2;
        }
        StringBuilder connectLine = lines[lineIndex + 1];
        for (int lineFillIndex = connectLine.length(); lineFillIndex < connectPosition; lineFillIndex++) {
            connectLine.append(' ');
        }
        connectLine.append('\\');
        // insert the right part of the next value line
        plot(subTreeRoot.right, actualOffset + elementLength, lineIndex + 2, elementLength, lines);
    }
}

对于与您在问题中包含的树相似的树:

BinaryTree binarySearchTree = new BinaryTree(
        new BinaryNode(12, 
                new BinaryNode(8,
                        new BinaryNode(5,
                                new BinaryNode(3),
                                null),
                        new BinaryNode(9)),
                new BinaryNode(14,
                        null,
                        new BinaryNode(34,
                                new BinaryNode(24),
                                new BinaryNode(35)))));
binarySearchTree.plot();

我得到以下输出:

       12
      /  \
    8    14
   /  \     \
  5   9      34
 /           / \
3          24  35