摘要：如果對樹的基本操作還不清楚的話，可參看樹結(jié)構(gòu)查找二叉樹直接給出遍歷方式打印節(jié)點，這個位置是中序遍歷既然我們已經(jīng)可以遍歷它，那有沒有方式可以記錄下當(dāng)前節(jié)點在第幾層呢也就是，第一層第二層第三層第四層。

載一棵小樹苗，精心培育，總有一天會長成參天大樹
????????????????比如查找二叉、AVL、B + *、紅黑……

但是，今天不種樹，改成畫樹……

事情時這樣的：在搞懂簡單二叉樹的過程中，經(jīng)常需要驗證自己的代碼有沒有問題，我之前的做法是“斷點+肉眼觀察”大法。隨著節(jié)點的增多，斷點還好，肉眼越來越扛不住，遂決定把樹打印出來。把樹的各種操作（新增/刪除節(jié)點）前后進行比對，是非一目了然！

對于上面的樹，我們已經(jīng)可以從根節(jié)點遍歷它了。（如果對樹的基本操作還不清楚的話，可參看【樹結(jié)構(gòu)1】查找二叉樹）

直接給出遍歷方式：

public void treeIterator(TwoForkTree tree){
    if(tree==null){
        return ;
    }

    treeIterator(tree.leftNode);
    System.out.print(tree.getId()+"	");   //打印節(jié)點，這個位置是“中序遍歷”
    treeIterator(tree.rightNode);
}

既然我們已經(jīng)可以遍歷它，那有沒有方式可以記錄下當(dāng)前節(jié)點在第幾層呢？也就是，第一層：32；第二層：20、40；第三層：35、41；第四層：38。如果可以做到，我們再按層級，一層一層的輸出，不就把樹打印出來了嘛！

怎么記錄當(dāng)前層級呢？對遍歷方法稍加變動即可

public void record(TwoForkTree tree,int index){
    if(tree==null){
        return ;
    }
    index++;
    record(tree.leftNode,index);
    System.out.println(index+":"+tree.getId()+"	");
    record(tree.rightNode,index);
}

執(zhí)行結(jié)果：

接下來的事情簡單了，我們把上述控制臺輸出的內(nèi)容，用Map保存下來，再逐行輸出即可。

//按層級存儲節(jié)點的值
@Getter
Map> layerTree = new HashMap<>();

public void record(TwoForkTree tree,int index){
    if(tree==null){
        return ;
    }
    index++;
    record(tree.leftNode,index);

    List layerData = layerTree.get(index);
    if(CollectionUtils.isEmpty(layerData)){
        layerData = new LinkedList<>();
        layerTree.put(index,layerData);
    }
    layerData.add(tree.id);

    record(tree.rightNode,index);
}

測試以及逐行輸出即可：

@Test
public void testRecord(){
    tree.record(tree,0);
    SimpleNode simpleNode = (SimpleNode) tree;
    Map> layerTree = simpleNode.layerTree;

    int layerIndex=0;
    while (layerIndex layerData = layerTree.get(layerIndex);
        for (Integer data:layerData){
            System.out.print(data+"	");
        }
        System.out.println();
    }
}

執(zhí)行結(jié)果：

網(wǎng)上的資料大部分到這里就結(jié)束了，但看看這個產(chǎn)物，雖然是把樹按層級打印出來了，但很多部分還需要你腦補才行。留白太大，對藝術(shù)作品還好，但學(xué)習(xí)研究還是盡可能精準的好。我想要的是，帶著枝杈的樹！

# 目標(biāo)

   32
  /  
20    40
     /  
    35   41
     
      38

怎么實現(xiàn)呢？遍歷節(jié)點過程中，像Map中存儲節(jié)點的時候，我們完全可以知道，它的子節(jié)點情況——如果有左子節(jié)點，記錄一個/；如果有右子節(jié)點，記錄一個。由此，我們可以封裝一個Bean。

