国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

【樹結構2】樹打印

bawn / 3300人閱讀

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

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

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

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

思路

對于上面的樹,我們已經可以從根節點遍歷它了。(如果對樹的基本操作還不清楚的話,可參看【樹結構1】查找二叉樹)

直接給出遍歷方式:

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

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

既然我們已經可以遍歷它,那有沒有方式可以記錄下當前節點在第幾層呢?也就是,第一層:32;第二層:20、40;第三層:35、41;第四層:38。如果可以做到,我們再按層級,一層一層的輸出,不就把樹打印出來了嘛!

怎么記錄當前層級呢?對遍歷方法稍加變動即可

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

執行結果:

代碼實現

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

//按層級存儲節點的值
@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();
    }
}

執行結果:

改進

網上的資料大部分到這里就結束了,但看看這個產物,雖然是把樹按層級打印出來了,但很多部分還需要你腦補才行。留白太大,對藝術作品還好,但學習研究還是盡可能精準的好。我想要的是,帶著枝杈的樹!

# 目標

   32
  /  
20    40
     /  
    35   41
     
      38

怎么實現呢?遍歷節點過程中,像Map中存儲節點的時候,我們完全可以知道,它的子節點情況——如果有左子節點,記錄一個/;如果有右子節點,記錄一個。由此,我們可以封裝一個Bean。

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

對代碼進行調整后,效果變成這樣:

雖然還要進行腦補,但似乎容易了些?當然,這不是結束,其實距離目標效果就差最后一步了。我們需要對數值和子節點連接符(“/”、“”)分別存儲,輸出時根據上一層的位置做調整!

給出完整實現:

/**
 * 樹打印
 */
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++;
    }

    // 數據還原
    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` "后面的符號),是因為打印方法還略有不足——有時兩個節點會連在一起,沒辦法看出具體的節點值。分割符的存在算是投機取巧。

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/72723.html

相關文章

  • 一篇文章學會二叉和二叉查找

    摘要:二叉樹和二叉查找樹一個父節點的兩個子節點分別稱為左節點和右節點。下圖展示了一顆二叉樹當考慮某種特殊的二叉樹,比如二叉查找樹時,確定子節點非常重要。實現二叉查找樹定義對象。現在可以創建一個類來表示二叉查找樹。因此二叉查找樹也被叫做二叉排序樹。 樹是計算機科學中經常用到的一種數據結構。樹是一種非線性的數據結構,以分層的方式存儲數據。 樹被用來存儲具有層級關系的數據,比如文件系統中的文件。 ...

    BaronZhang 評論0 收藏0
  • 的算法

    摘要:樹和樹的算法一樹樹的概念樹英語是一種抽象數據類型或是實作這種抽象數據類型的數據結構,用來模擬具有樹狀結構性質的數據集合。一種時間復雜度額外空間復雜度的二叉樹的遍歷方式,為二叉樹的節點個數。 樹和樹的算法 一、樹 1.1 樹的概念 樹(英語:tree)是一種抽象數據類型(ADT)或是實作這種抽象數據類型的數據結構,用來模擬具有樹狀結構性質的數據集合。它是由n(n>=1)個有限節點組成一個...

    RaoMeng 評論0 收藏0
  • 的算法

    摘要:樹和樹的算法一樹樹的概念樹英語是一種抽象數據類型或是實作這種抽象數據類型的數據結構,用來模擬具有樹狀結構性質的數據集合。一種時間復雜度額外空間復雜度的二叉樹的遍歷方式,為二叉樹的節點個數。 樹和樹的算法 一、樹 1.1 樹的概念 樹(英語:tree)是一種抽象數據類型(ADT)或是實作這種抽象數據類型的數據結構,用來模擬具有樹狀結構性質的數據集合。它是由n(n>=1)個有限節點組成一個...

    PiscesYE 評論0 收藏0
  • 學習JavaScript數據結構與算法 —

    摘要:定義樹同散列表一樣,是一種非順序數據結構。一個節點及其后代可以組成一個子樹如圖中的。方法允許傳入子樹一直遍歷左側子節點,直到底部搜索特定值搜索特定值的處理與插入值的處理類似。同理,找左側子樹的最大值替換上來也可以。 定義 樹同散列表一樣,是一種非順序數據結構。現實中樹的例子有家譜、公司組織架構圖及其它樹形結構關系。樹由一系列節點構成,每個節點都有一個父節點(除根節點外)以及零個或多個子...

    shiguibiao 評論0 收藏0

發表評論

0條評論

bawn

|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<