资讯专栏INFORMATION COLUMN

【树结构2】树打印

bawn / 3299人阅读

摘要:如果对树的基本操作还不清楚的话,可参看树结构查找二叉树直接给出遍历方式打印节点,这个位置是中序遍历既然我们已经可以遍历它,那有没有方式可以记录下当前节点在第几层呢也就是,第一层第二层第三层第四层。

载一棵小树苗,精心培育,总有一天会长成参天大树
                比如查找二叉、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` "后面的符号),是因为打印方法还略有不足——有时两个节点会连在一起,没办法看出具体的节点值。分割符的存在算是投机取巧。

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/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元查看
<