class Printer{
    private Integer id;
    private int index;
    private String leftChildLink;
    private String rightChildLink;
}

對代碼進行調(diào)整后，效果變成這樣：

雖然還要進行腦補，但似乎容易了些？當(dāng)然，這不是結(jié)束，其實距離目標(biāo)效果就差最后一步了。我們需要對數(shù)值和子節(jié)點連接符（“/”、“”）分別存儲，輸出時根據(jù)上一層的位置做調(diào)整！

給出完整實現(xiàn)：

/**
 * 樹打印
 */
public void printTree(){
    Map> printMap = printTree(this,0);
    int layerIndex = 1;
    StringBuilder idBu = new StringBuilder();
    StringBuilder linkBu = new StringBuilder();
    LinkedList nextLineIdPositions = new LinkedList<>();
    while (layerIndex<=layerTreeMap.size()){
        List printers = printMap.get(layerIndex);
        int lastIdLen = 0;
        int lastIdPosition = 0;
        for(Printer printer:printers){
            int position;
            if(CollectionUtils.isEmpty(nextLineIdPositions)){
                position = 20;
            }else {
                position = nextLineIdPositions.removeFirst()-idLen(printer.getId())/2;
                if(position<=lastIdPosition+lastIdLen){
                    position+=idLen(printer.getId())/2;
                }
            }
            lastIdPosition = position;
            lastIdLen = idLen(printer.getId());
            appendAt(idBu,position,printer.getId()+"`");

            if(!Strings.isNullOrEmpty(printer.getLeftChildLink())
                    || !Strings.isNullOrEmpty(printer.getRightChildLink())){
                int linkPosition = idBu.length()-idLen(printer.getId());
                if(!Strings.isNullOrEmpty(printer.getLeftChildLink())){
                    appendAt(linkBu,linkPosition-idLen(printer.getId())/2,printer.getLeftChildLink());
                    nextLineIdPositions.add(linkPosition-idLen(printer.getId())/2);
                }

                if(!Strings.isNullOrEmpty(printer.getRightChildLink())){
//                        if(Strings.isNullOrEmpty(printer.getLeftChildLink())){
//                            linkPosition+=2;
//                        }
                    appendAt(linkBu,linkPosition+idLen(printer.getId()),printer.getRightChildLink());
                    nextLineIdPositions.add(linkPosition+idLen(printer.getId())+1);
                }
            }
        }
        System.out.println(idBu.toString());
        System.out.println(linkBu.toString());
        idBu.setLength(0);
        linkBu.setLength(0);
        layerIndex++;
    }

    // 數(shù)據(jù)還原
    layerTreeMap.clear();
}

private int idLen(Integer id){
    return (id+"").length();
}

private StringBuilder appendAt(StringBuilder bu,int position,String param){
    while (bu.length()> layerTreeMap = new HashMap<>();

private Map> printTree(TwoForkTree node,int index){

    if(node==null){
        return null;
    }

    index++;
    List tempList = layerTreeMap.get(index);
    if(CollectionUtils.isEmpty(tempList)){
        tempList = new LinkedList();
        layerTreeMap.put(index,tempList);
    }
    Printer printer = new Printer();
    tempList.add(printer);
    printer.setId(node.getId());
    printer.setIndex(index);
    if(node.leftNode!=null){
        printer.setLeftChildLink("/");
    }
    if(node.rightNode!=null){
        printer.setRightChildLink("");
    }

    printTree(node.leftNode,index);


    printTree(node.rightNode,index);

    return layerTreeMap;
}

@Setter
@Getter
public class Printer{
    private Integer id;
    private int index;
    private String leftChildLink;
    private String rightChildLink;
}

最終效果：

注：之所以加了分割符（ " 32` "后面的符號），是因為打印方法還略有不足——有時兩個節(jié)點會連在一起，沒辦法看出具體的節(jié)點值。分割符的存在算是投機取巧。