算法实战——多叉树全路径遍历

发表于

本文为原创作品，首发于微信公众号：【坂本先生】，如需转载请在文首明显位置标明“转载于微信公众号：【坂本先生】”，否则追究其法律责任。

微信文章地址：实战算法——多叉树全路径遍历

前言

本文研究的是如何对一个多叉树进行全路径的遍历，并输出全路径结果。该问题的研究可以用在：Trie树中查看所有字典值这个问题上。本文将对该问题进行详细的模拟及进行代码实现，讨论了递归和非递归两种方法优劣并分别进行实现，如果读者对这两种方法的优劣不感兴趣可直接跳到问题构建章节进行阅读。文章较长，推荐大家先收藏再进行阅读。

文章目录

递归和非递归比较

这个问题知乎上已经有了很多答案（www.zhihu.com/question/20…

递归

将一个问题分解为若干相对小一点的问题，遇到递归出口再原路返回，因此必须保存相关的中间值，这些中间值压入栈保存，问题规模较大时会占用大量内存。

非递归

执行效率高，运行时间只因循环次数增加而增加，没什么额外开销。空间上没有什么增加

递归的劣势和优势

递归的劣势

  • 递归容易产生”栈溢出”错误（stack overflow）。因为需要同时保存成千上百个调用记录，所以递归非常耗费内存。
  • 效率方面，递归可能存在冗余计算。使用递归的方式会有冗余计算（比如最典型的是斐波那契数列，计算第6个需要计算第4个和第5个，而计算第5个还需要计算第4个，所处会重复）。迭代在这方面有绝对优势。

递归的优势

递归拥有较好的代码可读性，对于数据量不算太大的运算，使用递归算法绰绰有余。

问题构建

现在存在一个多叉树，其结点情况如下图，需要给出方法将叶子节点的所有路径进行输出。

最终输出结果应该有5个，即[rad,rac,rbe,rbf,rg]

问题解决

首先我们对结点进行分析，构建一个结点类（TreeNode），然后我们需要有一个树类（MultiTree），包含了全路径打印的方法。最后我们需要建立一个Main方法进行测试。最终的项目结构如下：

注意：本文使用了lombok注解，省去了get，set及相关方法的实现。如果读者没有使用过lombok也可以自己编写对应的get，set方法，后文会对每个类进行说明需要进行实现的方法，对核心代码没有影响。

TreeNode类

节点类，主要包含两个字段：

  • content：用于存储当前节点存储的内容
  • childs：用于存储子节点信息，HashMap的string存储的是子节点内容，childs采用HashMap实现有利于实现子节点快速查找

该类中包含了必要的get，set方法，一个无参构造器，一个全参构造器

1
2
3
4
5
6
7
复制代码@Data
@RequiredArgsConstructor
@AllArgsConstructor
public class TreeNode {
    private String content;
    private HashMap<String,TreeNode> childs;
}

MultiTree类

包含的字段只有两个：

  • root：根节点
  • pathList：用于存储遍历过程中得到的路径

该类中的构造函数中我手动创建问题构建中的树，相关代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
复制代码    public MultiTree(){
        //创建根节点
        HashMap rootChilds = new HashMap();
        this.root = new TreeNode("r",rootChilds);

        //第一层子节点
        HashMap aChilds = new HashMap();
        TreeNode aNode = new TreeNode("a",aChilds);

        HashMap bChilds = new HashMap();
        TreeNode bNode = new TreeNode("b",bChilds);

        HashMap gChilds = new HashMap();
        TreeNode gNode = new TreeNode("g",gChilds);

        //第二层结点
        HashMap dChilds = new HashMap();
        TreeNode dNode = new TreeNode("d",dChilds);

        HashMap cChilds = new HashMap();
        TreeNode cNode = new TreeNode("c",cChilds);

        HashMap eChilds = new HashMap();
        TreeNode eNode = new TreeNode("e",eChilds);

        HashMap fChilds = new HashMap();
        TreeNode fNode = new TreeNode("f",fChilds);

        //建立结点联系
        rootChilds.put("a",aNode);
        rootChilds.put("b",bNode);
        rootChilds.put("g",gNode);

        aChilds.put("d",dNode);
        aChilds.put("c",cNode);

        bChilds.put("e",eNode);
        bChilds.put("f",fNode);
    }

在这个树中，每个节点都有childs，如果是叶子节点，则childs中的size为0，这是下面判断一个节点是否为叶子节点的重要依据接下来我们会对核心算法代码进行实现。

Main类

1
2
3
4
5
6
7
8
9
复制代码public class Main {
    public static void main(String[] args) {
        MultiTree tree = new MultiTree();
        List<String> path1 = tree.listAllPathByRecursion();
        System.out.println(path1);
        List<String> path2 = tree.listAllPathByNotRecursion();
        System.out.println(path2);
    }
}

递归方法

需要完善MultiTree类中的listAllPathByRecursion方法和listPath方法

递归过程方法：listAllPathByRecursion

