java - 遵循一些规则逐层打印二叉树

Question

我有一项艰巨的任务要做，需要你的帮助。

我需要遵循以下规则打印二叉树: 逐级打印，不使用矩阵； 必须从根开始打印，并且永远不应该在打印后编辑行； 该数字不能与任何其他数字位于同一列。 这是格式:

              |----10----|
           |--13--|      1---|
           15    11          0

它不是 AVL 树。必须在任何大小的树上工作。

这是我到目前为止所拥有的:

public String printTree() {
    if (getAltura() == -1) { //See if the tree is empty
        return "Arvore Vazia";
    }
    if (getAltura() == 0) { //Check if only have one node in the tree;
        return raiz.chave + "";
    }
    return printTree0();
}

private String printTree0() {
    String arvore = ""; //String with the binary tree
    //String linha = ""; 
    int espaco = 0; //That was what I try to use to put the number under the "|" character
    //int altura = 0;
    Queue<Nodo> q = new LinkedList<>();
    for (int i = 0; i <= getAltura(); i++) {
        q.addAll(getNivel(i));
    }

    while (!q.isEmpty()) {
        Nodo n = q.remove();
        if (n.direito == null && n.esquerdo == null) {
            for (int i = 0; i < espaco; i++) {
                arvore += " ";
            }
        }
        if (n.esquerdo != null) { //Check if this node has a left son.
            int subarvores = tamanhoSubarvores(n.esquerdo); //Do the math to see how many ASCII character are need to put in this side of the tree.
            for (int i = 0; i < subarvores; i++) {
                arvore += " ";
                espaco++;
            }
            arvore += "|";
            for (int i = 0; i < subarvores; i++) {
                arvore += "-";
            }
        }
        arvore += n.chave;
        if (n.direito != null) { //Check if this node has a right son.
            int subarvores = tamanhoSubarvores(n.direito); //Do the math to see how many ASCII character are need to put in this side of the tree.
            for (int i = 0; i < subarvores; i++) {
                arvore += "-";
            }
            arvore += "|";
            for (int i = 0; i < subarvores; i++) {
                arvore += " ";
            }
        }

        arvore += "\n";

    }

    return arvore;

}

private int tamanhoSubarvores(Nodo nodo) {
    int size = 0;
    for (Nodo n : getNivel(nodo.altura, nodo)) {
        size += Integer.toString(n.chave).length();
    }
    return size;
}

谢谢。

Answer 1

您正在尝试做的事情称为 Breadth First Search 。鉴于AVL树仅在添加或删除元素期间与普通二叉搜索树不同，上面wiki链接中列出的BF搜索的算法逻辑应该申请。