2015-11-03 79 views
1

我有一個艱鉅的任務需要你的幫助。按照一些規則逐級打印二叉樹

我需要打印一個二叉樹遵循此規則: 按級別打印級別,不使用矩陣; 必須從根目錄打印,並且打印後永遠不要編輯這些行; 該號碼不能與其他任何列相同。 這是格式:

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

謝謝。

+2

如果你發佈一些你的嘗試,你會得到更多的運氣。 – natario

+1

什麼是輸入格式? – Cruncher

+1

你問什麼具體問題?你迄今爲止做了什麼工作?你有沒有在http://stackoverflow.com/help/on-topic閱讀stackoverflow介紹:*提問作業幫助的問題必須包括你迄今爲解決問題所做的工作的總結,以及難以解決它。* –

回答

1

你正在做的事叫做Breadth First Search。鑑於AVL tree僅在添加或移除元素期間與正常的Binary Search Tree不同,因此應適用上面wiki鏈接中列出的BF-Search的算法邏輯。

+0

謝謝,這有助於很多。到目前爲止,我只打印第一層,並在樹上進一步深入。 –