This website requires JavaScript.

一文看懂,Java如何实现遍历的深度优先、广度优先

分类:编程人生 发布于:2020-07-17 11:20:09 字数 2445 120次阅读 java

最近在做一个一键转发的工具,需要统计信息被转发的次数,为了实现无限裂变,我在数据库表的设计时,加入了parentId字段,把表做成了一个树型结构。

列名 类型
id varchar
parentId varchar
其他字段 ...
  1. 递归即是自己调用自己,凡是方法内的有调自己的都属于递归。
public void exampleMethod() {
    exampleMethod() ;
}
  1. 循环不存在自己调用自己,循环可以嵌套。
public void exampleMethod() {
    for(int i = 0 ; i < length ; i ++) {
        for(int j =0 ; j < size; j ++) {

        }
    }
}
  1. 函数调用是有时间和空间消耗的,每一次函数调用,都需要再内存中分配空间以保存参数、返回地址及临时变量。而且往栈里压入数据和弹出数据都需要时间,更何况,每个进程的栈的容量是有限的。因此,递归实现的效率不如循环。
  1. 抛开业务、场景等因素,循环和递归是可以相互改写的。但是一般情况下用递归要比循环的代码逻辑上好理解一些。
  1. 什么是深度优先?
    打个不恰当的比喻,吃面时,你总是一根根的吃,一根不吃完,你不会吃其他的。

  2. 什么是广度优先?
    还是吃面,你总一大口一大口的吃,但是一口吃到嘴巴,你咽不下去,只能咬断了,先咽了再吃另外一口。

  3. 编码实例

用递归实现深度优先

public List<ImageText> getListByParentId(String parentId) {
    return this.imageTextDao.getListByParentId(parentId);
}

//递归
private void count(List<Long> statistics , List<ImageText> imageTextArray) {
    for(ImageText imageText : imageTextArray) {
    statistics.add(1L) ;
    List<ImageText> tempChilds2 = this.imageTextService.getListByParentId(imageText.getId()) ;
    if (CollectionUtils.isNotEmpty(tempChilds2)) {
        this.count(statistics, tempChilds2);
    }
    }
}

//方法入口
public Long countRelayById(String id) {
    List<Long> statistics = Lists.newArrayList() ;
    List<ImageText> imageTextArray = this.imageTextService.getListByParentId(id) ;
    this.count(statistics, imageTextArray) ;
    return statistics.size() ;
}

用循环实现广度优先


public List<ImageText> getListByParentId(String parentId) {
    return this.imageTextDao.getListByParentId(parentId);
}

//循环
public Long countRelayById(String id) {
    Long statistics = 0l ;
    List<ImageText> imageTextArray = this.imageTextService.getListByParentId(id) ;
    while(CollectionUtils.isNotEmpty(imageTextArray)) {
    List<ImageText> tempChilds = null ;

    for (ImageText child : imageTextArray) { // 遍历子节点
        // ------------
        // 获取child内容,或其他处理
        // ------------
        statistics ++ ;

        List<ImageText> tempChilds2 = this.imageTextService.getListByParentId(child.getId()) ;
        if (CollectionUtils.isNotEmpty(tempChilds2)) {
            if(tempChilds == null) {
                    tempChilds = Lists.newArrayList() ;
            }
                    tempChilds.addAll(tempChilds2);
            }
    }
    imageTextArray = tempChilds;
    }
    return statistics;
}

如果觉得老易写的还可以,请在评论区留言、点赞,写的不行请批评~~~~基本都会回复。

文章下方有我微信公众号的二维码,请扫描关注!