算法流程图如下：

代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
复制代码public void listPath(TreeNode root,String path){

    if(root.getChilds().isEmpty()){//叶子节点
        path = path + root.getContent();
        pathList.add(path); //将结果保存在list中
        return;
    }else{ //非叶子节点
        path = path  + root.getContent() + "->";

        //进行子节点的递归
        HashMap<String, TreeNode> childs = root.getChilds();
        Iterator iterator = childs.entrySet().iterator();
        while(iterator.hasNext()){
            Map.Entry entry = (Map.Entry)iterator.next();
            TreeNode childNode  = (TreeNode) entry.getValue();
            listPath(childNode,path);
        }
    }
}

递归调用方法：listAllPathByRecursion

1
2
3
4
5
6
复制代码public List<String> listAllPathByRecursion(){
    //清空路径容器
    this.pathList.clear();
    listPath(this.root,"");
    return this.pathList;
}

非递归方法

非递归方法的代码量和递归方法一比，简直是太多了，而且内容不好理解，不知道大家能不能看懂我写的代码，我已经尽力写上相关注释了。

首先建立了两个栈，示意图如下，栈的实现使用Deque，需要注意的是代码中的空指针情况。

  • 主栈：用于处理节点和临时路径的存储，主栈为空时说明，节点处理完毕
  • 副栈：用于存放待处理节点，副栈为空时说明，节点遍历完毕

其他相关变量介绍：

  • popCount ：用于存储一个节点的子节点的弹出个数。例如r有3个子节点，如果r对应的弹出个数为3，说明r的叶子节点处理完毕，可以弹出r。因为r弹出后，主栈没有元素，故处理完毕。
  • curString：用于存储临时路径，当主栈元素变化时，curString也会进行变化，例如上图curString为“r->g->”，当栈顶元素弹出时，需要减去”g->”。如果栈顶元素是叶子节点说明该条路径已经遍历完成，需要添加到path路径容器中。

程序流程图：

具体实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
复制代码/**
 * 非递归方法输出所有路径
 */
public List<String> listAllPathByNotRecursion(){
    //清空路径容器
    this.pathList.clear();
    //主栈，用于计算处理路径
    Deque<TreeNode> majorStack = new ArrayDeque();
    //副栈，用于存储待处理节点
    Deque<TreeNode> minorStack = new ArrayDeque();
    minorStack.addLast(this.root);

    HashMap<String,Integer> popCount = new HashMap<>();
    String curString  = "";

    while(!minorStack.isEmpty()){
        //出副栈，入主栈
        TreeNode minLast = minorStack.pollLast();
        majorStack.addLast(minLast);
        curString+=minLast.getContent()+"->";
        //将该节点的子节点入副栈
        if(!minLast.getChilds().isEmpty()){
            HashMap<String, TreeNode> childs = minLast.getChilds();
            Iterator iterator = childs.entrySet().iterator();
            while(iterator.hasNext()){
                Map.Entry entry = (Map.Entry)iterator.next();
                TreeNode childNode  = (TreeNode) entry.getValue();
                minorStack.addLast(childNode);
            }
        }
        //出主栈
        TreeNode majLast = majorStack.peekLast();
        //循环条件：栈顶为叶子节点 或 栈顶节点孩子节点遍历完了（需要注意空指针问题）
        while(majLast.getChilds().size() ==0 ||
                (popCount.get(majLast.getContent())!=null && popCount.get(majLast.getContent()).equals(majLast.getChilds().size()))){

            TreeNode last = majorStack.pollLast();
            majLast = majorStack.peekLast();

            if(majLast == null){ //此时主栈为空，运算完毕
                return this.pathList;
            }
            if(popCount.get(majLast.getContent())==null){//第一次弹出孩子节点，弹出次数设为1
                popCount.put(majLast.getContent(),1);
            }else{ //非第一次弹出孩子节点，在原有基础上加1
                popCount.put(majLast.getContent(),popCount.get(majLast.getContent())+1);
            }
            String lastContent = last.getContent();
            if(last.getChilds().isEmpty()){//如果是叶子节点才将结果加入路径集中
                this.pathList.add(curString.substring(0,curString.length()-2));
            }
            //调整当前curString，减去2是减的“->”这个符号
            curString = curString.substring(0,curString.length()-lastContent.length()-2);
        }
    }
    return this.pathList;
}

测试

调用Main类中的main方法，得到执行结果，和预期结果相同，代码通过测试

1
2
复制代码listAllPathByRecursion[r->a->c, r->a->d, r->b->e, r->b->f, r->g]
listAllPathByNotRecursion[r->g, r->b->f, r->b->e, r->a->d, r->a->c]

结论

其实该文章是我在研究《基于Trie树的敏感词过滤算法实现》的一个中间产物，其实原来应该也实现过多叉树的路径遍历问题，但是因为时间原因加之原来没有较好的知识管理系统，代码和笔记都丢了，今天趁机再进行一波总结。希望该文章能够帮助到需要的人。

参考资料

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%